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: 1282
Venue: PODS
Year: 2003
Pagerank: 5.093636e-05
Overall Rank: 12,810 | 12.12%
DOI: 10.1145/773153.773164

Incoming Non-self Citations Over Time

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

Authors

1. Andreas Behrend (University of Bonn)

BibTeX Citation

@inproceedings{behrend_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases}},
        url = {https://dl.acm.org/doi/10.1145/773153.773164},
        doi = {10.1145/773153.773164},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Behrend, Andreas},
        year = {2003}
}

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.00060089598
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.0001126031
1,410	Magic is Relevant	1990	SIGMOD	0.00010853223
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
2,474	Logic Programming as Constructivism: A Formalization and its Application to Databases	1989	PODS	8.5305658e-05
7,131	Magic-sets Transformation in Nonrecursive Systems	1992	PODS	5.694968e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	344	On the Power of Magic	1987	PODS
2	13,117	Backward chaining evaluation in stratified disjunctive theories	1990	PODS
3	6,008	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
4	2,511	Aggregation and Relevance in Deductive Databases	1991	VLDB
5	1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
6	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
7	3,307	Magic Conditions	1990	PODS
8	12,549	Query Evaluation with Soft-Key Constraints	2008	PODS
9	1,714	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS
10	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS