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: 992
Venue: PODS
Year: 1993
Pagerank: 5.8212982e-05
Overall Rank: 6,620 | 54.59%
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,430	Design and Implementation of the Glue-Nail Database System	1993	SIGMOD	7.4202634e-05
13,032	XSB as an Efficient Deductive Database Engine	1994	SIGMOD	5.093636e-05
13,049	Query Evaluation under the Well Founded Semantics (Extended Abstract)	1993	PODS	5.093636e-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
344	On the Power of Magic	1987	PODS	0.00020659405
1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.0001126031
1,522	Unfounded Sets and Well-Founded Semantics for General Logic Programs	1988	PODS	0.00010502706
1,714	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS	9.9404301e-05
2,028	A Procedural Semantics for Well Founded Negation in Logic Programs	1989	PODS	9.285972e-05
3,430	Design and Implementation of the Glue-Nail Database System	1993	SIGMOD	7.4202634e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,079	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD
2	7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS
3	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
4	5,735	Tie-Breaking Semantics and Structural Totality (Extended Abstract)	1992	PODS
5	12,990	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS
6	4,337	Magic Counting Methods	1987	SIGMOD
7	9,981	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB
8	1,714	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS
9	3,307	Magic Conditions	1990	PODS
10	1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS