A Database Interface for Complex Objects
The MIT Press eBooks · 1994
We describe a formal design for a logical query language using -terms as data structures to interact effectively and efficiently with a relational database.The structure of -terms provides an adequate representation for so-called complex objects.They generalize conventional terms used in logic programming: they are typed attributed structures, ordered thanks to a subtype ordering.Unification of -terms is an effective means for integrating multiple inheritance and partial information into a deduction process.We define a compact database representation for -terms, representing part of the subtyping relation in the database as well.We describe a retrieval algorithm based on an abstract interpretation of the -term unification process and prove its formal correctness.This algorithm is efficient in that it incrementally retrieves only additional facts that are actually needed by a query, and never retrieves the same fact twice. R ésum éNous décrivons la conception formelle d'un langage de requêtes logiques utilisant lestermes comme structure de données pour interagir effectivement and efficacement avec une base de données relationnelle.La structure des -termes fournit une représentation adéquate pour les objets soi-disant complexes.Ils généralisent les termes conventionnels utilisés en programmation logique: ce sont des structures typées et attribuées, ordonnées grâce à un ordre de sous-types.L'unification des -termes est un moyen effectif d'intégrer héritage multiple et information partielle dans un processus de déduction.Nous définissons une représentation compacte en base de données pour les -termes, representant aussi une partie de l'ordre sur les types dans la base de données.Nous décrivons un algorithme d'extraction de données basé sur l'interprétation abstraite de l'unification des -termes et prouvons sa correction formelle.Cet algorithme est efficace en ce sens qu'il extraie de façon incrémentale seuls les faits supplémentaires qui sont nécéssaires à une requête, et jamais deux fois le même fait.