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).