Decidable containment of recursive queries

DOI10.1016/j.tcs.2004.10.031zbMath1101.68513OpenAlexW2144771279WikidataQ64360091 ScholiaQ64360091MaRDI QIDQ555766

Diego Calvanese, Giuseppe De Giacomo, Moshe Y. Vardi

Publication date: 10 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.031

zbMATH Keywords

DatalogQuery containmentRegular path queriesSemistructured data

Mathematics Subject Classification ID

Database theory (68P15) Data structures (68P05)

Related Items (4)

Regular queries on graph databases ⋮ Eliminating Recursion from Monadic Datalog Programs on Trees ⋮ A theoretical framework for knowledge-based entity resolution ⋮ Reasoning and Query Answering in Description Logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equivalence of recursive and nonrecursive Datalog programs
• The complexity of querying indefinite data about linearly ordered domains
• Alternating tree automata
• Data independent recursion in deductive databases
• Elementary induction on abstract structures
• Regular path queries with constraints
• Tree acceptors and some of their applications
• On the foundations of the universal relation model
• Horn clause queries and generalizations
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On conjunctive queries containing inequalities
• Equivalences Among Relational Expressions with the Union and Difference Operators
• Equivalence of Datalog queries is undecidable
• Equivalences among Relational Expressions
• Representing and reasoning on XML documents: a description logic approach
• Generalized finite automata theory with an application to a decision problem of second-order logic
• A medvedev characterization of sets recognized by generalized finite automata
• Answering queries using views: A survey

This page was built for publication: Decidable containment of recursive queries