Undecidable optimization problems for database logic programs
Undecidable optimization problems for database logic programs
复制标题
数据库逻辑程序的不可判定优化问题
DOI：
10.1145/174130.174142
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Moshe Y. Vardi
中科院分区：
文献类型：
--
作者：
H. Gaifman;Harry G. Mairson;Y. Sagiv;Moshe Y. Vardi
DataLog是逻辑程序的语言，如果可以从数据库中使用，则可以从数据库中进行查询。确定给定的数据编程是否可以绑定，即使对于线性程序也是不可识别的（即，每个规则最多包含递归谓词的程序）。如果Datalog程序是稳定的，则是不可行的，这是不乏味的，并且包含此作品的较早版本，该版本在第二届IEEE逻辑I〜Z计算机科学研讨会（ITHACA）的会议记录中出现在相同的标题下。纽约，1987年，第106-115页。在这里报告的大多数研究是在H. Gaifman访问SRI International的AI中心的，他希望承认。他还希望感谢IBM Watson Research Center和IBM Almaden Research Center在1989年夏天完成了本文的结论，此处报告的研究部分是在H. Mairson的计算机科学部门完成的。斯坦福大学，并得到了海军研究办公室（ONR）合同NOO014-85-C-0731的支持牛津大学。在这里报告的研究是在Y. Sagiv访问斯坦福大学的计算机科学系，并得到了AT＆T基金会的赠款，IBM Corporation和National Science Foundation（NSF） -12791。布兰代斯大学，马萨诸塞州沃尔瑟姆，02254;为直接商业优势制作或分发。否则要复制或重新发布的计算机，需要费用和/或特定的许可。 1993年7月。第683-713页H. Gaifman等人。 1S不同于Logspace和NC）相同的属性与线性程序相等的属性以及在Logspace中的属性和在NC中的属性
Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program F’, then t’ is said to be bounded. It is shown that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs (i.e., programs in which each rule contains at most one occurrence of a recursive predicate). It is then shown that every semantic property of Datalog programs is undecidable if it is stable, is strongly nontrivial, and contains An earlier version of this work appeared under the same title in the Proceedings of the 2nd IEEE Symposium on Logic i~z Computer Science (Ithaca, N.Y.). IEEE, New York, 1987, pp. 106-115. Most of the research reported here was done while H. Gaifman was visiting the AI Center of SRI International whose support he wishes to acknowledge. He also wishes to thank IBM Watson Research Center and IBM Almaden Research Center for support in the summer of 1989, when the concluding work on this paper was done. The research reported here was done partly while H. Mairson was at the Computer Science Department of Stanford University and was supported by the Office of Naval Research (ONR) contract NOO014-85-C-0731 and partly while he was at the Programming Research Group of Oxford University. The research reported here was done while Y. Sagiv was visiting the Computer Science Department of Stanford University and was supported by a grant of AT & T Foundation, a grant of IBM Corporation and the National Science Foundation (NSF) grant 1ST 84-12791. Authors’ addresses: H. Gaifman and Y. Sagiv, Hebrew University, Jerusalem 91904, Israel; H. Mairson, Department of Computer Science, Brandeis University, Waltham, MA 02254; M. Y. Vardi, IBM Almaden Research Center, K53-802, 650 Harry Road, San Jose, CA 95120-6099. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage. the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 01993 ACM 0004-5411/93/0700-0683 $01.50 Journal of the Awxmt]on for Computing Machinery, VO1 40, No 3. July 1993. PP 683-713 684 H. GAIFMAN ET AL. boundedness. In particular, the property of being first-order 1s undecidable and (assuming that PTIME 1s different from LOGSPACE and from NC) the same holds for the property of being equivalent to a linear program and for the properties of being in LOGSPACE and of being in NC