October 1984 | TOMASZ IMIELIŃSKI AND WITOLD LIPSKI, JR.
This paper addresses the semantics of Codd's relational model of data, focusing on the conditions that must be satisfied to extend the usual relational operators (such as projection, selection, union, and join) to handle tables with "null values" of various kinds. The authors propose three practical systems for representing incomplete information in relational databases:
1. **Codd Tables**: These tables support projection and selection but cannot support both projection and join simultaneously. The system is based on Codd's null values (@) and is shown to be safe and complete.
2. **V-Tables**: These tables support projection, positive selection, union, join, and renaming of attributes, allowing for the processing of arbitrary conjunctive queries. They are based on tables with multiple ("marked") null values or variables and are designed to handle all relational operators on tables in the same way as with usual relations. However, they cannot support projection and arbitrary selection.
3. **Conditional Tables**: This system, mainly of theoretical interest, supports projection, selection, union, join, and renaming. It is based on conditional tables, which are V-tables with an additional column containing a condition. This system can also handle the difference operator under a closed world assumption.
The paper also discusses the theoretical underpinnings of these systems, including the concept of a representation system and the conditions that must be satisfied for a system to be semantically meaningful. The authors provide algorithms for evaluating selection over Codd tables and analyze the limitations of Biskup's approach, which is based on independent arguments for union and join. The paper concludes with a discussion of related work and future directions.This paper addresses the semantics of Codd's relational model of data, focusing on the conditions that must be satisfied to extend the usual relational operators (such as projection, selection, union, and join) to handle tables with "null values" of various kinds. The authors propose three practical systems for representing incomplete information in relational databases:
1. **Codd Tables**: These tables support projection and selection but cannot support both projection and join simultaneously. The system is based on Codd's null values (@) and is shown to be safe and complete.
2. **V-Tables**: These tables support projection, positive selection, union, join, and renaming of attributes, allowing for the processing of arbitrary conjunctive queries. They are based on tables with multiple ("marked") null values or variables and are designed to handle all relational operators on tables in the same way as with usual relations. However, they cannot support projection and arbitrary selection.
3. **Conditional Tables**: This system, mainly of theoretical interest, supports projection, selection, union, join, and renaming. It is based on conditional tables, which are V-tables with an additional column containing a condition. This system can also handle the difference operator under a closed world assumption.
The paper also discusses the theoretical underpinnings of these systems, including the concept of a representation system and the conditions that must be satisfied for a system to be semantically meaningful. The authors provide algorithms for evaluating selection over Codd tables and analyze the limitations of Biskup's approach, which is based on independent arguments for union and join. The paper concludes with a discussion of related work and future directions.