Optimizing Approximations of DNF Query Lineage in Probabilistic XML - IMT - Institut Mines-Télécom Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Optimizing Approximations of DNF Query Lineage in Probabilistic XML

Résumé

Probabilistic XML is a probabilistic model for uncertain tree-structured data, with applications to data integration, information extraction, or uncertain version control. We explore in this work efficient algorithms for evaluating tree-pattern queries with joins over probabilistic XML or, more specifically, for listing the answers to a query along with their computed or approximated probability. The approach relies on, first, producing the lineage query by evaluating it over the probabilistic XML document, and, second, looking for an optimal strategy to compute the probability of the lineage formula. This latter part relies on a query-optimizer–like approach: exploring different evaluation plans for different parts of the formula and estimating the cost of each plan, using a cost model for the various evaluation algorithms. We demonstrate the efficiency of this approach on datasets used in previous research on probabilistic XML querying, as well as on synthetic data. We also compare the performance of our query engine with EvalDP, Trio, and MayBMS/SPROUT.
Fichier non déposé

Dates et versions

hal-00874442 , version 1 (17-10-2013)

Identifiants

  • HAL Id : hal-00874442 , version 1

Citer

Asma Souihli, Pierre Senellart. Optimizing Approximations of DNF Query Lineage in Probabilistic XML. ICDE (International Conference on Data Engineering), Apr 2013, Brisbane, Australia. pp.721-732. ⟨hal-00874442⟩
103 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More