Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases

Summary: Bottom-up Magic Set-based evaluation for stratified deductive databases using Kerisit's weak consequence operator to compute a two-valued well-founded model of magic rules. Shows weak stratification can yield unsound/incomplete answers and introduces soft stratification to restore soundness and completeness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1283
Venue: PODS
Year: 2003
Pagerank: 4.1945683e-05
Overall Rank: 12,617 | 12.23%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Andreas Behrend

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
1,205	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.00013285448
1,423	Magic is Relevant	1990	SIGMOD	0.00012054867
1,979	Logic Programming as Constructivism: A Formalization and its Application to Databases	1989	PODS	9.8794371e-05
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05
7,075	Magic-sets Transformation in Nonrecursive Systems	1992	PODS	4.842703e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
365	On the Power of Magic	1987	PODS	0.00025585898
12,922	Backward chaining evaluation in stratified disjunctive theories	1990	PODS	4.1945683e-05
6,254	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.1368042e-05
2,544	Aggregation and Relevance in Deductive Databases	1991	VLDB	8.5730083e-05
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05
5,628	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.4030815e-05
3,283	Magic Conditions	1990	PODS	7.280826e-05
12,356	Query Evaluation with Soft-Key Constraints	2008	PODS	4.1945683e-05
1,381	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS	0.00012283951
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783