Why Not Negation By Fixpoint?

Summary: Demonstrates that the natural fixpoint semantics for DATALOG with negation faces inherent complexity-theoretic barriers to efficient implementation. Introduces Inflationary DATALOG, an efficiently implementable negation semantics based on inflationary fixpoints. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 833
Venue: PODS
Year: 1988
Pagerank: 0.00020329959
Overall Rank: 551 | 96.17%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Phokion G. Kolaitis
2. Christos H. Papadimitriou

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
352	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00026299604
374	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00025286717
620	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00019005954
1,448	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011938045
2,515	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6128871e-05
3,767	Polynomial Time Query Processing in Temporal Deductive Databases	1990	PODS	6.7783966e-05
4,010	A Web Odyssey: from Codd to XML	2001	PODS	6.5351699e-05
4,141	Explicit Control of Logic Programs Through Rule Algebra	1988	PODS	6.4141369e-05
4,757	Stable Models and Non-Determinism in Logic Programs with Negation	1990	PODS	5.9434944e-05
5,705	Datalog Unchained	2021	PODS	5.3621239e-05
6,255	Queries are easier than you thought (probably)	1992	PODS	5.1367617e-05
7,173	CONSTRAINT QUERY LANGUAGES (preliminary report)	1990	PODS	4.8114568e-05
7,368	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	4.7507411e-05
12,910	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.1945683e-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
374	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00025286717

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,852	Negation and Minimality in Non-Horn Databases	1993	PODS	6.7017663e-05
2,907	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.933806e-05
14,196	On Negation in HiLog	1991	PODS	-
5,992	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2415551e-05
4,491	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS	6.1422281e-05
11,158	Generative Datalog with Stable Negation	2023	PODS	4.1945683e-05
12,833	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1945683e-05
4,298	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2885419e-05
3,251	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3215694e-05
5,063	Tie-Breaking Semantics and Structural Totality (Extended Abstract)	1992	PODS	5.7267485e-05