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.00010804573
Overall Rank: 1,712 | 88.10%
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
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868
1,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
2,474	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7135761e-05
3,553	Compiling Separable Recursions	1988	SIGMOD	6.9779134e-05
4,370	Distributed Processing Of Logic Programs	1988	SIGMOD	6.2486359e-05
6,365	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.0945408e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
12,792	Combinatorial Games in Database Theory	1995	PODS	4.1945683e-05
12,826	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.1945683e-05
12,929	Factoring Augmented Regular Chain Programs	1990	VLDB	4.1945683e-05
12,981	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1945683e-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.0010066783
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
200	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00035012858
296	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028644922
365	On the Power of Magic	1987	PODS	0.00025585898
537	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.0002068591
1,545	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	0.0001144821

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,746	Binding Propagation in Disjunctive Databases	1998	VLDB	4.1945683e-05
843	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS	0.00016005595
4,136	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4188795e-05
3,435	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0966834e-05
4,141	Explicit Control of Logic Programs Through Rule Algebra	1988	PODS	6.4141369e-05
12,884	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS	4.1945683e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
5,102	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS	5.6992154e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8602644e-05