Complexity of repair checking and consistent query answering

Abstract

Inkonsistente Datenbanken (also Datenbanken, die gegebene Integritätsbedingungen verletzen) treten heute in vielerlei Anwendungen, nicht zuletzt im Bereich der Datenintegration, auf. Wie mit solchen inkonsistenten Datenbanken umgegangen werden kann, ist Gegenstand aktueller Forschungen. Das Zentrum dieses Forschungsfelds bilden die beiden Konzepte des repairs und der consistent answers. Gegeben eine Datenbank D und eine Menge C an Integritätsbedingungen, die repairs von D in Bezug auf C sind diejenigen konsistenten Datenbanken I die sich von D nur minimal unterscheiden. Die consistent answers einer Abfrage Q sind nun diejenigen Tupel die Q in allen repairs von D liefert. Diese Arbeit untersucht die Komplexität der beiden wohl wichtigsten Entscheidungsprobleme dieses Forschungsfelds: Repair Checking (RC) und Consistent Query Answering (CQA). Das Problem RC ist, gegeben zweier Datenbanken D und I, sowie einer Menge von Integritätsbedingungen C als Eingabe, festzustellen ob I ein repair von D in Bezug auf C ist. Das Problem CQA ist, gegeben einer Datenbank D, Integritätsbedingungen C und einer booleschen Abfrage Q als Eingabe, festzustellen ob Q in allen repairs von D in Bezug auf C erfüllt ist. Bisherige Untersuchungen fokussierten vor allem die Datenkomplexität, also jene Komplexität, bei der lediglich die Datenbank variieren darf, und alle anderen Teile der Eingabe festgehalten werden. Während für einige wenige Klassen an Integritätsbedingungen auch die kombinierte Komplexität (also jene Komplexität, bei der alle Teile der Eingabe variieren dürfen) bekannt war, blieb für die Mehrzahl an Klassen die kombinierte Komplexität bisher noch unerforscht. Eine detaillierte Untersuchung anderer Kombinationen (also zum Beispiel nur die Integritätsbedingungen festzuhalten), war bisher noch komplett ausständig. Das Ziel dieser Arbeit ist eine umfassende Analyse der Komplexität der beiden Probleme RC und CQA für fundamentale Klassen von Integritätsbedingungen. Unsere Analyse ermöglicht ein tieferes Verständnis der unterschiedlichen Quellen der Komplexität und gewährt Einblick in deren teils komplexes Zusammenspiel.

Inconsistent databases (i.e., databases violating some given set of integrity constraints) may arise in many applications such as, for instance, data integration. Hence, the handling of inconsistent data has evolved as an active field of research. The key concepts in this area are those of repairs and consistent answers. Given a set C of integrity constraints and a (presumably inconsistent) database instance D, a repair of D w.r.t. C is a database instance I which satisfies C and which differs minimally from D. The consistent answers of a query Q are those answers that one would obtain over every repair I of D. In this thesis, we consider the two fundamental decision problems in this context: Repair Checking (RC) and Consistent Query Answering (CQA). The problem RC asks, given two databases D and I and a set of constraints C as input, if I is a repair of D w.r.t. C. The problem CQA asks, given a database D, a set of constraints C and a Boolean query Q as input, if Q is true in all repairs of D w.r.t. C. So far, these problems have been mainly studied from the point of view of data complexity (where all parts of the input except for the database are considered as fixed). While for some kinds of integrity constraints, also combined complexity (where all parts of the input are allowed to vary) has been considered, for several other kinds of integrity constraints, combined complexity has been left unexplored. Moreover, a more detailed analysis (keeping other parts of the input fixed - e.g., the constraints only) is completely missing. The goal of our work is a thorough analysis of the complexity of the RC and CQA problems. Our contribution is a complete picture of the complexity of these problems for a wide range of integrity constraints. Our analysis thus allows us to get a better understanding of the true sources of complexity.