Cette thèse a été soutenue le 17 janvier 2000.
Le but de notre recherche est d'aborder les problèmes de versions d'objets de grande taille dans les bases de données. Les images sont des objets de grande taille, faiblement structurés, qu'il est possible d'organiser par des structures telles que l'arbre quaternaire. En traitement d'images, les utilisateurs ont besoin de conserver différents états d'une même image, chaque état correspondant au résultat d'une opération ou d'une série d'opérations particulières sur l'image. Ces états peuvent être considérés comme des versions d'images. Nous proposons une structure, l'Arbre Quaternaire Générique, qui stocke des images similaires, la similarité étant définie par une distance entre les arbres quaternaires représentant les images. Deux images sont similaires si leurs arbres quaternaires diffèrent seulement sur un nombre relativement faible de noeuds. L'Arbre Quaternaire Générique minimise l'espace de stockage, par partage de parties communes entre images, et permet d'appliquer des opérations sur les images, comme la comparaison d'images, la comparaison d'une même région dans différentes images ou la mise à jour simultanée de différentes images.
Maude Manouvrier
sous la direction de Mme Geneviève Jomier
Equipe Bases de Données et Génie Logiciel
Laboratoire LAMSADE
Fichiers postcripts de la thèse
Les objets de grande taille, fortement structurés, se trouvent naturellement dans les SGBDOO, lors de la manipulation de racines de persistance (ensemble d'identificateurs d'objets), par exemple. Nos travaux permettent également de répondre aux problèmes de redondance lors du stockage des versions d'ensemble ou de collection d'objets. Ces objets de grande taille sont gérés le plus souvent à l'aide de structures d'index comme les arbres B+. Nous proposons des mécanismes de gestion de versions d'arbre B+ pour optimiser la gestion de versions de collection d'objets. Les mécanismes proposés dans cette thèse peuvent être généralisés aux structures d'index arborescentes en général, offrant par conséquent un large domaine d'applications couvrant en particulier les systèmes d'informations géographiques et les entrepôts de données.
Mots-clés :
Bases de données, structures d'index, objets de grande taille faiblement ou fortement structurés, versions, optimisation du stockage, similarité d'images, collections d'objets
Cette thèse est organisée en trois parties. La partie A présente en détail le cadre et la problématique de la thèse. Dans cette partie, le chapitre 1 présente les différents mécanismes de gestion des objets de grande taille dans les bases de données et décrit quelques approches de versionnement d'objets de grande taille. Le chapitre 2 présente l'approche des Versions de Bases de Données, sur laquelle se basent les propositions de cette thèse.
La partie B concerne la gestion des images similaires. L'application de traitement d'images, qui a été le point de départ de la proposition présentée dans cette partie de la thèse, est décrite dans le chapitre 3. Les images gérées par les utilisateurs de cette application sont organisées en arbre quaternaire. Le chapitre 4 présente cette structure, les différentes manières de l'implanter et plusieurs approches de compactage d'images similaires organisées en arbre quaternaire. Le chapitre 5 présente l'Arbre Quaternaire Générique. Le chapitre 6 compare cette structure aux autres travaux de recherche.
La partie C présente la généralisation des mécanismes proposés dans la partie B aux arbres B+ et aux arbres R. Dans cette partie, le chapitre 7 présente les structures d'Arbre B+ Générique et d'Arbre R Générique. Le chapitre 8 compare les autres approches avec les arbres génériques proposés dans la thèse.