2009 | OriginalPaper | Buchkapitel
A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form, and Minimization
verfasst von : Yuqing Wu, Dirk Van Gucht, Marc Gyssens, Jan Paredaens
Erschienen in: Dataspace: The Final Frontier
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the expressiveness of a positive fragment of path queries, denoted Path
$\mathstrut^+$
, on node-labeled trees documents. The expressiveness of Path
$\mathstrut^+$
is studied from two angles. First, we establish that Path
$\mathstrut^+$
is equivalent in expressive power to a particular sub-fragment as well as to the class of tree queries, a sub-class of the first-order conjunctive queries defined over label, parent-child, and child-parent predicates. The translation algorithm from tree queries to Path
$\mathstrut^+$
yields a normal form for Path
$\mathstrut^+$
queries. Using this normal form, we can decompose a Path
$\mathstrut^+$
query into sub-queries that can be expressed in a very small sub-fragment of Path
$\mathstrut^+$
for which efficient evaluation strategies are available. Second, we characterize the expressiveness of Path
$\mathstrut^+$
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.