Théorie des bases de données
En informatique, la théorie des bases de données englobe un vaste ensemble de sujets relatifs aux études et recherches dans le domaine théorique des bases de données et de leur systèmes de gestion.
Domaines d'étude modifier
Les aspects théoriques de la gestion des bases de données incluent entre autres les fondements des langages de requêtes, la complexité, la puissance d'expression des requêtes[1], la théorie des modèles finis, le contrôle de dépendance, les fondements du contrôle de concurrence, la sauvegarde et restauration, les bases de données temporelles, déductives (en), spatiales, probabilistes (en), la gestion de données incertaines (en), et les données du Web.
Les travaux sont basés traditionnellement sur le modèle relationnel, car ce modèle est considéré généralement comme le plus simple et le plus fondamental. Par extension ou généralisation, on obtient des résultats qui correspondent à d'autres modèles de données, comme les modèles orientés objet ou semi-structurés (en), ou des modèles de données en graphes et le langage XML.
Un thème central de la théorie des bases de données est de comprendre la complexité et la puissance d'expression des langages de requête[2] et leur connexion avec la logique. Les points de départ sont l'algèbre relationnelle et la logique du premier ordre qui, par le théorème de Codd, sont équivalents. Dans ce cadre, des requêtes importantes comme l'accessibilité dans les graphes ne peuvent pas être exprimées ; des langages plus puissants basés sur la programmation logique, tels que datalog, ont été étudiés. Un autre sujet d'intérêt concerne les fondements de l'optimisation de requêtes et de l'intégration de données. Dans ce domaine, les études portent surtout sur les requêtes conjonctives (en) qui admettent une optimisation même sous contraintes, en utilisant l'algorithme de Chase (en).
Les conférences scientifiques principales dans ce domaine sont le ACM Symposium on Principles of Database Systems (PODS) et la International Conference on Database Theory (ICDT).
Notes et références modifier
- Evgeny Dantsin, Thomas Eiter, Georg Gottlob, et Andrei Voronkov, « Complexity and expressive power of logic programming », ACM Comput. Surv., vol. 33, no 3, 2001, p. 374-425.
- Schweikardt, Schwentick et Segoufin 2009.
Bibliographie modifier
- Serge Abiteboul, Richard B. Hull et Victor Vianu, Foundations of Databases, Addison-Wesley, (ISBN 0-201-53771-0, lire en ligne).
- Jacky Akoka et Isabelle Comyn-Wattiau, Conception des bases de données relationnelles en pratique, Vuibert 2001.
- Hector Garcia-Molina, Jeffrey D. Ullman et Jennifer Widom, Database Systems : The Complete Book, Prentice Hall : Pearson education international, , 1203 p. (ISBN 978-0-13-187325-4).
- Nicole Schweikardt, Thomas Schwentick et Luc Segoufin, chap. 19 « Database Theory: Query Languages », dans Mikhail J. Atallah et Marina Blanton (éditeurs), Algorithms and Theory of Computation Handbook, vol. 2, Chapman & Hall/CRC, , 2e éd. (ISBN 978-1584888185).
