Classical algorithms for query optimization presuppose the absence of inconsistencies or uncertainties in the database and exploit only valid semantic knowledge provided, e.g., by integrity constraints. Data inconsistency or uncertainty, however, is a widespread critical issue in ordinary databases: total integrity is often, in fact, an unrealistic assumption and violations to integrity constraints may be introduced in several ways. In this report we present an approach for semantic query optimization that, differently from the traditional ones, relies on not necessarily valid semantic knowledge, e.g., provided by violated or soft integrity constraints, or induced by applying data mining techniques. Query optimization that leverages invalid semantic knowledge cannot guarantee the semantic equivalence between the original user's query and its rewriting: thus a query optimized by our approach yields approximate answers that can be provided to the users whenever fast but possibly partial responses are required. Also, we evaluate the impact of use of invalid semantic knowledge in the rewriting of a query by computing a measure of the quality of the answer returned to the user, and we rely on the recent theory of Belief Logic Programming to deal with the presence of possible correlation in the semantic knowledge used in the rewriting.
For instance, @cite_0 introduces the model of belief databases, where the tuples of a (relational) database are annotated by users' beliefs, which express their agreement or disagreement on the reliability of the data. Beliefs do not measure uncertainty of knowledge, but provide a qualitative evaluation of the presence of conflicts in the information contained in the database: thus, they are taken into account for query answering, but they are not exploited to optimize a query or to provide approximate results.
@cite_0
2145515910
We propose a database model that allows users to annotate data with belief statements. Our motivation comes from scientific database applications where a community of users is working together to assemble, revise, and curate a shared data repository. As the community accumulates knowledge and the database content evolves over time, it may contain conflicting information and members can disagree on the information it should store. For example, Alice may believe that a tuple should be in the database, whereas Bob disagrees. He may also insert the reason why he thinks Alice believes the tuple should be in the database, and explain what he thinks the correct tuple should be instead. We propose a formal model for Belief Databases that interprets users' annotations as belief statements. These annotations can refer both to the base data and to other annotations. We give a formal semantics based on a fragment of multi-agent epistemic logic and define a query language over belief databases. We then prove a key technical result, stating that every belief database can be encoded as a canonical Kripke structure. We use this structure to describe a relational representation of belief databases, and give an algorithm for translating queries over the belief database into standard relational queries. Finally, we report early experimental results with our prototype implementation on synthetic data. We consider the privacy problem in data publishing: given a database instance containing sensitive information "anonymize" it to obtain a view such that, on one hand attackers cannot learn any sensitive information from the view, and on the other hand legitimate users can use it to compute useful statistics. These are conflicting goals. In this paper we prove an almost crisp separation of the case when a useful anonymization algorithm is possible from when it is not, based on the attacker's prior knowledge. Our definition of privacy is derived from existing literature and relates the attacker's prior belief for a given tuple t, with the posterior belief for the same tuple. Our definition of utility is based on the error bound on the estimates of counting queries. The main result has two parts. First we show that if the prior beliefs for some tuples are large then there exists no useful anonymization algorithm. Second, we show that when the prior is bounded for all tuples then there exists an anonymization algorithm that is both private and useful. The anonymization algorithm that forms our positive result is novel, and improves the privacy utility tradeoff of previously known algorithms with privacy utility guarantees such as FRAPP. The Closed World Assumption (CWA) on databases expresses the assumption that an atom not in the database is false. This assumption is applicable only in cases where the database has complete knowledge about the domain of discourse. In this article, we investigate locally closed databases, that is: databases that are sound but partially incomplete about their domain. Such databases consist of a standard database instance, augmented with a collection of Local Closed World Assumptions (LCWAs). A LCWA is a “local” form of the CWA, expressing that a database relation is complete in a certain area, called a window of expertise. In this work, we study locally closed databases both from a knowledge representation and from a computational perspective. At the representation level, the approach taken in this article distinguishes between the data that is conveyed by a database and the metaknowledge about the area in which the data is complete. We study the semantics of the LCWA's and relate it to several knowledge representation formalisms. At the reasoning level, we study the complexity of, and algorithms for two basic reasoning tasks: computing certain and possible answers to queries and determining whether a database has complete knowledge on a query. As the complexity of these tasks is unacceptably high, we develop efficient approximate methods for query answering. We also prove that for useful classes of queries and locally closed databases, these methods are optimal, and thus they solve the original query in a tractable way. As a result, we obtain classes of queries and locally closed databases for which query answering is tractable. The detection of duplicate tuples, corresponding to the same real-world entity, is an important task in data integration and cleaning. While many techniques exist to identify such tuples, the merging or elimination of duplicates can be a difficult task that relies on ad-hoc and often manual solutions. We propose a complementary approach that permits declarative query answering over duplicated data, where each duplicate is associated with a probability of being in the clean database. We rewrite queries over a database containing duplicates to return each answer with the probability that the answer is in the clean database. Our rewritten queries are sensitive to the semantics of duplication and help a user understand which query answers are most likely to be present in the clean database. The semantics that we adopt is independent of the way the probabilities are produced, but is able to effectively exploit them during query answering. In the absence of external knowledge that associates each database tuple with a probability, we offer a technique, based on tuple summaries, that automates this task. We experimentally study the performance of our rewritten queries. Our studies show that the rewriting does not introduce a significant overhead in query execution time. This work is done in the context of the ConQuer project at the University of Toronto, which focuses on the efficient management of inconsistent and dirty databases.