Incomplete Information and Dependencies in Relational Databases

Summary: Incomplete-information relational databases mix null-valued data with dependencies; chase converts dependencies into a null-based form. With arbitrary implicational dependencies, the transformation is not fully equivalent, and info corruption evades detection under projection, positive selection, union, join, and renaming; also studies view-dependency effects. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2283
Venue: SIGMOD
Year: 1983
Pagerank: 6.8936288e-05
Overall Rank: 4,115 | 71.77%
DOI: 10.1145/582192.582222

Incoming Non-self Citations Over Time

Authors

1. Tomasz Imielinski (McGill University)
2. Witold Lipski, Jr. (Polish Academy of Sciences)

BibTeX Citation

@inproceedings{imielinski_sigmod83,
        title = {{Incomplete Information and Dependencies in Relational Databases}},
        author = {Imielinski, Tomasz and Witold Lipski, Jr.},
        series = {{SIGMOD} '83},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582192.582222},
        url = {https://dl.acm.org/doi/10.1145/582192.582222},
        year = {1983}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,402	Update Semantics for Incomplete Databases	1985	VLDB	8.6276184e-05
2,904	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	7.9757931e-05
3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.1534069e-05
4,032	On Relational Algebra With Marked Nulls	1984	PODS	6.9453392e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
13,248	Inverting Relational Expressions - A Uniform And Natural Technique For Various Database Problems	1983	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,353	Chase Termination for Guarded Existential Rules	2015	PODS
2	2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS
3	1,537	Assumptions in Relational Database Theory	1982	PODS
4	13,233	On Lossless Transformation of Database Schemes Not Necessarily Satisfying Universal Instance Assumption (preliminary version)	1984	PODS
5	5,617	Relative Information Completeness	2009	PODS
6	9,259	Querying Weak Instances	1984	PODS
7	13,151	Partition Semantics For Incomplete Information In Relational Databases	1988	SIGMOD
8	14,459	Completeness Information and Its Application to Query Processing	1986	VLDB
9	40	Testing Implications Of Data Dependencies	1979	SIGMOD
10	3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB