| 部分赋值一阶逻辑公式的条件求值——NP完全性及在特定情况下的求解 |
| |
| 引用本文： | 潘久辉.部分赋值一阶逻辑公式的条件求值——NP完全性及在特定情况下的求解[J].中南大学学报(自然科学版),1989(2). |
| |
| 作者姓名： | 潘久辉 |
| |
| 作者单位： | 中南矿冶学院计算机科学系 |
| |
| 摘 要： | 部分赋值的一阶逻辑公式的条件求值问题是在关系数据库应用,尤其是在分布式环境下应用中经常遇到的问题。此问题在一般意义下的解是NP完全的。本文首先证明此问题的解存在的充要条件,从而推知其NP完全性。然后给出该问题在一种特定情况下的求解方法。
|
| 关 键 词： | 谓词逻辑 数据库 关系代数 |
THE CONDITIONAL EVALUATION OF FIRST ORDER LOGIC EXPRESSIONS PARTIALLY ASSIGNED--NP-COMPLETENESS AND THE SOLUTIONS IN SPECIAL SITUATIONS |
| |
| Pan Jiuhui.THE CONDITIONAL EVALUATION OF FIRST ORDER LOGIC EXPRESSIONS PARTIALLY ASSIGNED--NP-COMPLETENESS AND THE SOLUTIONS IN SPECIAL SITUATIONS[J].Journal of Central South University:Science and Technology,1989(2). |
| |
| Authors: | Pan Jiuhui |
| |
| Institution: | Pan Jiuhui Department of Computer Science |
| |
| Abstract: | The problem of conditional evaluation of first order logic expressions partially
assigned frequently occurs in the context of Relational Database Application,
especially in the environment of distributed databases. In general, the solution to
this problem is NP-complete.
This paper gives sufficient and necessary condition for the existence of the
solution to the problem, and thus shows its NP-completeness. And also, the
methods of solving the problem in some special situations are proposed. |
| |
| Keywords: | predicate logic database relational algebra |
| 本文献已被 CNKI 等数据库收录！ |
