Dynamic Expressiveness of Logics

大量的数据，受制于频繁的更新，构成了数据管理系统最近的挑战。搜索引擎使用和维护的数据会随着收到的消息而不断更新。社交网络中的关系变化频繁，对其他用户的数据可见性产生了各种各样的影响。在这样的动态环境中，从效率的角度考虑，每次更新数据后从头开始计算必要的信息往往是不可能的。相反，它可以用所谓的“动态算法”增量计算。这些算法在更新数据和预先计算的辅助信息的基础上工作。然而，在计算机科学的许多应用中，查询现在不是作为算法公式化的，而是通过声明性规范语言。用户只描述查询结果的所需属性，而不描述如何计算这些属性。通常，这种声明性规范语言是基于逻辑的。例如，时态逻辑是用于自动验证的规范语言的基础，是用于数据库查询语言的谓词逻辑的基础，是用于本体的描述逻辑的基础。这个项目的重点是在动态场景中作为规范语言使用的逻辑的表达能力，也就是说，这种逻辑以增量方式描述查询的能力。最后一个主要的，系统的探索这一领域的研究已经在2003年Hesse的论文项目中进行。从那时起，这项技术的现状主要是零星的结果，其中一些是由本建议的作者获得的。因此，缺乏对这一领域进行最新的全面检查，考虑到新的研究观点。在这个项目中，将系统地开发用于扩大增量可表达查询类的新技术。在这样做的同时，我们的目标是开发探索这种逻辑的表达性边界的方法。最后-类似于经典的，“非动态”的情况-逻辑规范语言的动态表达能力和算法的动态复杂性之间的联系将被检查。

Enormous amounts of data, subject to frequent updates, constitute a recent challenge for data management systems.Data used and maintained by search engines is continuously updated by incoming messages. Relationships in social networks are changing frequently, with various consequences for the visibility of data for other users.In such dynamical settings it is often - in view of efficiency - impossible to compute neccessary information from scratch after each update on the data. Instead, it can be incrementally computed with so-called 'dynamic algorithms'. Those algorithms work on the basis of the updated data and precomputed auxiliary information.However, in many applications of computer science, queries are nowadays not formulated as algorithms, but by means of declarative specification languages. Users only describe desired properties of the query results but not how they have to be computed. Usually, such declarative specification languages are based on logics. For example, temporal logics are the basis of specification languages for automatic verification, predicate logic for query languages for databases and description logics for ontologies.The focus of this project is on the expressivity of logics used as specification languages in dynamic scenarios, that is, the ability of such logics to describe queries in an incremental fashion.The last major, systematic exploration of this area of research has been undertaken in the dissertation project of Hesse, 2003. Since then the state of the art was dominated by sporadic results, some of which were obtained by the author of this proposal. An up-to-date comprehensive examination of this area, taking fresh research perspectives into account, is thus lacking.In this project, new techniques for enlarging the class of incrementally expressible queries shall be develloped systematically. While doing so, we aim at develloping methods for exploring the borders of expressivity of such logics, too. Finally - similar to the classical, "non-dynamic" case - connections between dynamic expressivity of logical specification languages and algorithmic dynamic complexity shall be examined.