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: h5bf724bed2dbb833
Venue: PODS
Year: 1982
Pagerank: 6.337274e-05
Overall Rank: 4,964 | 66.63%
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,753	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.4336287e-05
5,480	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	6.1130394e-05
6,281	Independent and Separable Database Schemes	1983	PODS	5.8238839e-05
7,279	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.5671882e-05
9,434	The Revenge Of The Jd	1983	PODS	5.1781766e-05
13,483	On the Properties and Characterisation of Connection-trap-free Schemes (Extended Abstract)	1986	PODS	4.9793485e-05
13,538	Inverting Relational Expressions - A Uniform And Natural Technique For Various Database Problems	1983	PODS	4.9793485e-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
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045899672
278	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00022313978
769	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00014104125
3,602	First Order Logic Formalization for Functional, Multivalued and Mutual Dependencies	1978	SIGMOD	7.1740999e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,549	A Theory Of Data Dependencies Over Relational Expressions	1982	PODS
2	12,695	Completeness of Queries over Incomplete Databases	2011	VLDB
3	3,529	Inference Rules for Functional and Inclusion Dependencies	1983	PODS
4	2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
5	3,807	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
6	159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
7	1,291	Extending Dependencies with Conditions	2007	VLDB
8	8,674	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
9	4,753	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS
10	9,198	On the Satisfiability of Dependency Constraints in Entity-Relationship Schemata	1987	VLDB