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é:   
Semantic acyclicity of conjunctive queries
du groupe Séminaire Méthodes Formelles

Date 2016-05-03  11:00-12:00
TitreSemantic acyclicity of conjunctive queries 
RésuméThe evaluation problem for Conjunctive Queries (CQ) is known to be NP-complete in combined complexity and W[1]-complete in parameterized complexity. However, acyclic CQs and more generally CQs of bounded tree-width can be evaluated in polynomial time in combined complexity and they are fixed-parameter tractable. We study the problem of whether a CQ can be rewritten into an equivalent CQ of bounded tree-width, in the presence of unary functional dependencies. We show that this problem is decidable in doubly exponential time, or in exponential time for a restricted class of queries. When it exists, the algorithm also yields a witness query. This is a work that will appear in LICS this summer. 
Lieu76 
OrateurDiego Figueira 
Emailwww.labri.fr/perso/dfigueir/ 
UrlCNRS / LaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index