Soutenance mémoire
Langages centrés données
Evolution des bases de données
On dit que l’Histoire commence avec l’invention de l’écriture qui a permis à l’homme de prendre conscience de la possibilité de produire et de conserver une substance immatérielle, d’abord des inventaires ou des registres, puis des histoires, pour arriver à ce que représente l’écriture aujourd’hui. De la même manière, on peut dire que l’invention de la tabulatrice en 1889 pourrait être vue dans quelque temps comme la fin du préinformatique et la naissance de l’ère du traitement automatique de l’information.
La tabulatrice a été inventée par Hermann Hollerith en 1889. Il s’agit d’une machine électromécanique qui utilise des cartes perforées capables de traiter des données statistiques . Hollerith utilisa les cartes perforées pour stocker des tableaux statistiques et inventa ainsi le premier support de données. Il fabriqua également une machine avec le principe suivant : une information est représentée par l’absence ou la présence d’un trou dans un support. Le trou est détecté mécaniquement et l’information est comptabilisée électriquement. La tabulatrice a eu un franc succès avec les résultats obtenus dans le cadre du recensement national de la population des États-Unis. En 1896, Hollerith fonda l’entreprise TMC qui deviendra IBM en 1924.
Le modèle le plus courant de cartes perforées contient 12 lignes et 80 colonnes. Un croisement entre une ligne et une colonne peut être perforé ou pas. La présence de trou correspond à une valeur pour une information. Les lignes de 0 à 9 représentent les chiffres de 0 à 9 et les lignes 11 et 12 permettent de représenter les lettres. Par exemple, la valeur d’une colonne qui a une perforation uniquement sur la ligne 1 est 1 et la valeur d’une colonne qui a deux perforations, l’une sur la ligne 1 et l’autre sur la ligne 12 est A. Les cartes perforées étaient souvent étiquetées par une description générale du contenu et par des étiquettes au niveau des champs d’informations ou des valeurs. Dans une carte perforée, ce n’est pas les données qui sont stockées, mais plutôt une représentation de ces données. A cette époque, le stockage et la représentation des données étaient indissociables.
Jusqu’au milieu des années cinquante, les ordinateurs servaient principalement à effectuer des calculs complexes et parfois, plus rarement, à traiter des informations encodées dans des fichiers . C’est l’apparition, en 1956, du premier disque dur, l’IBM 350, qui a fait prendre une nouvelle dimension à l’ordinateur. Il était dès lors possible, dans des conditions raisonnables, de collecter et de stocker des informations, de les consulter, de les modifier et de les traiter. C’est le premier germe semé dans ce que deviendra le champ des bases de données.
Jusqu’au début des années soixante, les informations étaient encodées et stockées sous forme d’enregistrements dans des fichiers. Ceci a fait rapidement apparaître certaines limitations qu’il fallait vite lever, parmi celles-ci :
— l’accès séquentiel aux enregistrements contenus dans un fichier ralentissait énormément la consultation d’informations ciblées;
— la modification et la gestion des enregistrements demandaient parfois des efforts fastidieux d’encodage et de programmation;
— les informations étaient encodées dans des formats spécifiques en lien étroit avec les programmes qui les utilisaient. Cela rendait très difficile la réutilisation des fichiers stockés par une autre application.
Dans les années soixante, émergea l’idée de séparer les données de leurs traitements et de concevoir des logiciels spécialisés dans la gestion des données. Ces systèmes sont désignés par le nom de systèmes de gestion de bases de données , la base de données étant le nom attribué aux collections d’informations. Les SGBD sont accompagnés de langages dédiés afin de recevoir les instructions de l’utilisateur et d’effectuer les tâches qui leur sont déléguées. Ces tâches sont :
— l’encodage et le stockage physique des données collectées;
— l’accès aux données via des opérations prédéfinies;
— la gestion des modifications de données;
— le partage de données entre différentes applications.
Les SGBD devaient également être une solution pour sortir de la vision séquentielle imposée par le stockage physique brut et pour mieux exprimer les liens qui peuvent exister entre les différents enregistrements d’une base de données. Cette quête, celle de l’expressivité d’une part, et de la distanciation vis-à vis de la représentation physique de l’autre, a guidé et guide encore aujourd’hui les concepteurs des SGBD.
Paradigme relationnel
En 1970, Codd a défini le modèle relationnel et l’algèbre qui lui est associée [Codd, 1970]. C’est un modèle où les enregistrements sont organisés en relations homogènes. L’algèbre définit des opérateurs ensemblistes simples. Cette innovation a facilité significativement l’interaction avec les SGBD. Le travail de Codd est considéré comme fondateur dans le domaine des bases de données. En 1974, Sequel [Chamberlin et Boyce, 1974], l’ancêtre de SQL, un langage proche de la langue naturelle anglaise, qui permet de manipuler des bases de données relationnelles, a été présenté par Chamberlin et Boyce. Depuis, les SGBD relationnels utilisant SQL sont de loin les plus répandus.
Une des caractéristiques principales du modèle relationnel est qu’il est en première forme normale (1NF), c’est à dire que les valeurs des attributs dans les tuples doivent toutes être atomiques [Codd, 1971]. En 1977, Makinouchi considère la norme 1NF comme trop restrictive et propose un modèle où la valeur associée à un attribut peut être un ensemble d’ensembles [Makinouchi, 1977]. Le paradigme relationnel est au coeur de tous les paradigmes qui sont apparus après lui. Tous étendent le modèle et les opérateurs relationnels ou les utilisent.
Paradigmes imbriqués et paradigme objet
Dans les années quatre-vingt, de nombreux modèles de données, où les valeurs peuvent être elles-mêmes des relations, sont proposés. Bancilhon [Bancilhon et al., 1982] propose une approche qui permet de traiter des relations non-normalisées en s’intéressant à l’optimisation des opérateurs unaires. [Abiteboul et Bidoit, 1986] et [Scholl et al., 1989] présentent le système Verso qui manipule un modèle où les valeurs peuvent être des relations. Ils utilisent pour cela une représentation interne en forme d’arbre. Dans [Van Gucht et Fischer, 1988], les auteurs présentent un modèle avec des relations imbriquées à plusieurs niveaux et étendent l’algèbre relationnelle avec les opérateurs Nest et Unnest qui proposent un système permettant de restructurer les relations et de passer de 1NF à non-1NF et inversement.
En 1990, Colby a présenté une approche basée sur des identifiants [Colby, 1990]. Cluet et Moerkotte [Cluet et Moerkotte, 1993] ont généralisé l’idée et ont proposé des bases de données Objet qui permettent de manipuler des objets identifiés (pointeurs) au travers de méthodes définies par l’utilisateur. D’un point de vue théorique, ces modèles sont proches, c’est la mise en oeuvre qui diffère d’une approche à l’autre. Il est à noter également que la grande majorité des projets dont sont issus ces travaux n’ont pas eu un grand succès dans le monde réel à cause de la domination du modèle relationnel dans le monde applicatif.
Paradigmes semi-structurés
Dans les années quatre-vingt-dix, et avec la démocratisation du Web, des représentations de données semi-structurées voient le jour, notamment le standard XML. Ces paradigmes permettent d’intégrer des données hétérogènes. Ils reposent sur le paradigme imbriqué. Nous nous étendrons pas sur ces paradigmes que nous jugeons inutiles à la compréhension de notre travail de recherche.
NoSQL
Depuis les années deux mille, avec l’apparition du Web 2.0, des applications modernes (notamment les réseaux sociaux et le e-commerce) et du cloud computing, les données ont pris une nouvelle dimension. Elle sont un élément central dans la révolution technologique et sociétale de ces deux dernières décennies. Cette révolution a engendré de nouveaux besoins et donc de nouveaux défis. L’apparition ou la « réhabilitation » de certains formats (modèles) de données (JSON, XML, RDF et graphes) et les langages/systèmes permettant de les manipuler (MongoDB, XQuery, Sparql et Cypher) sont une des réponses à ces défis. Ces langages et systèmes modernes sont regroupés sous le terme NoSQL (Not only SQL). Les langages NoSQL reprennent les opérateurs de NRA et en introduisent de nouveaux selon le modèle de données auquel ils sont appliqués. Les modèles de données NoSQL sont basés sur le modèle imbriqué avec de nouveaux types de valeurs et de données. Nous avons l’intuition, d’un point de vue théorique, que tous ces langages peuvent être représentés, à un certain niveau d’abstraction, par un langage imbriqué extensible qui s’applique à un modèle imbriqué suffisamment générique pour représenter les différents modèles NoSQL.
|
Table des matières
INTRODUCTION
Première partie : Contexte
I Langages centrés données
I.1 Evolution des bases de données
I.1.1 Paradigme navigationnel
I.1.2 Paradigme relationnel
I.1.3 Paradigmes imbriqués et paradigme objet
I.1.4 Paradigmes semi-structurés
I.1.5 NoSQL
I.2 L’algèbre relationnelle (RA)
I.2.1 Le modèle relationnel
I.2.2 Les opérateurs relationnels
I.3 Le langage SQL
I.3.1 Modèle de données de SQL
I.3.2 Le langage d’interrogation des données
I.3.3 Spécificités de SQL
I.3.3.1 Les valeurs nulles
I.3.3.2 Les requêtes corrélées
I.4 L’algèbre imbriquée (NRA)
I.4.1 Modèle de données
I.4.2 Les opérateurs de NRA
I.5 Comparaison entre RA, SQL et NRA
I.6 Conclusion
II Compilation certifiée en Coq
II.1 Méthodes formelles
II.2 Assistants de preuve
II.2.1 Coq
II.3 Compilation certifiée correcte
II.3.1 Définitions
II.3.1.1 Compilation
II.3.1.2 Encodage et décodage
II.3.1.3 Mécanisation d’un langage
II.3.1.4 Compilateur algébrique
II.3.2 Correction d’un compilateur algébrique
II.3.2.1 Encodage et Décodage isomorphiques
II.3.2.2 Encodage homomorphique
II.3.2.3 Décodage homomorphique
II.3.3 Compilation certifiée en Coq d’un langage jouet
II.3.3.1 Le langage ToyExp
II.3.3.2 Instanciations de ToyExp
II.3.3.3 Définition et certification de ToyExpCert
II.3.3.4 Instanciation du compilateur ToyExpCert
II.4 Conclusion
III Formalisation de SQL et de NRA
III.1 SqlCert
III.1.1 Présentation de SqlCert
III.1.2 SQLAlg : Une extension de RA pour SQL
III.1.2.1 Représentation des données
III.1.2.2 Syntaxe
III.1.2.3 Exemples de requêtes
III.1.2.4 Les environnements de SQLAlg
III.1.2.5 Sémantique
Sémantique des expressions sans agrégats
Sémantique des expressions avec agrégats
Sémantique des formules
Sémantique des requêtes
III.1.2.6 Preuve de concept : Une instance de la spécification
III.2 Q*Cert
III.2.1 Présentation de Q*Cert
III.2.2 NRAe
III.2.2.1 Représentation des données
III.2.2.2 Syntaxe de NRAe
III.2.2.3 Sémantique de NRAe
III.3 Conclusion
Deuxième partie : Contribution
IV De SQLAlg vers NRAe
IV.1 Objectifs et présentation de la méthodologie
IV.1.1 Objectifs de la traduction
IV.1.2 Présentation générale de la traduction
IV.2 Encodage du modèle de données
IV.2.1 Encodage des valeurs
IV.2.2 Encodage des noms d’attributs
IV.2.3 Encodage de la logique trivaluée
IV.2.4 Encodage des tuples
IV.2.5 Encodage des collections
IV.2.6 Récapitulatif de l’encodage des données
IV.3 Encodage des instances de bases de données
IV.4 Encodage et gestion des environnements
IV.5 La traduction de SQLAlg
IV.5.1 Les expressions
IV.5.1.1 Expressions simples
IV.5.1.2 Expressions complexes
IV.5.1.3 Listes d’expressions nommées
IV.5.2 Les formules
IV.5.2.1 Symboles de prédicat
IV.5.2.2 Opérateurs NRAe de la logique trivaluée
IV.5.3 Les requêtes
IV.5.4 Exemple de traduction
IV.6 Réalisation des spécifications
IV.6.1 Les valeurs nulles
IV.6.2 Valeurs de la logique trivaluée
IV.6.3 Les symboles de fonction
IV.6.4 Les symboles d’agrégat
IV.6.5 Les symboles de prédicat et les opérateurs logiques
IV.7 Théorèmes de correction de la traduction
IV.8 Conclusion
Troisième partie : Discussion
V Discussion
V.1 Cas d’application : DBCert
V.1.1 Présentation de DBCert
V.1.2 Préservation de la sémantique
V.1.3 Exemple
V.1.4 Évaluation de DBCert
V.1.4.1 AlaSQL
V.1.4.2 Benchmarks
V.1.4.3 Résultats
V.1.4.4 Performances
V.2 Travaux connexes
CONCLUSION
