Notions of Dependency Satisfaction

Summary: Introduces two notions of dependency satisfaction—consistency (generalizes weak satisfaction; suits EGDs but conflicts with TGDs) and completeness (matches intuitive TGD semantics; awkward for EGDs)—framing them as alternative enforcement policies. Characterizes both via tableaux and first-order semantics, links their decision problems to dependency implication, and examines avoiding a universal relation scheme. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 625
Venue: PODS
Year: 1982
Pagerank: 6.482729e-05
Overall Rank: 4,843 | 66.78%
DOI: 10.1145/588111.588142

Incoming Non-self Citations Over Time

Authors

1. Marc H. Graham (Georgia Institute of Technology; University of Toronto)
2. Alberto O. Mendelzon (University of Toronto)

BibTeX Citation

@inproceedings{graham_pods82,
        address = {New York, NY, USA},
        series = {{PODS} '82},
        title = {{Notions of Dependency Satisfaction}},
        url = {https://dl.acm.org/doi/10.1145/588111.588142},
        doi = {10.1145/588111.588142},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Graham, Marc H. and Mendelzon, Alberto O.},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,659	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.5797982e-05
5,351	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	6.2533477e-05
6,153	Independent and Separable Database Schemes	1983	PODS	5.9569613e-05
7,132	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.694968e-05
9,260	The Revenge Of The Jd	1983	PODS	5.2970277e-05
13,193	On the Properties and Characterisation of Connection-trap-free Schemes (Extended Abstract)	1986	PODS	5.093636e-05
13,248	Inverting Relational Expressions - A Uniform And Natural Technique For Various Database Problems	1983	PODS	5.093636e-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
266	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00022823892
742	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00014426824
3,529	First Order Logic Formalization for Functional, Multivalued and Mutual Dependencies	1978	SIGMOD	7.3387532e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
2	12,404	Completeness of Queries over Incomplete Databases	2011	VLDB
3	3,461	Inference Rules for Functional and Inclusion Dependencies	1983	PODS
4	2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
5	3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
6	162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
7	1,277	Extending Dependencies with Conditions	2007	VLDB
8	8,506	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
9	4,659	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS
10	9,029	On the Satisfiability of Dependency Constraints in Entity-Relationship Schemata	1987	VLDB