Document Server@UHasselt >
Research >
Research publications >

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
Paredaens, Jan
Issue Date: 2011
Citation: 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
URI: http://hdl.handle.net/1942/12114
DOI: 10.1093/comjnl/bxq055
ISI #: 000292339500007
ISSN: 0010-4620
Category: A1
Type: Journal Contribution
Validation: ecoom, 2012
Appears in Collections: Research publications

Files in This Item:

There are no files associated with this item.

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