On The Complexity And Axiomatizability Of Consistent Database States

Summary: Analyzes complexity and axiomatizability of consistency (existence of a weak universal instance) for a fixed dependency set Σ. Key dichotomy: embedded dependencies can make consistency non‑recursive and not finitely axiomatizable by any effective logic; only total dependencies yield P-time (possibly high-degree) decidability and finite axiomatization in fixpoint logic. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h5ced8d0cc246716a
Venue: PODS
Year: 1984
Pagerank: 6.4336287e-05
Overall Rank: 4,753 | 68.05%
DOI: 10.1145/588011.588052

Incoming Non-self Citations Over Time

Authors

1. Marc H. Graham (Georgia Institute of Technology)
2. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{graham_pods84,
        address = {New York, NY, USA},
        series = {{PODS} '84},
        title = {{ON THE COMPLEXITY AND AXIOMATIZABILITY OF CONSISTENT DATABASE STATES}},
        url = {https://dl.acm.org/doi/10.1145/588011.588052},
        doi = {10.1145/588011.588052},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Graham, Marc H. and Vardi, Moshe Y.},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
633	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015380574
2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.0893712e-05
5,480	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	6.1130394e-05
13,424	Can Constant-time Maintainability Be More Practical?	1989	PODS	4.9793485e-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
278	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00022313978
4,964	Notions of Dependency Satisfaction	1982	PODS	6.337274e-05
9,434	The Revenge Of The Jd	1983	PODS	5.1781766e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,465	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB
2	897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
3	159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
4	2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
5	33	Consistent Query Answers in Inconsistent Databases	1999	PODS
6	3,529	Inference Rules for Functional and Inclusion Dependencies	1983	PODS
7	5,480	Constant Time Maintenance or The Triumph of the fd.	1986	PODS
8	13,539	Path Expressions in Databases (Extended Abstract)	1983	PODS
9	12,501	Certain Query Answering in Partially Consistent Databases	2014	VLDB
10	8,674	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB