Early = Earliest?

Abstract : Early query answering is the core issue of memory efficient query evaluation on data streams. The idea is to select and reject answer candidates as early as possible on the stream, so that they do not have to be stored in main memory. Since earliest query answering is unfeasible for XPath, as first no- ticed by Benedikt, Jeffrey and Ley-Wild in 2008, most exist- ing streaming algorithms for XPath approximate it in some early manner, while focussing on high time efficiency. Such approximations, however, spoil all theoretical guarantees on memory efficiency. In this paper, we prove that earliest query answering is indeed feasible for positive Forward XPath queries, which have neither unsatisfiable nor valid subqueries. The core in- sight is that a variant of Colmerauer's independence property can be proven for the corresponding fragment of the FXP tree logic. Based on this independence property, we can show that the early query answering algorithm from [13], which is based on a compiler from FXP to early nested word automata, is indeed earliest for all positive FXP0 queries with neither unsatisfiable nor valid subformulas. Further- more, this algorithm outperforms most previous algorithms for XPath evaluation on XML streams in time efficiency and coverage, as shown elsewhere. Available here.

Type de document :
[Research Report] inria lille. 2013
Liste complète des métadonnées

Contributeur : Joachim Niehren <>
Soumis le : mercredi 16 octobre 2013 - 12:41:50
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27


  • HAL Id : hal-00873742, version 1


Anthony Lick, Joachim Niehren. Early = Earliest?. [Research Report] inria lille. 2013. 〈hal-00873742〉



Consultations de la notice