Incomplete Objects - A Data Model for Design and Planning Applications.

Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty: Incomplete Objects - A Data Model for Design and Planning Applications. SIGMOD Conference 1991: 288-297
  author    = {Tomasz Imielinski and
               Shamim A. Naqvi and
               Kumar V. Vadaparty},
  editor    = {James Clifford and
               Roger King},
  title     = {Incomplete Objects - A Data Model for Design and Planning Applications},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {288-297},
  ee        = {, db/conf/sigmod/ImielinskiNV91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP,}


We are motivated by applications within design, planning and scheduling areas, where current research appears to be focused on syntactic issues of performance and volume. We take a more semantic view of applications within these areas and discover several useful functionalities that are poorly supported. For example, facilities for handling incomplete specifications are quite inadequate. We introduce a notion of OR-objects and show that it captures incomplete specifications naturally. In particular, a database with OR-objects represents a set of possible worlds, e.g., a world for each design or schedule, and queries can either be evaluated in the "interpretations" of the database, or in the database itself. We formalize these notions of interpretations and hypothetical queries in an object-oriented setting, and provide a complexity characterization for our queries.

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

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 BibTeX , SIGMOD Record 20(2), June 1991

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 891 KB]


Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
Serge Abiteboul, Paris C. Kanellakis: Database Theory Column: Query Languages for Complex Object Databases. SIGACT News 21(3): 9-18(1990) BibTeX
François Bancilhon: Object-Oriented Database Systems. PODS 1988: 152-162 BibTeX
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
Catriel Beeri, Shamim A. Naqvi, Oded Shmueli, Shalom Tsur: Set Constructors in a Logic Database Language. J. Log. Program. 10(1/2/3&4): 181-232(1991) BibTeX
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
Tomasz Imielinski, Kumar V. Vadaparty: Complexity of Query Processing in Databases with OR-Objects. PODS 1989: 51-65 BibTeX
Barry E. Jacobs: On Database Logic. J. ACM 29(2): 310-332(1982) BibTeX
Christophe Lécluse, Philippe Richard, Fernando Vélez: O2, an Object-Oriented Data Model. SIGMOD Conference 1988: 424-433 BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

  1. Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki: Scalar Aggregation in FD-Inconsistent Databases. ICDT 2001: 39-53
  2. I-Min A. Chen, Richard Hull, Dennis McLeod: An Execution Model for Limited Ambiguity Rules and Its Application to Derived Data Update. ACM Trans. Database Syst. 20(4): 365-413(1995)
  3. Kumar V. Vadaparty, Shamim A. Naqvi: Using Constraints for Efficient Query Processing in Nondeterministic Databases. IEEE Trans. Knowl. Data Eng. 7(6): 850-864(1995)
  4. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
  5. Leonid Libkin: Normalizing Incomplete Databases. PODS 1995: 219-230
  6. Leonid Libkin: Approximation in Databases. ICDT 1995: 411-424
  7. Leonid Libkin: Query Language Primitives for Programming with Incomplete Databases. DBPL 1995: 6
  8. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  9. Alain Pirotte, Esteban Zimányi, David Massart, Tatiana Yakusheva: Materialization: A Powerful and Ubiquitous Abstraction Pattern. VLDB 1994: 630-641
  10. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  11. Leonid Libkin, Limsoon Wong: Semantic Representations and Query Languages for Or-sets. PODS 1993: 37-48
  12. Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:40:07 2009