A study of a positive fragment of path queries: Expressiveness, normal form, and minimization

Y. Wu, D. Van Gucht, M. Gyssens, J. Paredaens

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We study the expressiveness of a positive fragment of path queries, denoted Path, on node-labeled trees documents. The expressiveness of Path is studied from two angles. First, we establish that Path 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 yields a normal form for Path queries. Using this normal form, we can decompose a Path query into sub-queries that can be expressed in a very small sub-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.
Original languageEnglish
Title of host publicationDataspace: The Final Frontier (26th British National Conference on Databases, BNCOD 26, Birmingham, UK, July 7-9, 2009. Proceedings)
EditorsA.P. Sexton
Place of PublicationBerlin
PublisherSpringer
Pages133-145
ISBN (Print)978-3-642-02842-7
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
Volume5588
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'A study of a positive fragment of path queries: Expressiveness, normal form, and minimization'. Together they form a unique fingerprint.

  • Cite this

    Wu, Y., Van Gucht, D., Gyssens, M., & Paredaens, J. (2009). A study of a positive fragment of path queries: Expressiveness, normal form, and minimization. In A. P. Sexton (Ed.), Dataspace: The Final Frontier (26th British National Conference on Databases, BNCOD 26, Birmingham, UK, July 7-9, 2009. Proceedings) (pp. 133-145). (Lecture Notes in Computer Science; Vol. 5588). Berlin: Springer. https://doi.org/10.1007/978-3-642-02843-4_14