Dependency Satisfaction in Databases with Incomplete Information

Summary: Unified treatment of query evaluation and dependency satisfaction under incomplete information. Introduces a correct complete relational algebra and a chase to enforce functional and full-join dependencies on null-valued data, generalizing prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7821
Venue: VLDB
Year: 1984
Pagerank: 7.1534069e-05
Overall Rank: 3,750 | 74.28%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Gösta Grahne (University of Helsinki)

BibTeX Citation

@article{grahne_vldb84,
        title = {{Dependency Satisfaction in Databases with Incomplete Information}},
        author = {Grahne, Gösta},
        journal = {PVLDB},
        series = {{VLDB} '84},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
947	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00013041389
1,162	Principles of Dataspace Systems	2006	PODS	0.00011866011
2,402	Update Semantics for Incomplete Databases	1985	VLDB	8.6276184e-05
2,514	From Complete to Incomplete Information and Back	2007	SIGMOD	8.4818577e-05
2,904	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	7.9757931e-05
3,476	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.3807586e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
602	On the Semantics of Updates in Databases	1983	PODS	0.00015856828
1,380	Null Values in Data Base Management: A Denotational Semantics Approach	1979	SIGMOD	0.00010965714
4,115	Incomplete Information and Dependencies in Relational Databases	1983	SIGMOD	6.8936288e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,617	Relative Information Completeness	2009	PODS
2	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
3	495	A Complete Axiomatization For Functional And Multivalued Dependencies In Database Relations	1977	SIGMOD
4	2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
5	6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD
6	13,151	Partition Semantics For Incomplete Information In Relational Databases	1988	SIGMOD
7	12,404	Completeness of Queries over Incomplete Databases	2011	VLDB
8	40	Testing Implications Of Data Dependencies	1979	SIGMOD
9	14,459	Completeness Information and Its Application to Query Processing	1986	VLDB
10	4,115	Incomplete Information and Dependencies in Relational Databases	1983	SIGMOD