The Complexity of Reusing and Modifying Rulebases

Summary: Adds predicate substitution to deductive databases to enable reuse and incremental modification of rulebases by substituting predicates (not just variables) during query evaluation. Proves Datalog with substitution is EXPTIME-complete in data complexity and provides proof/model-theory and fixpoint semantics, characterizing the language's extra expressive power. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 977
Venue: PODS
Year: 1992
Pagerank: -
Overall Rank: 14,168 | 1.44%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Anthony J. Bonner

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,922	Below and Above Why-Provenance for Datalog Queries	2024	PODS	4.1945683e-05
13,000	Adaptive Predicate Managers in Database Systems	1986	VLDB	4.1945683e-05
12,833	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1945683e-05
6,932	Database Updates in Logic Programming	1988	PODS	4.8925595e-05
6,693	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	4.9598818e-05
8,125	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5797807e-05
4,298	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2885419e-05
12,936	Declarative Expression of Deductive Database Updates	1989	PODS	4.1945683e-05
3,857	Constraints and Redundancy in Datalog	1992	PODS	6.6939005e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05