Incomplete Information in Relational Databases

Tomasz Imielinski, Witold Lipski

Research output: Contribution to journalArticle

604 Citations (Scopus)

Abstract

This paper concerns the semantics of Codd's relational model of data. Formulated are precise conditions that should be satisfied m a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed. These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by usmg a specified subset [l of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in fl are in fact derivable in this system. Two such systems of practical interest are shown. The first, based on the usual Codd's null values, supports projection and selection. The second, based on many different (“marked”) null values or variables allowed to appear in a table, is shown to correctly support projection, posmve selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries. A very desirable property enjoyed by this system is that all relational operators on tables are performed in exactly the same way as in the case of the usual relations. A third system, mainly of theoretical interest, supporting projection, selection, union, join, and renaming, is also discussed. Under a so-called closed world assumption, it can also handle the operator of difference. It is based on a device called a condiUonal table and is crucial to the proof of the correctness of the second system. All systems considered allow for relational expressions contaming arbitrardy many different relation symbols, and no form of the universal relation assumption is required.

Original languageEnglish (US)
Pages (from-to)761-791
Number of pages31
JournalJournal of the ACM (JACM)
Volume31
Issue number4
DOIs
StatePublished - Sep 20 1984

Fingerprint

Semantics
Processing

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence
  • Information Systems
  • Control and Systems Engineering
  • Hardware and Architecture

Cite this

Imielinski, Tomasz ; Lipski, Witold. / Incomplete Information in Relational Databases. In: Journal of the ACM (JACM). 1984 ; Vol. 31, No. 4. pp. 761-791.
@article{e63a9c139fd945e0a70c55f1ab5d9034,
title = "Incomplete Information in Relational Databases",
abstract = "This paper concerns the semantics of Codd's relational model of data. Formulated are precise conditions that should be satisfied m a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed. These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by usmg a specified subset [l of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in fl are in fact derivable in this system. Two such systems of practical interest are shown. The first, based on the usual Codd's null values, supports projection and selection. The second, based on many different (“marked”) null values or variables allowed to appear in a table, is shown to correctly support projection, posmve selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries. A very desirable property enjoyed by this system is that all relational operators on tables are performed in exactly the same way as in the case of the usual relations. A third system, mainly of theoretical interest, supporting projection, selection, union, join, and renaming, is also discussed. Under a so-called closed world assumption, it can also handle the operator of difference. It is based on a device called a condiUonal table and is crucial to the proof of the correctness of the second system. All systems considered allow for relational expressions contaming arbitrardy many different relation symbols, and no form of the universal relation assumption is required.",
author = "Tomasz Imielinski and Witold Lipski",
year = "1984",
month = "9",
day = "20",
doi = "https://doi.org/10.1145/1634.1886",
language = "English (US)",
volume = "31",
pages = "761--791",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "4",

}

Incomplete Information in Relational Databases. / Imielinski, Tomasz; Lipski, Witold.

In: Journal of the ACM (JACM), Vol. 31, No. 4, 20.09.1984, p. 761-791.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Incomplete Information in Relational Databases

AU - Imielinski, Tomasz

AU - Lipski, Witold

PY - 1984/9/20

Y1 - 1984/9/20

N2 - This paper concerns the semantics of Codd's relational model of data. Formulated are precise conditions that should be satisfied m a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed. These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by usmg a specified subset [l of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in fl are in fact derivable in this system. Two such systems of practical interest are shown. The first, based on the usual Codd's null values, supports projection and selection. The second, based on many different (“marked”) null values or variables allowed to appear in a table, is shown to correctly support projection, posmve selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries. A very desirable property enjoyed by this system is that all relational operators on tables are performed in exactly the same way as in the case of the usual relations. A third system, mainly of theoretical interest, supporting projection, selection, union, join, and renaming, is also discussed. Under a so-called closed world assumption, it can also handle the operator of difference. It is based on a device called a condiUonal table and is crucial to the proof of the correctness of the second system. All systems considered allow for relational expressions contaming arbitrardy many different relation symbols, and no form of the universal relation assumption is required.

AB - This paper concerns the semantics of Codd's relational model of data. Formulated are precise conditions that should be satisfied m a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed. These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by usmg a specified subset [l of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in fl are in fact derivable in this system. Two such systems of practical interest are shown. The first, based on the usual Codd's null values, supports projection and selection. The second, based on many different (“marked”) null values or variables allowed to appear in a table, is shown to correctly support projection, posmve selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries. A very desirable property enjoyed by this system is that all relational operators on tables are performed in exactly the same way as in the case of the usual relations. A third system, mainly of theoretical interest, supporting projection, selection, union, join, and renaming, is also discussed. Under a so-called closed world assumption, it can also handle the operator of difference. It is based on a device called a condiUonal table and is crucial to the proof of the correctness of the second system. All systems considered allow for relational expressions contaming arbitrardy many different relation symbols, and no form of the universal relation assumption is required.

UR - http://www.scopus.com/inward/record.url?scp=0021513522&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021513522&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/1634.1886

DO - https://doi.org/10.1145/1634.1886

M3 - Article

VL - 31

SP - 761

EP - 791

JO - Journal of the ACM

JF - Journal of the ACM

SN - 0004-5411

IS - 4

ER -