On the Equivalence of Recursive and Nonrecursive Datalog Programs
作者:
Highlights:
•
摘要
We study the problem of determining whether a given recursive Datalog program is equivalent to a given nonrecursive Datalog program. Since nonrecursive Datalog programs are equivalent to unions of conjunctive queries, we study also the problem of determining whether a given recursive Datalog program is contained in a union of conjunctive queries. For this problem, we prove doubly exponential upper and lower time bounds. For the equivalence problem, we prove triply exponential upper and lower time bounds.
论文关键词:
论文评审过程:Received 8 May 1996, Available online 25 May 2002.
论文官网地址:https://doi.org/10.1006/jcss.1997.1452