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

这项跨学科研究是由加州大学圣克鲁斯分校的Phokion Kolaitis教授和莱斯大学的Moshe Vardi教授合作进行的。约束满足和联合查询评价分别是人工智能和数据库系统中普遍存在的两个基本问题。由于已知这些问题在最坏的情况下是难以计算的，人工智能和数据库系统的研究人员试图发现约束满足和联合查询评估的可处理情况，并设计启发式算法来解决这些问题。然而，到目前为止，这些研究基本上是并行进行的，两个领域之间很少或没有相互作用。最近的研究表明，约束满足和连接查询评价之间存在着紧密而精确的联系。该项目的主要目标是进一步探索约束满足和联合查询评估之间的联系，并检查为这些问题中的每个问题开发的技术对其他问题的适用性。为此，一个新的博弈论框架正在被开发，以统一看似不相关的结果，确定这两个问题的其他可处理的情况，并为一般情况设计启发式。此外，人工智能社区开发的算法和启发式正在评估其在联合查询评估中的有效性，反之亦然。本项目取得的成果将增强人工智能和数据库系统之间的交互，并将促进这两个领域之间的知识转移。

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.