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.3149914e-05
Overall Rank: 4,251 | 70.46%
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,580	On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals	1992	PODS	8.5008376e-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
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,519	Complexity Aspects of Various Semantics for Disjunctive Databases	1993	PODS	5.0239231e-05
12,980	Computing Facts In Non-Horn Deductive Systems.	1988	VLDB	4.1905499e-05
3,855	Negation and Minimality in Non-Horn Databases	1993	PODS	6.6953111e-05
8,328	Negation as Failure for First-Order Queries (Extended Abstract)	1986	PODS	4.5392079e-05
3,739	Towards a Real Horn Clause Language	1988	VLDB	6.7979486e-05
2,715	Query Processing in Deductive Databases with Incomplete Information	1986	SIGMOD	8.2411079e-05
582	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019753367
14,182	The Complexity of Reusing and Modifying Rulebases	1992	PODS	-
3,856	Relational Specifications of Infinite Query Answers	1989	SIGMOD	6.6938945e-05
12,842	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1905499e-05