On Relational Algebra With Marked Nulls

Summary: Defines necessary and sufficient conditions for extending relational algebra to tables with marked nulls, enabling recursive computation of the "true tuples" of a query result following the expression structure. Proves these conditions match prior axioms and shows the simple "naive" semantics (treat nulls as ordinary values) is correct for projection, positive selection, union, natural join and renaming, coinciding with Reiter's proof-theoretic response. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 698
Venue: PODS
Year: 1984
Pagerank: 6.9453392e-05
Overall Rank: 4,032 | 72.34%
DOI: 10.1145/588011.588040

Incoming Non-self Citations Over Time

Authors

1. Witold Lipski, Jr. (Polish Academy of Sciences; University of Paris)

BibTeX Citation

@inproceedings{jr_pods84,
        address = {New York, NY, USA},
        series = {{PODS} '84},
        title = {{ON RELATIONAL ALGEBRA WITH MARKED NULLS}},
        url = {https://dl.acm.org/doi/10.1145/588011.588040},
        doi = {10.1145/588011.588040},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Witold Lipski, Jr.},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,245	Certain Answers Meet Zero-One Laws	2018	PODS	6.3012734e-05
5,378	Troubles with Nulls, Views from the Users	2022	VLDB	6.2406439e-05
5,677	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	6.1248899e-05
8,837	Coping with Incomplete Data: Recent Advances	2020	PODS	5.3596619e-05
9,225	Queries with Arithmetic on Incomplete Databases	2020	PODS	5.3035385e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4,115	Incomplete Information and Dependencies in Relational Databases	1983	SIGMOD	6.8936288e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,677	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS
2	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
3	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
4	6,852	When is Naive Evaluation Possible?	2013	PODS
5	1,928	Relations with Relation Names as Arguments: Algebra and Calculus	1992	PODS
6	1,380	Null Values in Data Base Management: A Denotational Semantics Approach	1979	SIGMOD
7	3,733	Closed World Databases Opened Through Null Values	1988	VLDB
8	3,925	A Formal Semantics of SQL Queries, Its Validation, and Applications	2018	VLDB
9	613	Database Relations with Null Values (Extended Abstract)	1982	PODS
10	13,152	A Sound and Complete Query Evaluation Algorithm for Relational Databases with Null Values	1988	SIGMOD