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: 709
Venue: PODS
Year: 1984
Pagerank: 6.6328189e-05
Overall Rank: 3,917 | 72.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Marc H. Graham
2. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
537	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.0002068591
2,769	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.1450304e-05
5,841	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	5.3039672e-05
12,939	Can Constant-time Maintainability Be More Practical?	1989	PODS	4.1945683e-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
135	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00042421957
2,918	Notions of Dependency Satisfaction	1982	PODS	7.9051531e-05
9,013	The Revenge Of The Jd	1983	PODS	4.4096041e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,744	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.957936e-05
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
104	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00048766186
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
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
5,841	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	5.3039672e-05
13,050	Path Expressions in Databases (Extended Abstract)	1983	PODS	4.1945683e-05
12,012	Certain Query Answering in Partially Consistent Databases	2014	VLDB	4.1945683e-05
8,269	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB	4.5455963e-05