Dynamic Expressiveness of Logics

逻辑的动态表达

基本信息

批准号：
228818952
负责人：
Professor Dr. Thomas Schwentick
金额：
--
依托单位：
Informatik I - Lehrstuhl Logik in der Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2013
资助国家：
德国
起止时间：
2012-12-31 至 2019-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/228818952?language=en
关键词：
Dynamic Expressiveness 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.

通过频繁更新的大量数据构成了数据管理系统的最新挑战。通过搜索引擎使用和维护的数据通过传入消息不断更新。社交网络中的关系经常发生变化，对其他用户的数据可见性产生了各种后果。在这种动态设置中，鉴于效率，在每次数据更新后都无法从头开始计算必要信息。相反，可以使用所谓的“动态算法”来逐步计算它。这些算法是根据更新的数据和预先计算的辅助信息来工作的。但是，在计算机科学的许多应用中，当今查询不是作为算法提出的，而是通过声明的规范语言进行的。用户仅描述查询结果的所需属性，但不描述必须如何计算它们。通常，这种声明的规范语言基于逻辑。例如，时间逻辑是自动验证的规范语言的基础，数据库的查询语言的谓词逻辑和描述本体论的逻辑。该项目的重点是在动态场景中用作规范语言的逻辑的表达性，也就是说，在动态场景中，即在最终的研究中描述了这种逻辑的能力。 Hesse，2003年。从那时起，艺术的状态由零星的结果主导，其中一些是由本提案的作者获得的。因此，缺乏对这一领域的最新全面检查，并考虑了新的研究观点。在该项目中，应系统地对扩大渐进式查询的新技术进行系统的发展。在这样做的同时，我们旨在探索这种逻辑表达性的边界。最后 - 应检查与经典的“非动态”情况 - 逻辑规范语言的动态表达之间的连接与算法动态复杂性之间的连接。