Evènement pour le groupe Graphes et Logique

Date 2011-03-08  11:00-12:00
TitreEfficient Enumeration of Conjunctive Queries over X-underbar Structures 
RésuméThis talk focuses on efficient enumeration algorithms for conjunctive queries for databases over binary relations that satisfy the X-underbar property. Tree-like relations such as XPath axes or grids are natural examples of such relations. Enumeration algorithms amount to output answers to queries with a small delay between consecutive answers, while allowing preprocessing the input structure. We first present an algorithm for conjunctive queries over X-underbar structures, avoiding an exponential blowup appearing in existing algorithms. Then, we consider acyclic conjunctive queries and show that such queries admit an enumeration algorithm with a smaller delay. As an application of our method, we also show how these algorithms apply to XPath queries evaluation over XML documents. Finally, we consider conjunctive queries with possible inequalities between variables, which query evaluation turns out to be NP-hard.  
Lieusalle 76 
OrateurOlivier Gauwin 
UrlUniversity of Mons 

Aucun document lié à cet événement.

Retour à l'index