Query Evaluation

自从np硬度理论诞生以来，计算机科学就不得不面对这样一个现实：许多令人感兴趣的计算问题不太可能在计算上易于处理。由于这些难题的实例需要在实践中处理和解决，因此很自然地寻求（此类问题的）在计算上可处理的有限案例，以期更好地理解可处理性和难处理性的来源。我们建议从这个角度来研究查询求值问题。查询求值（这里）被定义为以下问题：一个实例由一个公式和一个关系结构组成；任务是计算结构上公式的答案（或满意的赋值）。研究查询评估的动机源于这样一个事实，即这个问题在许多领域都很突出，例如数据库理论、现实世界问题建模和计算复杂性理论。在这里，我们的目标是理解各种公式的性质如何影响这项任务的复杂性：这个项目的一个关键目标是证明系统的复杂性分类定理，这些定理描述了一个逻辑，在这个任务上是可处理的公式的类别。除了证明分类定理外，我们还计划研究许多相关的研究问题，这些问题是由描述的动机自然产生的；这些问题涉及多种研究领域，包括图论、数据库理论和有限模型理论。例如，我们将努力理解可处理案例的性质，特别是可以解决它们的有效算法的类型。为了证明这样的分类定理，我们的目标是为公式开发复杂性度量，这将允许识别查询评估的可追溯性结果，就像图上树宽度的既定度量允许涉及图的问题的可追溯性结果一样。因此，这个目标可能在整个计算机科学中具有广泛和概念性的兴趣，因为它涉及找到分解比图更复杂的对象的方法。让我们注意到，在之前完成的研究中，树宽度本身已经被应用于测量和理解逻辑公式。有待开发的复杂性度量将潜在地构成树宽度的进一步有趣的概括，并且有可能与现有的丰富的树宽度理论相互作用和扩展。该项目范围内的成功研究将产生强大的学术影响，从而有能力改善数据库查询评估的最新实践。从本质上讲，该项目提出了一些基础问题，这些问题支持对数据库查询评估进行更深入和更丰富的理解，并重点关注其效率；这些研究问题由于理论观点的成熟而得以推进。因此，通过开发的技术的实现，有可能使查询评估更有效，在这里考虑的查询的基本类上，降低成本并允许行业中更高的功能。

Ever since the birth of the theory of NP-hardness,computer science has had to cope with the realizationthat many computational problems of interestare unlikely to be computationally tractable.As instances of such hard problems need to be coped with and solved in practice,it is natural to seek restricted cases (of such problems) that are computationally tractable, in hopes of better understandingthe sources of tractability and intractability.We propose to study the problemof query evaluation from this angle.Query evaluation is (here) defined to be the following problem:an instance consists ofa formula and a relational structure;the task is tocompute the answers (or satisfying assignments)to the formula over the structure.Motivations for studying query evaluation arise fromthe fact that this problem occurs prominently in many areas, such asdatabase theory, real-world problem modelling, andcomputational complexity theory.Here, we aim to understand how the nature of various formulas impacts the complexity of this task:a key aim of this project is to prove systematic complexityclassification theorems that describe, for a logic,the classes of formulas on which this task is tractable.In addition to proving classification theorems,we plan to study many associated research issues thatarise naturally from the described motivation;these issues relate to a diversity of research areas including graph theory,database theory, and finite model theory.For example, we will strive tounderstand the nature of the tractable cases, in particular,the types of efficient algorithms that can solve them.Towards proving such classification theorems,we aim to develop complexity measures for formulasthat will allow for the identification of tractability results for query evaluation,much as the established measure of treewidth on graphs allows for tractability resultsfor problems involving graphs.This objective may thus be of broad and conceptual interest throughout computer science, as it involvesfinding ways to decompose objects that are more complex thangraphs.Let us note that treewidth itselfhas already been applied to measure and understand logical formulasin previously completed research.The complexity measures to be developed will potentially constitutefurther interesting generalizations of treewidth, and there isthe potential for an interplay with and broadening ofthe existing rich theory of treewidth.Successful research in the scope of this project will have strong academic ramifications, which then have the abilityto improve state-of-the-art practice in database query evaluation.In essence, this project asks foundational questions that supporta much deeper and richer understanding of database query evaluation, and crucially focuses on its efficiency; these research issues can now be advanced due to the maturity of the theoretical point of view.Via implementations of the developed techniques,there is thus the potential to make query evaluation much more efficient, on the foundational classes of queries considered here, reducing costs and allowing for higher capabilities in the industry.