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.