Automata Approach to XML Data Indexing

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F18%3A00316899" target="_blank" >RIV/68407700:21240/18:00316899 - isvavai.cz</a>

Result on the web

<a href="http://www.mdpi.com/2078-2489/9/1/12" target="_blank" >http://www.mdpi.com/2078-2489/9/1/12</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/info9010012" target="_blank" >10.3390/info9010012</a>

Result language

angličtina

Original language name

Automata Approach to XML Data Indexing

Original language description

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 O(m) and does not depend on the size of the original XML document.

Czech name

—

Czech description

—

Type

J_SC - Article in a specialist periodical, which is included in the SCOPUS database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Information

ISSN

2078-2489

e-ISSN

2078-2489

Volume of the periodical

9

Issue of the periodical within the volume

1

Country of publishing house

CH - SWITZERLAND

Number of pages

25

Pages from-to

—

UT code for WoS article

000436146300012

EID of the result in the Scopus database

2-s2.0-85040102641