Publication
Title
A study of a positive fragment of path queries : expressiveness, normal form and minimization
Author
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, parentchild and childparent 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.
Language
English
Source (journal)
The computer journal. - London
Publication
London : 2011
ISSN
0010-4620
Volume/pages
54:7(2011), p. 1091-1118
ISI
000292339500007
Full text (Publishers DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 30.08.2011
Last edited 13.04.2017
To cite this reference