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: 708
Venue: PODS
Year: 1984
Pagerank: 6.5797982e-05
Overall Rank: 4,659 | 68.04%
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
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.2736086e-05
5,351	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	6.2533477e-05
13,134	Can Constant-time Maintainability Be More Practical?	1989	PODS	5.093636e-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
266	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00022823892
4,843	Notions of Dependency Satisfaction	1982	PODS	6.482729e-05
9,260	The Revenge Of The Jd	1983	PODS	5.2970277e-05

Semantically Similar Papers

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