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: 873
Venue: PODS
Year: 1989
Pagerank: 6.1548494e-05
Overall Rank: 5,594 | 61.63%
DOI: 10.1145/73721.73750

Incoming Non-self Citations Over Time

Authors

1. Anthony J. Bonner (Rutgers University)

BibTeX Citation

@inproceedings{bonner_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Hypothetical Datalog: Negation and Linear Recursion}},
        url = {https://dl.acm.org/doi/10.1145/73721.73750},
        doi = {10.1145/73721.73750},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bonner, Anthony J.},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,563	Complexity Aspects of Various Semantics for Disjunctive Databases	1993	PODS
2	13,167	Computing Facts in Non-Horn Deductive Systems	1988	VLDB
3	5,964	Negation and Minimality in Non-Horn Databases	1993	PODS
4	8,566	Negation as Failure for First-Order Queries (Extended Abstract)	1986	PODS
5	4,072	Towards a Real Horn Clause Language	1988	VLDB
6	3,512	Query Processing in Deductive Databases with Incomplete Information	1986	SIGMOD
7	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
8	14,368	The Complexity of Reusing and Modifying Rulebases	1992	PODS
9	4,235	Relational Specifications of Infinite Query Answers	1989	SIGMOD
10	13,027	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS