Eliminating recursion from monadic datalog programs on trees

DOI10.1007/978-3-662-48057-1_31MaRDI QIDQ2946356zbMATH OpenOpenAlexFDO

Authors Filip Mazowiecki, Joanna Ochremiak, Adam Witkowski

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.02444

Mathematics Subject Classification ID

Logic programming (68N17) Database theory (68P15)

Abstract: We study the problem of eliminating recursion from monadic datalog programs on trees with an infinite set of labels. We show that the boundedness problem, i.e., determining whether a datalog program is equivalent to some nonrecursive one is undecidable but the decidability is regained if the descendant relation is disallowed. Under similar restrictions we obtain decidability of the problem of equivalence to a given nonrecursive program. We investigate the connection between these two problems in more detail.

Recommendations

• On the equivalence of recursive and nonrecursive Datalog programs
• Monadic datalog and regular tree pattern queries
• Undecidable optimization problems for database logic programs
• Monadic datalog and regular tree pattern queries
• Undecidable boundedness problems for datalog programs

Cites work

• scientific article; zbMATH DE number 4147465 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• A simple characterization of uniform boundedness for a class of recursions
• Containment of monadic Datalog programs via bounded clique-width
• Data independent recursion in deductive databases
• Decidable containment of recursive queries
• Monadic Datalog Containment
• Monadic datalog and regular tree pattern queries
• Optimizing Conjunctive Queries over Trees Using Schema Information
• Undecidable boundedness problems for datalog programs
• Undecidable optimization problems for database logic programs

Cited in

(3)

• Monadic datalog and regular tree pattern queries
• Undecidable optimization problems for database logic programs
• Monadic datalog and regular tree pattern queries

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Eliminating recursion from monadic datalog programs on trees

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