Λεπτομέρειες

ΕίδοςΔημοσίευση
ΚωδικόςTR-2007-12
ΤίτλοςEvaluation of Partial Path Queries on XML Data
ΣυγγραφέαςΣτέφανος Σουλδάτος, Xiaoying Wu, Δημήτρης Θεοδωράτος, Θεόδωρος Δαλαμάγκας, Τίμος Σελλής
Έτος2007
Λέξεις κλειδιάpartial path query, partial path-pattern query, XML query evaluation, XML query processing, tree-structured data
ΠερίληψηXML query languages typically allow the specification of structural patterns of elements. Finding the occurrences of such patterns in an XML tree is the key operation in XML query processing. Many algorithms have been presented for this operation. These algorithms focus mainly on the evaluation of path-pattern or tree-pattern queries. In this paper, we define a partial path-pattern query language, and we address the problem of its e±cient evaluation on XML data. In order to process partial path-pattern queries, we introduce a set of sound and complete inference rules to characterize structural relationship derivation. We provide necessary and su±cient conditions for detecting query unsatisfiability and node redundancy. We show how partial path-pattern queries can be equivalently put in a canonical directed acyclic graph form. We developed two stack-based algorithms for the evaluation of partial path-pattern queries, PartialMJ and PartialPathStack. PartialMJ computes answers to the query by merge-joining the results of the root-to-leaf paths of a spanning tree of the query. PartialPathStack exploits a topological order of the nodes of the query graph to match the query pattern as a whole to the XML tree. The experimental evaluation of our algorithms shows that PartialPathStack is independent of intermediate results and largely outperforms PartialMJ.
ΚατηγορίαWWW and DBMS
ΔημοσίευσηProceedings of the 16th ACM Conference on Information and Knowledge Management (CIKM), Lisbon, Portugal, November 6-9, 2007
Αρχείο Επισκόπηση


Επιστροφή στην αρχική σελίδα