Hypothetical Datalog: Negation and Linear Recursion

Summary: Extends Horn-clause logic with hypothetical rule additions and stratification alternating negation-as-failure and linear recursion. Proves k-stratum rulebases are data-complete for Σ_k^P and exactly characterize relational queries in Σ_k^P without requiring a domain order. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 874
Venue: PODS
Year: 1989
Pagerank: 6.3212356e-05
Overall Rank: 4,255 | 70.40%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Anthony J. Bonner

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,578	On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals	1992	PODS	8.5091045e-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
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,522	Complexity Aspects of Various Semantics for Disjunctive Databases	1993	PODS	5.0287573e-05
12,970	Computing Facts In Non-Horn Deductive Systems.	1988	VLDB	4.1945683e-05
3,852	Negation and Minimality in Non-Horn Databases	1993	PODS	6.7017663e-05
8,335	Negation as Failure for First-Order Queries (Extended Abstract)	1986	PODS	4.5435639e-05
3,738	Towards a Real Horn Clause Language	1988	VLDB	6.8032471e-05
2,712	Query Processing in Deductive Databases with Incomplete Information	1986	SIGMOD	8.2488274e-05
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
14,168	The Complexity of Reusing and Modifying Rulebases	1992	PODS	-
3,853	Relational Specifications of Infinite Query Answers	1989	SIGMOD	6.7004022e-05
12,833	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1945683e-05