Bounds on the Propagation of Selection into Logic Programs

Summary: Maps binary chain programs H to a CFL L(H) and proves a constant selection is propagatable iff L(H) is regular (hence decidable). Shows p(X,X) is propagatable iff L(H) is finite, links these cases to weak MSO(1-successor), monadic generalized spectra, and program–language equivalences. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 795
Venue: PODS
Year: 1987
Pagerank: 0.000101081
Overall Rank: 1,653 | 88.67%
DOI: 10.1145/28659.28683

Incoming Non-self Citations Over Time

Authors

1. Catriel Beeri (Hebrew University)
2. Paris Kanellakis (Brown University)
3. François Bancilhon (INRIA; Microelectronics And Technology Computer Corporation)
4. Raghu Ramakrishnan (Microelectronics And Technology Computer Corporation; University of Texas)

BibTeX Citation

@inproceedings{beeri_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{Bounds on the Propagation of Selection into Logic Programs}},
        url = {https://dl.acm.org/doi/10.1145/28659.28683},
        doi = {10.1145/28659.28683},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Beeri, Catriel and Kanellakis, Paris and Bancilhon, François and Ramakrishnan, Raghu},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814
992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012790174
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,629	Compiling Separable Recursions	1988	SIGMOD	7.2392728e-05
4,121	Distributed Processing Of Logic Programs	1988	SIGMOD	6.8889854e-05
6,948	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.7306589e-05
7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.5160399e-05
12,986	Combinatorial Games in Database Theory	1995	PODS	5.093636e-05
13,020	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	5.093636e-05
13,124	Factoring Augmented Regular Chain Programs	1990	VLDB	5.093636e-05
13,179	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
344	On the Power of Magic	1987	PODS	0.00020659405
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
1,957	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	9.4146943e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,939	Binding Propagation in Disjunctive Databases	1998	VLDB
2	1,419	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS
3	6,077	Safety of Datalog Queries over Infinite Databases	1989	PODS
4	3,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS
5	4,263	Explicit Control of Logic Programs Through Rule Algebra	1988	PODS
6	13,078	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS
7	4,615	Tools for Datalog Boundedness	1991	PODS
8	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
9	5,210	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS
10	7,549	Hard problems for simple logic programs	1990	SIGMOD