Undecidable optimization problems for database logic programs

DOI10.1145/174130.174142MaRDI QIDQ3140022zbMATH OpenOpenAlexFDO

Authors Haim Gaifman, Yehoshua Sagiv, Moshe Y. Vardi, Harry G. Mairson

Publication date 6 December 1993

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/174130.174142

zbMATH Keywords

boundednessdataloglogic programmingoptimizationquery languagerecursionundecidability

Mathematics Subject Classification ID

Logic programming (68N17) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Undecidable boundedness problems for datalog programs
• Eliminating recursion from monadic datalog programs on trees
• Boundedness is undecidable for datalog programs with a single recursive rule
• Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
• About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs

Cited in

(36)

• Data independent recursion in deductive databases
• The functional dimension of inductive definitions
• OLDTNF-based evaluation method for handling recursive queries in deductive databases
• Bounded arity Datalog () queries on graphs
• Can datalog be approximated?
• A progression semantics for first-order logic programs
• Bounds in the propagation of selection into logic programs
• On the decidability of the termination problem of active database systems
• Generalization of ZYT-linearizability for bilinear datalog programs
• A tetrachotomy of ontology-mediated queries with a covering axiom
• Eliminating recursion from monadic datalog programs on trees
• Undecidability and intractability results concerning Datalog programs and their persistency numbers
• Undecidable boundedness problems for datalog programs
• Static analysis in Datalog extensions
• A simple characterization of uniform boundedness for a class of recursions
• scientific article; zbMATH DE number 517063 (Why is no real title available?)
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
• A datalog-based computational model for coordination-free, data-parallel systems
• Datalog and Its Extensions for Semantic Web Databases
• scientific article; zbMATH DE number 1926632 (Why is no real title available?)
• Characterizing boundedness in chase variants
• Guarded Ontology-Mediated Queries
• The dichotomy of evaluating homomorphism-closed queries on probabilistic graphs
• Boundedness of conjunctive regular path queries
• About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs
• Infinitary logic for computer science
• A Logical Approach to Constraint Satisfaction
• Querying data sources that export infinite sets of views
• Tie-breaking semantics and structural totality
• On the equivalence of recursive and nonrecursive Datalog programs
• Logical query optimization by proof-tree transformation
• Homogeneity and homogenizability: hard problems for the logic SNP
• When do homomorphism counts help in query algorithms?
• Adaptive query algorithms for relational structures based on homomorphism counts
• A more general theory of static approximations for conjunctive queries
• A semantic approach to optimize linear datalog programs

This page was built for publication: Undecidable optimization problems for database logic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140022)