Dynamic Expressiveness of Logics

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

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.