The Inference Problem for Template Dependencies

Summary: Template dependencies: integrity constraints stipulating that whenever tuples agree on certain attributes an additional agreeing tuple must exist. Proves implication/inference for template dependencies undecidable (no algorithm for logical consequence from a finite set), holds under both finite and unrestricted database semantics. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 631
Venue: PODS
Year: 1982
Pagerank: 7.1559646e-05
Overall Rank: 3,390 | 76.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yuri Gurevich
2. Harry R. Lewis

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,032	The Implication And Finite Implication Problems For Typed Template Dependencies	1982	PODS	9.7332616e-05
3,643	The Complexity of Data Exchange	2006	PODS	6.8862411e-05
6,033	Embedded Join Dependencies As A Tool For Decomposing Full Join Dependencies	1985	PODS	5.2415551e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,032	The Implication And Finite Implication Problems For Typed Template Dependencies	1982	PODS	9.7332616e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
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
8,269	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB	4.5455963e-05
13,059	A Theory Of Data Dependencies Over Relational Expressions	1982	PODS	4.1945683e-05
2,058	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.6585264e-05
1,954	Inference Rules for Functional and Inclusion Dependencies	1983	PODS	9.9639379e-05
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083101742
4,448	The Interaction between Functional Dependencies and Template Dependencies	1980	SIGMOD	6.1785017e-05
2,032	The Implication And Finite Implication Problems For Typed Template Dependencies	1982	PODS	9.7332616e-05