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.00020309855
Overall Rank: 552 | 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
353	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00026275228
375	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00025262028
618	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00018990567
1,450	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011926567
2,520	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6044305e-05
3,776	Polynomial Time Query Processing in Temporal Deductive Databases	1990	PODS	6.7716942e-05
4,014	A Web Odyssey: from Codd to XML	2001	PODS	6.5300582e-05
4,145	Explicit Control of Logic Programs Through Rule Algebra	1988	PODS	6.4076785e-05
4,754	Stable Models and Non-Determinism in Logic Programs with Negation	1990	PODS	5.9377721e-05
5,716	Datalog Unchained	2021	PODS	5.3569788e-05
6,254	Queries are easier than you thought (probably)	1992	PODS	5.1318451e-05
7,174	CONSTRAINT QUERY LANGUAGES (preliminary report)	1990	PODS	4.8068344e-05
7,363	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	4.7461604e-05
12,920	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.1905499e-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
375	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00025262028

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,855	Negation and Minimality in Non-Horn Databases	1993	PODS	6.6953111e-05
2,912	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.9261665e-05
14,210	On Negation in HiLog	1991	PODS	-
5,996	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2365238e-05
4,494	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS	6.1363251e-05
11,161	Generative Datalog with Stable Negation	2023	PODS	4.1905499e-05
12,842	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1905499e-05
4,291	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2824978e-05
3,256	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3135363e-05
5,058	Tie-Breaking Semantics and Structural Totality (Extended Abstract)	1992	PODS	5.7212391e-05