The Implication And Finite Implication Problems For Typed Template Dependencies

Summary: Establishes undecidability of implication and finite implication for typed template dependencies (generalizing embedded MVDs and JDs), implying no formal axiomatization. Extends to simple template dependencies and exhibits a finite set with unsolvable implication. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 631
Venue: PODS
Year: 1982
Pagerank: 7.5526697e-05
Overall Rank: 3,291 | 77.43%
DOI: 10.1145/588111.588149

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi (Stanford University)

BibTeX Citation

@inproceedings{vardi_pods82,
        address = {New York, NY, USA},
        series = {{PODS} '82},
        title = {{THE IMPLICATION AND FINITE IMPLICATION PROBLEMS FOR TYPED TEMPLATE DEPENDENCIES}},
        url = {https://dl.acm.org/doi/10.1145/588111.588149},
        doi = {10.1145/588111.588149},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vardi, Moshe Y.},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,433	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.4181806e-05
3,461	Inference Rules for Functional and Inclusion Dependencies	1983	PODS	7.3938918e-05
4,210	The Inference Problem for Template Dependencies	1982	PODS	6.8314006e-05
6,987	Embedded Join Dependencies As A Tool For Decomposing Full Join Dependencies	1985	PODS	5.7303405e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
10	Extending the Data Base Relational Model to Capture More Meaning	1979	SIGMOD	0.0007727299
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
4,210	The Inference Problem for Template Dependencies	1982	PODS	6.8314006e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,277	Extending Dependencies with Conditions	2007	VLDB
2	1,491	Composition of Mappings Given by Embedded Dependencies	2005	PODS
3	203	Dependency Inference	1987	VLDB
4	162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
5	6,505	Inferences Involving Embedded Multivalued Dependencies and Transitive Dependencies	1980	SIGMOD
6	3,461	Inference Rules for Functional and Inclusion Dependencies	1983	PODS
7	13,259	A Theory Of Data Dependencies Over Relational Expressions	1982	PODS
8	2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
9	4,160	The Interaction between Functional Dependencies and Template Dependencies	1980	SIGMOD
10	4,210	The Inference Problem for Template Dependencies	1982	PODS