Collaborative Research: Constraint Satisfaction, Database Query Evaluation, and Information Integration

这项跨学科的研究是由加州大学圣克鲁斯分校的菲基恩·科莱蒂斯教授和赖斯大学的摩西·瓦迪教授合作进行的。约束满足和合取查询求值分别是人工智能和数据库系统中普遍存在的两个基本问题。由于已知这些问题在最坏的情况下在计算上很难处理，人工智能和数据库系统的研究人员试图发现约束满足和合取查询评估的容易处理的情况，并设计启发式算法来解决这些问题。然而，到目前为止，这些研究在很大程度上是并行进行的，两个领域之间的互动相对较少或没有。最近的研究工作已经证实，约束满足和合取查询评估之间存在着强烈而准确的联系。这个项目的主要目标是进一步探索约束满足和合取查询求值之间的联系，并检查为每个问题开发的技术对另一个问题的适用性。为此，正在开发一种新的博弈论框架，以统一看似无关的结果，确定这两个问题的更多容易处理的情况，并为一般情况设计启发式方法。此外，人工智能社区开发的算法和启发式正在就其在合取查询评估中的效率进行评估，反之亦然。在该项目过程中取得的成果将加强人工智能和数据库系统之间的互动，并将促进这两个领域之间的知识转让。

This interdisciplinary research is carried out in a collaboration between Professors Phokion Kolaitis at the University of California, Santa Cruz and Moshe Vardi at Rice University. Constraint satisfaction and conjunctive query evaluation are two fundamental and ubiquitous problems in artificial intelligence and database systems, respectively. Since these problems are known to be computationally intractable in the worst case, researchers in artificial intelligence and database systems have sought to discover tractable cases of constraint satisfaction and conjunctive query evaluation, as well as to design heuristic algorithms for solving these problems. Thus far, however, these studies have been largely carried out in parallel and with relatively little or no interaction between the two areas. Recent research work has established that there are strong and exact connections between constraint satisfaction and conjunctive query evaluation. The main goal of this project is to further explore the connections between constraint satisfaction and conjunctive query evaluation, and to examine the applicability of techniques developed for each of these problems to the other problem. To this effect, a novel game-theoretic framework is being developed to unify seemingly unrelated results, identify additional tractable cases of these two problems, and design heuristics for the general case. Moreover, algorithms and heuristics developed by the artificial intelligence community are being evaluated in regards to their efficacy in conjunctive query evaluation, and vice versa. Results obtained in the course of this project will enhance the interaction between artificial intelligence and database systems, and will advance knowledge transfer between these two areas.