Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/10727
Title: | A study of a positive fragment of path queries: expressiveness, normal form, and minimization | Authors: | WU, Yuqing VAN GUCHT, Dirk GYSSENS, Marc PAREDAENS, Marc |
Issue Date: | 2009 | Publisher: | Springer | Source: | Sexton, Alan P. (Ed.) Dataspace: The Final Frontier, 26th British National Conference on Databases, BNCOD 26, Birmingham, UK, July 7-9, 2009. Proceedings. p. 133-145. | Series/Report: | Lecture Notes in Computer Science | Series/Report no.: | 5588 | Abstract: | We study the expressiveness of a positive fragment of path queries, denoted Path, on node-labeled trees documents. The expressiveness of Path is studied from two angles. First, we establish that Path is equivalent in expressive power to a particular sub-fragment as well as to the class of tree queries, a sub-class of the first-order conjunctive queries defined over label, parent-child, and child-parent predicates. The translation algorithm from tree queries to Path yields a normal form for Path queries. Using this normal form, we can decompose a Path query into sub-queries that can be expressed in a very small sub-fragment of Path for which efficient evaluation strategies are available. Second, we characterize the expressiveness of Path in terms of its ability to resolve nodes in a document. This result is used to show that each tree query can be translated to a unique, equivalent, and minimal tree query. The combination of these results yields an effective strategy to evaluate a large class of path queries on documents. | Document URI: | http://hdl.handle.net/1942/10727 | ISBN: | 978-3-642-02842-7 | DOI: | 10.1007/978-3-642-02843-4 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.