Abstract FR:

Les objets spatiaux, de par leur complexite, ne peuvent en general pas etre decrits de facon extensive, mais seulement intensionnellement, ce qui pose de serieux problemes aux systemes de gestion de bases de donnees. De la qualite de la modelisation des donnees depend la facilite de leur manipulation et l'efficacite des techniques d'evaluation que l'on peut mettre en uvre. La representation des objets a l'aide de contraintes rend possible une modelisation en terme d'ensembles qui permet une manipulation au moyen d'operations habituelles comme celles de l'algebre relationnelle. L'evaluation des requetes sur les objets spatiaux a generalement une complexite exponentielle en la dimension des donnees, ce qui limite la portee pratique des systemes pour des dimensions elevees. On montre comment dans le cadre du modele contrainte, il est possible d'utiliser des criteres telles que la dimension, la geometrie et la topologie des donnees pour maitriser le cout d'evaluation des requetes. Pour reduire la complexite en une fonction lineaire en la dimension, on propose des techniques d'evaluation basees sur des approximations. On montre aussi comment reconnaitre dans la requete des blocs correspondant a des problemes connus de geometrie. Une evaluation efficace de la requete est alors obtenue en remplacant ces blocs par l'algorithme correspondant. Enfin, on montre comment repondre plus rapidement a des requetes topologiques a l'aide d'une structure finie appelee graphe topologique et des techniques de reecriture de formules. Pour finir, on valide concretement la portee pratique de l'approche par contraintes et des concepts developpes dans cette these a l'aide d'un prototype, dedale, dont on presente la conception et l'implantation.