Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Efficient Enumeration of Conjunctive Queries over X-underbar Structures
du 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 
Emailolivier.gauwin@umons.ac.be 
UrlUniversity of Mons 



Aucun document lié à cet événement.

Retour
Retour à l'index