Title
A study of a positive fragment of path queries: expressiveness, normal form, and minimization A study of a positive fragment of path queries: expressiveness, normal form, and minimization
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
conferenceObject
Publication
Berlin :Springer, [*]
Subject
Computer. Automation
Source (book)
Dataspace, the final frontier: proceedings of the 26th British National Conference on Databases, BNCOD 26, Birmingham, UK, July 7-9, 2009
ISBN - Hoofdstuk
978-3-642-02842-7
ISI
000270351600014
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000270351600014&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000270351600014&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle