On the equivalence of recursive and nonrecursive Datalog programs

DOI10.1006/jcss.1997.1452zbMath0864.68029OpenAlexW2069760772MaRDI QIDQ676421

Surajit Chaudhuri, Moshe Y. Vardi

Publication date: 18 March 1997

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

Full work available at URL: https://doi.org/10.1006/jcss.1997.1452

zbMATH Keywords

Datalog program

Mathematics Subject Classification ID

Database theory (68P15) Theory of programming languages (68N15)

Related Items (6)

On Monotonic Determinacy and Rewritability for Recursive Queries and Views ⋮ Bounded arity Datalog \((\neq)\) queries on graphs ⋮ Containment of conjunctive queries on annotated relations ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ Decidable containment of recursive queries ⋮ Unnamed Item

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equivalence of recursive and nonrecursive Datalog programs
• Logical query optimization by proof-tree transformation
• Recursively indefinite databases
• Recursive queries and context-free graph grammars
• Automata-theoretic techniques for modal logics of programs
• Parallel complexity of logical query programs
• Data independent recursion in deductive databases
• Computable queries for relational data bases
• Elementary induction on abstract structures
• Space-bounded reducibility among combinatorial problems
• Structure and complexity of relational queries
• Tree acceptors and some of their applications
• Undecidable boundedness problems for datalog programs
• Undecidable optimization problems for database logic programs
• Deciding Equivalence of Finite Tree Automata
• On the foundations of the universal relation model
• Horn clause queries and generalizations
• Relational queries computable in polynomial time
• Minimizing function-free recursive inference rules
• On the menbership problem for functional and multivalued dependencies in relational databases
• Equivalences Among Relational Expressions with the Union and Difference Operators
• Alternation
• The Complexity of Tree Automata and Logics of Programs
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Decidability of Second-Order Theories and Automata on Infinite Trees
• A medvedev characterization of sets recognized by generalized finite automata

This page was built for publication: On the equivalence of recursive and nonrecursive Datalog programs