Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/12114
Title: | A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form and Minimization | Authors: | Wu, Yuqing Van Gucht, Dirk GYSSENS, Marc Paredaens, Jan |
Issue Date: | 2011 | Publisher: | OXFORD UNIV PRESS | Source: | COMPUTER JOURNAL, 54(7). p. 1091-1118 | Abstract: | We study the expressiveness of a positive fragment of path queries, denoted Path(+), on documents that can be represented as node-labeled trees. The expressiveness of Path(+) is studied from two angles. First, we establish that Path(+) is equivalent in expressive power to two particular subfragments, as well as to the class of tree queries, a subclass of the first-order conjunctive queries defined over the 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 subqueries that can be expressed in a very small 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. | Notes: | [Gyssens, M] Hasselt Univ, Fac Sci, B-3590 Diepenbeek, Belgium [Gyssens, M] Transnatl Univ Limburg, B-3590 Diepenbeek, Belgium [Wu, YQ; Van Gucht, D] Indiana Univ, Sch Informat & Comp, Bloomington, IN 47405 USA [Paredaens, J] Univ Antwerp, Dept Math & Comp Sci, B-2020 Antwerp, Belgium marc.gyssens@uhasselt.be | Keywords: | XML; path query; normal form; expressiveness; minimization | Document URI: | http://hdl.handle.net/1942/12114 | ISSN: | 0010-4620 | e-ISSN: | 1460-2067 | DOI: | 10.1093/comjnl/bxq055 | ISI #: | 000292339500007 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2012 |
Appears in Collections: | Research publications |
Show full item record
SCOPUSTM
Citations
11
checked on Sep 5, 2020
WEB OF SCIENCETM
Citations
10
checked on Oct 13, 2024
Page view(s)
72
checked on Apr 26, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.