Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 23 Novembre 2004

Sur la complexité de l'évaluation de requêtes acycliques

par Arnaud Durand (LACL, Université de Créteil)

Dans la littérature sur l'optimisation des requêtes dans les bases de données, on a mis en évidence (vers 1980) et beaucoup étudié depuis cette date un ensemble de requêtes (qu_on peut écrire en SQL) appelées « requêtes acycliques » et pour lesquelles le calcul du résultat de la requête est très efficace. En effet le temps d'exécution d'une telle requête sur une base de données quelconque est essentiellement proportionnel à la taille de la base de données : on dit que le temps est « linéaire » en la taille de la BD et on dira alors que la requête est « linéaire ». Cette linéarité est un point essentiel pour la rapidité de l'exécution d'une requête sur de très grosses bases de données. Il faut savoir que pour bien d'autres types de requêtes, on ne connaît pas de méthode algorithmique permettant d'en garantir l'exécution en temps moins que quadratique en la taille de la BD (voire pire), ce qui peut être très lent si cette taille est très grande.

Or il se trouve que, très récemment (résultat partiel en 1999 puis plus complet en 2004), on a identifié deux nouvelles classes de requêtes qui elles aussi sont « linéaires » (dans le sens précédent). Ces deux classes, notées Acyclique_ et Acyclique+, élargissent la classe des requêtes acycliques (notée classe Acyclique) en permettant d'utiliser, la première des inégalités _ entre attributs, la seconde des comparaisons <,>,_,_ entre attributs. Cela permet donc d'exprimer beaucoup plus de requêtes que les requêtes acycliques qui, elles, n'autorisent que des égalités entre attributs (ce qui correspond essentiellement à des jointures naturelles entre tables).

Dans cet exposé on expliquera ce que sont ces requêtes, les outils combinatoires et logiques permettant de les mettre en oeuvre en temps linéaire (en la taille de la base de données), ceci en se plaçant au départ dans un formalisme logique très comparable au calcul relationnel sur n-uplets (c'est-à-dire un formalisme très comparable à SQL).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr