October 1984 | TOMASZ IMIELIŃSKI AND WITOLD LIPSKI, JR.
This paper addresses the semantics of Codd's relational model of data, focusing on extending relational operators (projection, selection, union, join) to handle tables with null values. The authors propose precise conditions for a semantically meaningful extension of these operators, ensuring safety (no incorrect conclusions) and completeness (all valid conclusions are derivable). Two practical systems are presented: one based on Codd's null values, supporting projection and selection, and another using "marked" null values or variables, supporting projection, positive selection, union, join, and renaming. The latter system allows processing arbitrary conjunctive queries and maintains the same behavior as standard relations. A third system, of theoretical interest, supports projection, selection, union, join, and renaming, and can handle the difference operator under a closed-world assumption. All systems allow for relational expressions with arbitrary relation symbols and do not rely on the universal relation assumption. The paper also discusses the limitations of these systems, such as the inability to support union or join with Codd tables. The authors emphasize the importance of defining relational operators on tables with nulls in a semantically correct way to ensure accurate query processing.This paper addresses the semantics of Codd's relational model of data, focusing on extending relational operators (projection, selection, union, join) to handle tables with null values. The authors propose precise conditions for a semantically meaningful extension of these operators, ensuring safety (no incorrect conclusions) and completeness (all valid conclusions are derivable). Two practical systems are presented: one based on Codd's null values, supporting projection and selection, and another using "marked" null values or variables, supporting projection, positive selection, union, join, and renaming. The latter system allows processing arbitrary conjunctive queries and maintains the same behavior as standard relations. A third system, of theoretical interest, supports projection, selection, union, join, and renaming, and can handle the difference operator under a closed-world assumption. All systems allow for relational expressions with arbitrary relation symbols and do not rely on the universal relation assumption. The paper also discusses the limitations of these systems, such as the inability to support union or join with Codd tables. The authors emphasize the importance of defining relational operators on tables with nulls in a semantically correct way to ensure accurate query processing.