Bounds in the propagation of selection into logic programs

DOI10.1016/0022-0000(90)90035-JzbMath0796.68054OpenAlexW1975063966MaRDI QIDQ1813949

Catriel Beeri, Raghu Ramakrishnan, Paris C. Kanellakis, François Bancilhon

Publication date: 25 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(90)90035-j

zbMATH Keywords

optimizationcontext-free languagelogic programsprogram equivalencechain programsdatabase programsfirst-order expressibilityrecursive Horn clause programsselection propagation

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45) Logic programming (68N17) General topics in the theory of software (68N01)

Related Items (11)

Linearisability on Datalog programs ⋮ A data structure for arc insertion and regular path finding ⋮ Bounded arity Datalog \((\neq)\) queries on graphs ⋮ About boundedness for some datalog and DATALOGneg programs ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ A note on fixpoint techniques in data base recursive logic programs ⋮ The pushdown method to optimize chain logic programs ⋮ Inherent complexity of recursive queries ⋮ Compilation and evaluation of linear mutual recursions ⋮ GRAMMARS AND AUTOMATA TO OPTIMIZE CHAIN LOGIC QUERIES ⋮ Regular path queries with constraints

Cites Work

• Unnamed Item
• Parallel complexity of logical query programs
• Elementary induction on abstract structures
• Structure and complexity of relational queries
• The unsolvability of the equality problem for sentential forms of context-free grammars
• Undecidable optimization problems for database logic programs
• Weak Second‐Order Arithmetic and Finite Automata
• Reachability is harder for directed than for undirected finite graphs
• Implementation of logical query languages for databases
• Horn clause queries and generalizations
• On compiling queries in recursive first-order databases
• Decision Problems of Finite Automata Design and Related Arithmetics
• Contributions to the Theory of Logic Programming
• Monadic generalized spectra
• Generalized finite automata theory with an application to a decision problem of second-order logic

This page was built for publication: Bounds in the propagation of selection into logic programs