Query Evaluation

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

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.