{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:55:56Z","timestamp":1760241356699,"version":"build-2065373602"},"reference-count":46,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2018,1,6]],"date-time":"2018-01-06T00:00:00Z","timestamp":1515196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Czech Technical University in Prague (The Ministry of Education, Youth and Sports)","award":["SGS17\/209\/OHK3\/3T\/18"],"award-info":[{"award-number":["SGS17\/209\/OHK3\/3T\/18"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>The internal structure of XML documents can be viewed as a tree. Trees are among the fundamental and well-studied data structures in computer science. They express a hierarchical structure and are widely used in many applications. This paper focuses on the problem of processing tree data structures; particularly, it studies the XML index problem. Although there exist many state-of-the-art methods, the XML index problem still belongs to the active research areas. However, existing methods usually lack clear references to a systematic approach to the standard theory of formal languages and automata. Therefore, we present some new methods solving the XML index problem using the automata theory. These methods are simple and allow one to efficiently process a small subset of XPath. Thus, having an XML data structure, our methods can be used efficiently as auxiliary data structures that enable answering a particular set of queries, e.g., XPath queries using any combination of the child and descendant-or-self axes. Given an XML tree model with n nodes, the searching phase uses the index, reads an input query of size m, finds the answer in time \r\n          \r\n            \r\n              \r\n                O\r\n                (\r\n                m\r\n                )\r\n              \r\n            \r\n          \r\n         and does not depend on the size of the original XML document.<\/jats:p>","DOI":"10.3390\/info9010012","type":"journal-article","created":{"date-parts":[[2018,1,8]],"date-time":"2018-01-08T12:26:02Z","timestamp":1515414362000},"page":"12","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Automata Approach to XML Data Indexing"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6624-4433","authenticated-orcid":false,"given":"Eli\u0161ka","family":"\u0160est\u00e1kov\u00e1","sequence":"first","affiliation":[{"name":"Faculty of Information Technology, Czech Technical University in Prague, Th\u00e1kurova 9, 160 00 Praha 6, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Janou\u0161ek","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Czech Technical University in Prague, Th\u00e1kurova 9, 160 00 Praha 6, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,1,6]]},"reference":[{"key":"ref_1","unstructured":"Goldman, R., and Widom, J. (1997). DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Stanford University. Technical Report."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Pettovello, P.M., and Fotouhi, F. (2006, January 23\u201327). MTree: An XML XPath Graph Index. Proceedings of the 2006 ACM Symposium on Applied Computing (SAC), Dijon, France.","DOI":"10.1145\/1141277.1141389"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Zou, Q., Liu, S., and Chu, W.W. (2004, January 12\u201313). Ctree: A compact tree for indexing XML data. Proceedings of the 6th Annual ACM International Workshop on Web Information and Data Management, Washington, DC, USA.","DOI":"10.1145\/1031453.1031462"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tang, N., Yu, J., Ozsu, M., and Wong, K.F. (2008, January 7\u201312). Hierarchical indexing approach to support XPath queries. Proceedings of the IEEE 24th International Conference on Data Engineering, Cancun, Mexico.","DOI":"10.1109\/ICDE.2008.4497606"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kaushik, R., Bohannon, P., Naughton, J.F., and Korth, H.F. (2002, January 3\u20136). Covering indexes for branching path queries. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, WI, USA.","DOI":"10.1145\/564691.564707"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/3-540-49257-7_18","article-title":"Index structures for path expressions","volume":"Volume 1540","author":"Beeri","year":"1999","journal-title":"Database Theory\u2014ICDT \u201999"},{"key":"ref_7","unstructured":"Rao, P., and Moon, B. (2004, January 2). PRIX: Indexing and querying XML using prufer sequences. Proceedings of the 20th International Conference on Data Engineering, Boston, MA, USA."},{"key":"ref_8","first-page":"988","article-title":"AB-Index: An Efficient Adaptive Index for Branching XML Queries","volume":"Volume 4443","author":"Kotagiri","year":"2007","journal-title":"Advances in Databases: Concepts, Systems and Applications"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chung, C.W., Min, J.K., and Shim, K. (2002, January 3\u20136). APEX: An adaptive path index for XML data. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, WI, USA.","DOI":"10.1145\/564691.564706"},{"key":"ref_10","unstructured":"Li, Q., and Moon, B. (2001, January 11\u201314). Indexing and querying XML data for regular path expressions. Proceedings of the 27th International Conference on Very Large Data Bases, Roma, Italy."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wang, H., Park, S., Fan, W., and Yu, P.S. (2003, January 9\u201312). ViST: A dynamic index method for querying XML data by tree structures. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA.","DOI":"10.1145\/872757.872774"},{"key":"ref_12","unstructured":"Wang, H., and Meng, X. (2005, January 5\u20138). On the sequencing of tree structures for XML indexing. Proceedings of the IEEE 21st International Conference on Data Engineering, Tokoyo, Japan."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Tung, H.D.T., and Luong, D.D. (2016). An improved indexing method for Xpath queries. Indian J. Sci. Technol., 9.","DOI":"10.17485\/ijst\/2016\/v9i31\/92731"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Tatarinov, I., Viglas, S.D., Beyer, K., Shanmugasundaram, J., Shekita, E., and Zhang, C. (2002, January 3\u20136). Storing and querying ordered XML using a relational database system. Proceedings of the 2002 ACM SIGMOD international conference on Management of data, Madison, WI, USA.","DOI":"10.1145\/564691.564715"},{"key":"ref_15","unstructured":"Kha, D.D., Yoshikawa, M., and Uemura, S. (2001, January 2\u20136). An XML indexing structure with relative region coordinate. Proceedings of the IEEE 17th International Conference on Data Engineering, Heidelberg, Germany."},{"key":"ref_16","unstructured":"Clark, J., and DeRose, S. (2018, January 06). Available online: https:\/\/www.w3.org\/TR\/xpath\/."},{"key":"ref_17","unstructured":"DeRose, S. (2018, January 06). Available online: https:\/\/www.w3.org\/TR\/WD-xptr."},{"key":"ref_18","unstructured":"DeRose, S. (2018, January 06). Available online: https:\/\/www.w3.org\/TR\/xlink11\/."},{"key":"ref_19","unstructured":"Mandhani, B., and Suciu, D. (September, January 30). Query Caching and view selection for XML databases. Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"\u0160est\u00e1kov\u00e1, E., and Janou\u0161ek, J. (2015). Tree string path subsequences automaton and its use for indexing XML documents. International Symposium on Languages, Applications and Technologies, Springer.","DOI":"10.1007\/978-3-319-27653-3_17"},{"key":"ref_21","unstructured":"\u0160est\u00e1kov\u00e1, E., and Janou\u0161ek, J. (2017). Indexing XML documents using tree paths automaton. OASIcs-OpenAccess Series in Informatics, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., and Lecroq, T. (2007). Algorithms on Strings, Cambridge University Press.","DOI":"10.1017\/CBO9780511546853"},{"key":"ref_23","unstructured":"Crochemore, M., and Rytter, W. (1994). Text Algorithms, Oxford University Press."},{"key":"ref_24","unstructured":"Melichar, B., Janou\u0161ek, J., and Flouri, T. (2008). Introduction to Arbology, Czech Technical University."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"88","DOI":"10.4103\/0256-4602.49086","article-title":"Node labeling schemes in XML query optimization: A survey and trends","volume":"26","year":"2009","journal-title":"IETE Tech. Rev."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.jcss.2006.10.003","article-title":"Automata for XML\u2014A survey","volume":"73","author":"Schwentick","year":"2007","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_27","unstructured":"Br\u00fcggemann-Klein, A., and Wood, D. (2018, January 06). Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.50.5397."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/601858.601869","article-title":"Automata theory for XML researchers","volume":"31","author":"Neven","year":"2002","journal-title":"ACM Sigmod Rec."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Neven, F. (2002). Automata, logic, and XML. Computer Science Logic, Springer.","DOI":"10.1007\/3-540-45793-3_2"},{"key":"ref_30","unstructured":"Diao, Y., Fischer, P., Franklin, M.J., and To, R. (March, January 26). Yfilter: Efficient and scalable filtering of XML documents. Proceedings of the IEEE 18th International Conference on Data Engineering, San Jose, CA, USA."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1145\/1042046.1042051","article-title":"Processing XML streams with deterministic automata and stream indexes","volume":"29","author":"Green","year":"2004","journal-title":"ACM Trans. Database Syst."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.jpdc.2015.07.010","article-title":"An automaton-based index scheme supporting twig queries for on-demand XML data broadcast","volume":"86","author":"Liu","year":"2015","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/s00778-003-0094-0","article-title":"Re-tree: An efficient index structure for regular expressions","volume":"12","author":"Chan","year":"2003","journal-title":"VLDB J."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Segoufin, L., and Vianu, V. (2002, January 3\u20135). Validating streaming XML documents. Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Madison, WI, USA.","DOI":"10.1145\/543613.543622"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1145\/1111627.1111631","article-title":"Taxonomy of XML schema languages using formal language theory","volume":"5","author":"Murata","year":"2005","journal-title":"ACM Trans. Int. Technol."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Fan, W., Geerts, F., Jia, X., and Kementsietsidis, A. (2007, January 15\u201320). Rewriting regular XPath queries on XML views. Proceedings of the IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367912"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","article-title":"Finite automata and their decision problems","volume":"3","author":"Rabin","year":"1959","journal-title":"IBM J. Res. Dev."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/3-540-45735-6_6","article-title":"On the Size of DASG for Multiple Texts","volume":"Volume 2476","author":"Laender","year":"2002","journal-title":"String Processing and Information Retrieval"},{"key":"ref_39","unstructured":"Hoshino, H., Shinohara, A., Takeda, M., and Arikawa, S. (2000, January 29). Online construction of subsequence automata for multiple texts. Proceedings of the SPIRE Seventh International Symposium on String Processing and Information Retrieval, A Curuna, Spain."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","article-title":"Searching subsequences","volume":"78","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S1570-8667(03)00029-7","article-title":"Directed acyclic subsequence graph\u2014Overview","volume":"1","author":"Crochemore","year":"2003","journal-title":"J. Discret. Algorithms"},{"key":"ref_42","unstructured":"\u0160est\u00e1kov\u00e1, E. (2015). Indexing XML documents. [Master\u2019s Thesis, Czech Technical University in Prague, Faculty of Information Technology]."},{"key":"ref_43","unstructured":"Schimdt, A., Busse, R., Carey, M., Florescu, D., Kersten, M., Manolescu, I., and Waas, F. (2018, January 06). XMark\u2013An XML Benchmark Project. Available online: http:\/\/www.xml-benchmark.org\/."},{"key":"ref_44","unstructured":"(2018, January 06). UW XML Repository. Available online: http:\/\/aiweb.cs.washington.edu\/research\/projects\/xmltk\/xmldata\/www\/repository.html."},{"key":"ref_45","unstructured":"Saxonica (2018, January 06). Saxon\u2013The XSLT and XQuery Processor. Available online: http:\/\/saxon.sourceforge.net\/."},{"key":"ref_46","unstructured":"Apache Software Foundation (2018, January 06). Available online: http:\/\/xalan.apache.org\/."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/1\/12\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:50:21Z","timestamp":1760194221000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/1\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,6]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2018,1]]}},"alternative-id":["info9010012"],"URL":"https:\/\/doi.org\/10.3390\/info9010012","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2018,1,6]]}}}