On the decidability of containment of recursive datalog queries - preliminary report
Piero A. Bonatti · 2004
The problem of deciding query containment has important applications in classical query optimization and heterogeneous database systems. Query containment is undecidable for unrestricted recursive queries, and decidable for recursive monadic queries and conjunctive queries over regular path expressions. In this paper, we identify a new class of recursive queries with decidable containment. Our framework extends the aforementioned query classes by supporting recursive predicates with more than two arguments and nonlinear recursion.