ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Type Systems for Querying Class Hierarchies with Non-strict Inheritance.

Alexander Borgida: Type Systems for Querying Class Hierarchies with Non-strict Inheritance. PODS 1989: 394-400
@inproceedings{DBLP:conf/pods/Borgida89,
  author    = {Alexander Borgida},
  title     = {Type Systems for Querying Class Hierarchies with Non-strict Inheritance},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {394-400},
  ee        = {http://doi.acm.org/10.1145/73721.73759, db/conf/pods/Borgida89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Type checking at query compilation time is important for both detecting programmer errors and reducing the running time of queries. We have argued elsewhere [2] that entity-based data management systems which support class hierarchies, such as semantic data models and object-oriented dbms, should not be confined to have "strict inheritance" - i.e., they should permit contradictions between class specifications, albeit in an explicit and controlled way. In this paper we present a type system for queries manipulating objects in such classes. We provide sound and complete axiomatizations of the predications "delta is a subtype of tau" and "expression e has type tau". The absence of strict inheritance has normally been felt to preclude effective type checking. We show that the problem is co-NP-hard when disjoint types are admitted in the schema, but present a low-order polynomial-time algorithm that determines the absence of type errors in a query when the database has only entities.

Copyright © 1989 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
Antonio Albano, Luca Cardelli, Renzo Orsini: Galileo: A Strongly-Typed, Interactive Conceptual Language. ACM Trans. Database Syst. 10(2): 230-260(1985) BibTeX
[2]
Alexander Borgida: Modeling Class Hierarchies with Contradictions. SIGMOD Conference 1988: 434-443 BibTeX
[3]
...
[4]
...
[5]
William F. Dowling, Jean H. Gallier: Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae. J. Log. Program. 1(3): 267-284(1984) BibTeX
[6]
David W. Etherington, Raymond Reiter: On Inheritance Hierarchies With Exceptions. AAAI 1983: 104-108 BibTeX
[7]
John Mylopoulos, Philip A. Bernstein, Harry K. T. Wong: A Language Facility for Designing Database-Intensive Applications. ACM Trans. Database Syst. 5(2): 185-207(1980) BibTeX
[8]
...
[9]
Vaughan R. Pratt: A Near-Optimal Method for Reasoning about Action. J. Comput. Syst. Sci. 20(2): 231-254(1980) BibTeX
[10]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
[11]
Mitchell Wand: Complete Type Inference for Simple Objects. LICS 1987: 37-44 BibTeX
[12]
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. Eric Amiel, Marie-Jo Bellosta, Eric Dujardin, Eric Simon: Type-safe Relaxing of Schema Consistency Rules for Flexible Modeling in OODBMS. VLDB J. 5(2): 133-155(1996)
  2. Eric Amiel, Marie-Jo Bellosta, Eric Dujardin, Eric Simon: Supporting Exceptions to Schema Consistency to Ease Schema Evolution in OODBMS. VLDB 1994: 108-119
  3. Edward P. F. Chan: Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992: 202-211
  4. Catriel Beeri, Tova Milo: Subtyping in OODB's. PODS 1991: 300-314
  5. Serge Abiteboul, Paris C. Kanellakis, Emmanuel Waller: Method Schemas. PODS 1990: 16-27
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:58 2009