Please use this identifier to cite or link to this item:
Title: A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form and Minimization
Authors: Wu, Yuqing
Van Gucht, Dirk
Paredaens, Jan
Issue Date: 2011
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
Keywords: XML; path query; normal form; expressiveness; minimization
Document URI:
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


checked on Sep 5, 2020


checked on May 21, 2022

Page view(s)

checked on May 20, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.