Project Details
Projekt
Team Logics: New Bridges to Database Repairs
Applicant
Privatdozent Dr. Arne Meier
Subject Area
Theoretical Computer Science
Term
since 2023
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 511769688
Many areas of life in modern society are connected with or depend on large amounts of data: weather forecasts, internet search queries, or medical databases to name only a few. It is no exaggeration to say that the field of database theory is interwoven with many aspects of our lives. A fundamental concern in data processing is data consistency. In database systems, one assures consistency by providing several constraints that the database must satisfy at any instant of time. Particularly, large databases often lack this property or may become inconsistent in a variety of scenarios and for different reasons. For example, inconsistency may arise when multiple datasets are combined, whereas each dataset is consistent. For a bit more than a decade now, a modern concept of dependence and independence in logic exist. In 2007, Jouko Väänänen proposed with his Dependence Logic (DL) a logic in which one can express dependencies between variables as part of formulas in that logic. A team is a set of assignments and team semantics is the underlying concept in these logics. Clearly, DL can be seen as a logic quite close to the formalisms of databases. We will consider Repair Checking (RC) and Conjunctive Query Answering (CQA) from the perspective of DL. Here, we will focus on update-repairs and aim for a fitting connection to DL. Specifically, denial and equality generating dependencies is something we want to address by finding corresponding semantics and notions in DL. Furthermore, we aim to investigate the concept of Embedded Multi-Valued Dependencies (Fagin, 1977) in the scope of DL. These dependencies play an important role in database theory. Driven by the motivation to better understand the complexity of such database-related problems (the inference problem for functional and inclusion dependencies combined is undecidable), we will investigate such concepts in the fresh environment of team logics. Another cause for inconsistencies in DBs can be the exchange of data. Here, there are connections to the area of Belief Revision as well as Argumentation eminent. In this project, we also will approach the studied problems via the framework of parameterised complexity. Here, one thoroughly studies the complexity of problems w.r.t. so-called parameters beyond the classical complexity (in which one analyses problems w.r.t. the plain input length).
DFG Programme
Research Grants
International Connection
Austria, Finland, New Zealand, Sweden, USA
