An alternating fixpoint tailored to magic programs

Summary: Identifies mismatch between well-founded models of Datalog programs with negation (possibly non-2-valued) and their magic-set rewritings using common left-to-right SIPS, causing query-driven WF model divergence. Proposes a novel, natural tailoring of Van Gelder's alternating fixpoint to magic programs to restore agreement and enable correct query-directed evaluation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h53bedf21d0cdc093
Venue: PODS
Year: 1993
Pagerank: 5.6906839e-05
Overall Rank: 6,749 | 54.63%
DOI: 10.1145/153850.153861

Incoming Non-self Citations Over Time

Authors

1. Shinichi Morishita (IBM; International Business Machines Tokyo Research Laboratory; Stanford University)

BibTeX Citation

@inproceedings{morishita_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{An alternating fixpoint tailored to magic programs}},
        url = {https://dl.acm.org/doi/10.1145/153850.153861},
        doi = {10.1145/153850.153861},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Morishita, Shinichi},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,484	Design and Implementation of the Glue-Nail Database System	1993	SIGMOD	7.265089e-05
13,322	XSB as an Efficient Deductive Database Engine	1994	SIGMOD	4.9793485e-05
13,339	Query Evaluation under the Well Founded Semantics (Extended Abstract)	1993	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
352	On the Power of Magic	1987	PODS	0.00020223279
1,325	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.00011009279
1,556	Unfounded Sets and Well-Founded Semantics for General Logic Programs	1988	PODS	0.00010267435
1,744	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS	9.7353228e-05
2,076	A Procedural Semantics for Well Founded Negation in Logic Programs	1989	PODS	9.0786404e-05
3,484	Design and Implementation of the Glue-Nail Database System	1993	SIGMOD	7.265089e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,225	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD
2	7,599	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS
3	18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
4	5,861	Tie-Breaking Semantics and Structural Totality (Extended Abstract)	1992	PODS
5	13,280	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS
6	4,425	Magic Counting Methods	1987	SIGMOD
7	10,159	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB
8	1,744	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS
9	3,364	Magic Conditions	1990	PODS
10	1,325	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS