Efficient Algorithms for Processing XPath Queries

Efficient Algorithms for Processing XPath Queries,Georg Gottlob,Christoph Koch,Reinhard Pichler

Efficient Algorithms for Processing XPath Queries   (Citations: 317)
BibTex | RIS | RefWorks Download
Our experimental analysis of several popu- lar XPath processors reveals a striking fact: Query evaluation in each of the systems re- quires time exponential in the size of queries in the worst case. We show that XPath can be processed much more ecien tly, and pro- pose main-memory algorithms for this prob- lem with polynomial-time combined query evaluation complexity. Moreover, we present two fragments of XPath for which linear-time query processing algorithms exist.
Conference: Very Large Data Bases - VLDB , pp. 95-106, 2002
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Our observation that a bottom-up translation can be more efficient than a straightforward top-down approach has an analogue in the area of XPath query evaluation [19]...

    Matthias P. Kriegeret al. Automatic and efficient simulation of operation contracts

    • ...The main value of our work is to provide the first practical and public tool for compressed indexing of XML data, dubbed Succinct XML Self-Index (SXSI), which takes little space, solves a significant portion of XPath (currently we support at least Core XPath [12], i.e., all navigational axes, plus the three text predicates = (equality), contains, and starts-with), and largely outperforms the best public softwares supporti ng XPath we are ...
    • ...As a first shot, we target the “Core XPath” subset [12] of XPath 1.0...

    Diego Arroyueloet al. Fast in-memory XPath search using compressed indexes

    • ...The intuition behind the N(arrowed)E(extended)X(Path)I query language is that it restricts Core XPath [8] to only the descendant axis and extends it with a function about(P,S) which takes a path P and a string S as arguments [18]...

    Maria-Hendrike Peetzet al. Tree patterns with Full Text Search

    • ...Also, it has been shown that XML documents with recursive schemata have not been efficiently implemented by many state of the art commercial software systems [18], although more recent research databases have done so, such as MonetDB [28]...

    P. Mark Pettovelloet al. XPath query processing improvements

    • ...Core-XPath (introduced in [6]) is the fragment of XPath that captures all the navigational behavior of XPath...

    Diego Figueira. Satisfiability of downward XPath with data equality tests

Sort by: