|
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
| |
|
DOI
|
|
|
|
10.1093/COMJNL/BXQ055
| |
|
Volume/pages
|
|
|
|
54
:7
(2011)
, p. 1091-1118
| |
|
ISI
|
|
|
|
000292339500007
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|