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: 796
Venue: PODS
Year: 1987
Pagerank: 0.00011058643
Overall Rank: 1,636 | 88.64%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
276	Regular Path Queries with Constraints	1997	PODS	0.00029365217
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121
1,687	Automata Theory for Database Theoreticians	1989	PODS	0.0001090256
2,473	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7048914e-05
3,556	Compiling Separable Recursions	1988	SIGMOD	6.9712392e-05
4,367	Distributed Processing Of Logic Programs	1988	SIGMOD	6.2423944e-05
6,363	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.0896537e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
12,801	Combinatorial Games in Database Theory	1995	PODS	4.1905499e-05
12,835	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.1905499e-05
12,939	Factoring Augmented Regular Chain Programs	1990	VLDB	4.1905499e-05
12,992	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1905499e-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.00099936325
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
173	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038731283
209	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00034147258
299	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028555103
359	On the Power of Magic	1987	PODS	0.00025830228
541	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00020586706
1,532	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	0.00011466849

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,755	Binding Propagation in Disjunctive Databases	1998	VLDB	4.1905499e-05
839	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS	0.00015989602
4,138	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4127061e-05
3,440	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0897313e-05
4,145	Explicit Control of Logic Programs Through Rule Algebra	1988	PODS	6.4076785e-05
12,894	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS	4.1905499e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
5,102	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS	5.6936517e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8555836e-05