权益分类	功能权益	普通用户	{{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.

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