权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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。从那时起，最先进的技术就被零星的结果所主导，其中一些结果是由该提案的作者获得的。因此，缺乏对这一领域的最新全面审查，考虑到新的研究视角。在这个项目中，将系统地开发用于扩大增量可表达查询类别的新技术。在这样做的同时，我们的目标也是开发探索这种逻辑的表达性边界的方法。最后 - 类似于经典的“非动态”情况 - 应检查逻辑规范语言的动态表达性和算法动态复杂性之间的联系。