Query Evaluation

点击翻译按钮获取中文摘要

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.