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: 626
Venue: PODS
Year: 1982
Pagerank: 7.9051531e-05
Overall Rank: 2,918 | 79.71%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Marc H. Graham
2. Alberto O. Mendelzon

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,380	Independent and Separable Database Schemes	1983	PODS	7.1606467e-05
3,917	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.6328189e-05
5,841	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	5.3039672e-05
6,168	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.1716335e-05
9,013	The Revenge Of The Jd	1983	PODS	4.4096041e-05
12,995	On the Properties and Characterisation of Connection-trap-free Schemes (Extended Abstract)	1986	PODS	4.1945683e-05
13,049	Inverting Relational Expressions - A Uniform And Natural Technique For Various Database Problems	1983	PODS	4.1945683e-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
38	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00075110004
135	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00042421957
458	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00022657396
2,279	First Order Logic Formalization for Functional, Multivalued and Mutual Dependencies	1978	SIGMOD	9.1162095e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
12,209	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1945683e-05
1,954	Inference Rules for Functional and Inclusion Dependencies	1983	PODS	9.9639379e-05
2,058	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.6585264e-05
3,496	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.0397186e-05
104	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00048766186
1,401	Extending Dependencies with Conditions	2007	VLDB	0.00012187775
8,269	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB	4.5455963e-05
3,917	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.6328189e-05
8,871	On The Satisfiability Of Dependency Constraints In Entity-Relationship Schemata	1987	VLDB	4.431665e-05