Edinburgh Research Explorer

A Semantics for Complex Objects and Approximate Answers

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions



  • Download as Adobe PDF

    Rights statement: Elsevier Open Archive paper

    Final published version, 2.51 MB, PDF document

Original languageEnglish
Pages (from-to)170-218
Number of pages49
JournalJournal of Computer and System Sciences
Issue number1
Publication statusPublished - 1 Aug 1991


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.

Download statistics

No data available

ID: 10624802