The Second-Order Approach and its Application to View-Based Query Processing

在该项目中，将研究一种基于逻辑的知识处理方法，在这里称为二阶方法。其思想是，表达性表示语言一方面可以以一种非常自然的方式表述应用程序，但另一方面，可以通过简化为更适合计算的较差语言来处理。这种简化之所以成为可能，是因为在特定的应用程序上下文中使用了表达性语言结构。这种方法的概念证明已经在90年代末通过使用二阶量词消去来计算边界，以及最近在描述逻辑中的均匀插值（可以表示为二阶量词消去）的应用。该方法通常允许从应用领域追溯概念到逻辑的基本概念，指出新的应用可能性以及能够实现技术转移和组合的领域之间的相似之处。该项目连接了将相互促进的两条工作线：(1)特定应用领域的概念，基于视图的查询处理，将使用二阶运算符正式建模。(2)将开发计算方法，在形式化的基础上，主要通过消除二阶算子来实现应用。基于视图的查询处理的基本思想是翻译和分解查询，以便具有专门知识库和处理能力的多个代理可以参与答案计算。基于视图的查询处理与可定义性密切相关，是一个通用的逻辑概念，非常适合该项目的方法。关于基于视图的查询处理，项目的中心目标是所涉及概念的语义澄清、二阶运算符消除的可用性以计算查询转换，以及数据库以外的泛化。在计算方法方面，将开发基于命题逻辑的二阶算子消除新技术——与最近的SAT预处理器相关，基于一阶逻辑，并考虑到基于视图的查询处理中出现的特定公式模式。项目的结果应该作为适合二阶方法的大量进一步应用程序的详细的、正式的和自动化的基础。例如，这些包括非标准推理的变体、溯因推理、知识库的模块化、非单调推理和关于知识的推理。

In the project, an approach to logic-based knowledge processing, to be called here second-order approach, will be investigated. The idea is that expressive representation languages are, on the one hand, available to formulate applications in a very natural way, but on the other hand, are processed by reduction to poorer languages that are better suited for computation. Such reductions are made possible because the expressive language constructs are used in specific application contexts.Proofs of concept for this approach have been given in the late 90s with the use of second-order quantifier elimination for computing circumscription, and recently with applications of uniform interpolation (which can be expressed as second-order quantifier elimination) in description logics. The approach typically allows to trace concepts from the application area back to fundamental concepts of logic, indicating new application possibilities and parallels between areas that enable transfer and combination of techniques.The project connects two lines of work that will stimulate each other: (1) Concepts of a particular application area, view-based query processing, will be formally modeled with second-order operators. (2) Computational methods will be developed that realize applications, on the basis of the formalization, essentially by elimination of second-order operators.The basic idea of view-based query processing is to translate and decompose queries such that multiple agents with specialized knowledge bases and processing capabilities can contribute to answer computation. By its is close relation to definability, a general concept of logic, view-based query processing is well suited to the approach of the project. Central objectives of the project with respect to view-based query processing are semantic clarification of the involved concepts, availability of second-order operator elimination to compute query transformations, and generalization beyond databases.With respect to computational methods, new techniques for second-order operator elimination will be developed, based on propositional logic - related to recent SAT preprocessors, based on first-order logic, and by taking specific formula patterns into account that occur in view-based query processing.The results of the project should serve as an elaborate formal and automated foundation for a multitude of further applications that are suited for the second-order approach. These include, for example, variants of non-standard inferences, abductive reasoning, modularization of knowledge bases, non-monotonic reasoning, and reasoning about knowledge.