TL;DR
This paper introduces and analyzes relative inconsistency measures for indefinite databases, which can represent partial or disjunctive information. The authors propose a formal definition for these measures, investigate their compliance with rationality postulates, and analyze their computational complexity, offering a more nuanced way to quantify data quality in complex databases.
What Problem Does This Paper Address?
In AI and data management, dealing with conflicting or imprecise information is a significant challenge. Data quality directly impacts the effectiveness of AI systems, and understanding the severity and sources of inconsistency is crucial for improving data quality. While inconsistency measures (IMs) exist, most focus on "absolute" measures (total amount of inconsistency). However, "relative" measures, which quantify inconsistency as a proportion of the knowledge base, are often more intuitive and useful, especially when comparing databases of different sizes. This paper specifically tackles the problem of defining and analyzing relative inconsistency measures for indefinite databases. Indefinite databases, unlike traditional definite databases, can represent information that is not precisely known, using disjunctive tuples (e.g., "Person X is either A or B"). This adds complexity to inconsistency measurement, as conflicts can arise from multiple disjunctive possibilities. The paper aims to bridge this gap by extending the concept of relative inconsistency measures to this more expressive data model.
Methods
The authors introduce a postulate-based definition for relative inconsistency measures (IMs) specifically for indefinite databases with denial constraints (DCs). Denial constraints are a type of integrity constraint that specifies conditions that must not hold in the database. They then propose five specific relative IMs: $Im_v$, $IM$, $I_p$, $I_H$, and $I_C$. These measures are inspired by existing approaches for propositional knowledge bases and definite databases but are adapted to handle the disjunctive nature of indefinite tuples.
A key aspect of their methodology is the analysis of how these proposed IMs satisfy a set of rationality postulates. These postulates are desirable properties that an inconsistency measure should ideally possess, such as consistency (a consistent database has zero inconsistency) and normalization (inconsistency is bounded between 0 and 1). They also introduce and analyze additional postulates like "Safe-Element Reduction" and "MI-Normalization" to better characterize the behavior of these measures in the context of indefinite databases.
Furthermore, the paper delves into the computational complexity of these measures. They analyze the "data complexity" of problems related to computing the inconsistency value (the IM problem) and deciding if the inconsistency falls below, above, or exactly matches a given threshold (LV, UV, EV problems). This involves determining the complexity class to which these problems belong, considering both definite and indefinite databases.
Datasets
Not discussed in the paper. The paper focuses on theoretical definitions and complexity analysis, using a running example (Table 1, "Ancestor" database) to illustrate concepts rather than evaluating measures on large datasets.
Key Insights and Ideas
- Indefinite Databases Need Specialized IMs: Traditional inconsistency measures designed for definite data don't directly translate to indefinite databases due to the inherent disjunctions, requiring new formalisms.
- Postulates Guide Measure Design: The paper emphasizes the importance of rationality postulates in defining and evaluating inconsistency measures, showing how different measures satisfy varying sets of these properties.
- Trade-offs in Postulate Satisfaction: No single measure satisfies all desirable postulates, highlighting inherent trade-offs. For instance, "MI-Normalization" and "Contradiction" are shown to be incompatible.
- Complexity Varies Significantly: The computational complexity of calculating inconsistency measures can vary dramatically between definite and indefinite databases, and also among different measures themselves. Some measures remain tractable even for indefinite data, while others become quite complex, residing in higher levels of the polynomial hierarchy.
- Relative Measures Offer Nuance: The focus on relative measures provides a more intuitive understanding of inconsistency as a proportion, which is often more informative than absolute counts, especially for comparing databases of different scales.
Key Results
- Formal Definition and Five Measures: The paper provides a formal definition for relative inconsistency measures for indefinite databases with denial constraints and introduces five specific measures ($Im_v$, $IM$, $I_p$, $I_H$, $I_C$).
- Postulate Compliance: Table 2 summarizes the postulate satisfaction for these measures. Notably, $I_p$ and $I_H$ satisfy 7 out of 8 postulates for indefinite databases, while $Im_v$ and $I_C$ perform better for definite databases.
- Complexity Analysis: Table 3 details the complexity of computing inconsistency values and related decision problems. For indefinite databases, complexities range from P to $\Sigma_2^p$, $\Pi_2^p$, $D_p^c$, and even counting classes like #coNP. For definite databases, many measures are tractable (P for decision problems, FP for computation). Measures $I_H$ and $I_C$ maintain their complexity from definite to indefinite databases, while others become significantly harder.
Limitations and Future Work
- Limitations:
- The paper primarily focuses on theoretical definitions and complexity analysis, with limited empirical evaluation on real-world datasets.
- The set of postulates considered, while comprehensive, is not universally agreed upon, and alternative sets might lead to different conclusions about measure suitability.
- The analysis is limited to denial constraints and does not cover other types of integrity constraints like inclusion dependencies.
- Future Work:
- Other Forms of Incomplete Information: Extend the framework to handle other types of uncertainty, such as null values or "maybe" information.
- Broader Constraint Types: Incorporate other integrity constraints beyond denial constraints.
- Attribute-Level Inconsistency: Develop measures that can pinpoint inconsistencies at the attribute level, distinguishing issues arising from different sets of attributes.
- Implementation and Empirical Studies: Develop practical implementations (e.g., using ASP solvers) and conduct extensive empirical studies on real-world databases to validate the theoretical findings and compare the practical performance of the proposed measures.
Summary updated