Database theory is the area of theoretical computer science that investigates the foundations and
principles of data management systems using mathematical methods and techniques. This Research-in-Groups programme
will focus on aspects of managing inconsistent databases, i.e., databases that violate one or more integrity constraints that the data at hand ought to obey. For the past 25 years, database repairs and consistent query answers have been the main approach for coping with inconsistent databases. This investigation has been carried out under the assumption that set semantics is used. In recent
years, there has been a growing study of topics in data management under semiring semantics, which includes bag semantics as a special case (the standard semantics for the widely used query language SQL). So far, however, the study of semiring semantics has not been extended to database repairs and consistent answers. The goal of the proposed research is to investigate, for the first time,
inconsistent databases under semiring semantics. Specific problems include understanding the changes in the semantics and the computational complexity resulting when one shifts from setbased data (i.e., data annotated using the Boolean semiring) to the more general setting of semiring annotated data (bag semantics is the special case in which the annotations come from the semiring of
the natural numbers).
The research will be carried out by using mathematical methods and techniques from algebra, logic, computational complexity, and graph theory.
The participants (Phokion Kolaitis, Nina Pardal, and Jonni Virtema) met and interacted at the Simons Institute for the Theory of Computing in November of 2023. This interaction led them to embark on a research project aiming to carry out a systematic study of database repairs and consistent answers under semiring semantics, as described in the research proposal.
