An Efficient Method for Checking Object-Oriented Database Schema Correctness.
Anna Formica, Hans Dietmar Gröger, Michele Missikoff:
An Efficient Method for Checking Object-Oriented Database Schema Correctness.
ACM Trans. Database Syst. 23(3): 334-369(1998)@article{DBLP:journals/tods/FormicaGM98,
author = {Anna Formica and
Hans Dietmar Gr{\"o}ger and
Michele Missikoff},
title = {An Efficient Method for Checking Object-Oriented Database Schema
Correctness},
journal = {ACM Trans. Database Syst.},
volume = {23},
number = {3},
year = {1998},
pages = {334-369},
ee = {db/journals/tods/FormicaGM98.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Inheritance is introducted in object-oriented systems to enhance code reuse and create more compact and readable software. Powerful object models adopt multiple inheritance, allowing a type (or class) definition to inherit from more than one supertype. Unfortunately, in applying this powerful modeling mechanism, inheritance conflicts may be generated, which arise when the same property or operation is defined in more than one supertype. Inheritance conflicts identification and resolution is the key issue of this article. In strongly typed object-oriented systems the resolutioin of inheritance conflicts depends on the compatibility of the types of the conflicting definitions. In case of incompatible types, a contradiction arises. This article focuses on object-oriented databases (ODBs), providing a method aimed at supporting the designer in the construction of correct ODB schemas. The first necessary condition for schema correctness is the absence of contradictions. A second cause of schema incorrectness is due to the presence of structurally recursive types that, when defined within certain hierarchical patterns, cause the nontermination of the inheritance process. In the article, after the formal definition of a correct schema, two graph-theoretic methods aimed at verifying ODB schema correctness are analyzed. Although the first method is intuitive but inefficient, the second allows schema correctness to be checked in polynomial time, in the size of the schema. The results of this study are included in the implementation of Mosaico, an environment for ODB application design.
Copyright © 1998 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
[Abstract and Index Terms]
[Full Text in PDF Format, 255 KB]
References
- [Abadi and Cardelli 1996]
- ...
- [Agrawal and Gehani 1989]
- Rakesh Agrawal, Narain H. Gehani:
ODE (Object Database and Environment): The Language and the Data Model.
SIGMOD Conference 1989: 36-45 BibTeX
- [Ait-Kaci and Podelski 1993]
- Hassan Aït-Kaci, Andreas Podelski:
Towards a Meaning of LIFE.
J. Log. Program. 16(3): 195-234(1993) BibTeX
- [Albano et al. 1985]
- Antonio Albano, Luca Cardelli, Renzo Orsini:
Galileo: A Strongly-Typed, Interactive Conceptual Language.
ACM Trans. Database Syst. 10(2): 230-260(1985) BibTeX
- [Albano et al. 1995]
- Antonio Albano, Giorgio Ghelli, Renzo Orsini:
Fibonacci: A Programming Language for Object Databases.
VLDB J. 4(3): 403-444(1995) BibTeX
- [Amadio and Cardelli 1993]
- Roberto M. Amadio, Luca Cardelli:
Subtyping Recursive Types.
ACM Trans. Program. Lang. Syst. 15(4): 575-631(1993) BibTeX
- [Andrews and Harris 1987]
- Tim Andrews, Craig Harris:
Combining Language and Database Advances in an Object-Oriented Development Environment.
OOPSLA 1987: 430-440 BibTeX
- [Balsters et al. 1992]
- ...
- [Balsters and Fokkinga 1991]
- Herman Balsters, Maarten M. Fokkinga:
Subtyping Can Have a Simple Semantics.
Theor. Comput. Sci. 87(1): 81-96(1991) BibTeX
- [Banerjee et al. 1990]
- Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, Won Kim, Darrell Woelk, Nat Ballou, Hyoung-Joo Kim:
Data Model Issues for Object-Oriented Applications.
ACM Trans. Inf. Syst. 5(1): 3-26(1987) BibTeX
- [Beeri 1990]
- Catriel Beeri:
A Formal Approach to Object-Oriented Databases.
Data Knowl. Eng. 5: 353-382(1990) BibTeX
- [Borgida 1988]
- Alexander Borgida:
Modeling Class Hierarchies with Contradictions.
SIGMOD Conference 1988: 434-443 BibTeX
- [Bretl et al. 1989]
- Robert Bretl, David Maier, Allen Otis, D. Jason Penney, Bruce Schuchardt, Jacob Stein, E. Harold Williams, Monty Williams:
The GemStone Data Management System.
Object-Oriented Concepts, Databases, and Applications 1989: 283-308 BibTeX
- [Cardelli 1988]
- Luca Cardelli:
A Semantics of Multiple Inheritance.
Inf. Comput. 76(2/3): 138-164(1988) BibTeX
- [Cardelli and Wegner 1985]
- Luca Cardelli, Peter Wegner:
On Understanding Types, Data Abstraction, and Polymorphism.
ACM Comput. Surv. 17(4): 471-522(1985) BibTeX
- [Carpenter 1992]
- ...
- [Cattel and Barry 1997]
- ...
- [Cook and Palsberg 1989]
- William R. Cook, Jens Palsberg:
A Denotational Semantics of Inheritance and its Correctness.
OOPSLA 1989: 433-443 BibTeX
- [Cook et al. 1990]
- William R. Cook, Walter L. Hill, Peter S. Canning:
Inheritance Is Not Subtyping.
POPL 1990: 125-135 BibTeX
- [Formica and Missikoff 1994]
- Anna Formica, Michele Missikoff:
Correctness of ISA Hierarchies in Object-Oriented Database Schemas.
EDBT 1994: 231-244 BibTeX
- [Formica et al. 1997]
- Anna Formica, Hans Dietmar Gröger, Michele Missikoff:
Object-Oriented Database Schema Analysis and Inheritance Processing: A Graphtheoretic Approach.
Data Knowl. Eng. 24(2): 157-181(1997) BibTeX
- [Horowitz and Sahni 1983]
- Ellis Horowitz, Sartaj Sahni:
Fundamentals of Computer Algorithms.
Computer Science Press 1978
BibTeX
- [Khoshafian and Abnous 1990]
- ...
- [Khoshafian and Copeland 1986]
- Setrag Khoshafian, George P. Copeland:
Object Identity.
OOPSLA 1986: 406-416 BibTeX
- [Kifer and Lausen 1989]
- Michael Kifer, Georg Lausen:
F-Logic: A Higher-Order language for Reasoning about Objects, Inheritance, and Scheme.
SIGMOD Conference 1989: 134-146 BibTeX
- [Kim 1990a]
- Won Kim:
Introduction to Object-Oriented Databases.
MIT Press 1990, ISBN 0-262-11124-1
BibTeX
- [Kim 1990b]
- Won Kim:
Object-Oriented Databases: Definition and Research Directions.
IEEE Trans. Knowl. Data Eng. 2(3): 327-341(1990) BibTeX
- [Lecluse and Richard 1992]
- Christophe Lécluse, Philippe Richard:
The O2 Database Programming Language.
Building an Object-Oriented Database System, The Story of O2 1992: 195-214 BibTeX
- [Matthes and Schmidt 1993]
- ...
- [Missikoff and Toiati 1994a]
- Michele Missikoff, M. Toiati:
MOSAICO - A System for Conceptual Modeling and Rapid Prototyping of Object-Oriented Database Application.
SIGMOD Conference 1994: 508 BibTeX
- [Missikoff and Toiati 1994b]
- ...
- [Nebel 1991]
- ...
- [Versant 1991]
- ...
- [Yasukawa et al. 1992]
- Hideki Yasukawa, Hiroshi Tsuda, Kazumasa Yokota:
Objects, Properties, and Modules in QUIXOTE.
FGCS 1992: 257-268 BibTeX
- [Zicari 1992]
- Roberto Zicari:
A Framework for Schema Updates In An Object-Oriented Database System.
Building an Object-Oriented Database System, The Story of O2 1992: 146-182 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Wed Jun 4 19:23:48 2008