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,182 | 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,926	Below and Above Why-Provenance for Datalog Queries	2024	PODS	4.1905499e-05
13,011	Adaptive Predicate Managers in Database Systems	1986	VLDB	4.1905499e-05
12,842	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1905499e-05
6,934	Database Updates in Logic Programming	1988	PODS	4.8878659e-05
6,695	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	4.9550839e-05
8,129	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5753896e-05
4,291	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2824978e-05
12,946	Declarative Expression of Deductive Database Updates	1989	PODS	4.1905499e-05
3,859	Constraints and Redundancy in Datalog	1992	PODS	6.6875648e-05
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05