A Semantics for Complex Objects and Approximate Answers

Peter Buneman, Susan Davidson, Aaron Watters

Research output: Contribution to journalArticlepeer-review


A new definition of complex objects is introduced which provides a denotation for incomplete tuples as well as partially described sets. Set values are “sandwiched” between “complete” and “consistent” descriptions (respectively represented in the Smyth and Hoare powerdomains), allowing the maximal values to be arbitrary subsets of maximal elements in the domain of the space of descriptions. We then restrict our attention to complex objects which are in some sense “natural,” i.e., those which represent “views” of entity-relationship databases, and define rules over these objects. The rules can be used not only as an integrity check on the information in the database, but can be used constructively to infer consistent instances of conclusions and to refine complete instances of the hypothesis. The system is shown to extend the power of datalog (without negation) and the relational algebra (with set difference), and to have an efficient implementation.
Original languageEnglish
Pages (from-to)170-218
Number of pages49
JournalJournal of Computer and System Sciences
Issue number1
Publication statusPublished - 1 Aug 1991

Fingerprint Dive into the research topics of 'A Semantics for Complex Objects and Approximate Answers'. Together they form a unique fingerprint.

Cite this