Practical query answering in data exchange under inconsistency-tolerant semantics

Abstract

Exchange-repair semantics (or, XR-Certain semantics) is a recently proposed inconsistency-tolerant semantics in the context of data exchange. This semantics makes it possible to provide meaningful answers to target queries in cases in which a given source instance cannot be transformed into a target instance satisfying the constraints of the data exchange specification. It is known that computing the answers to conjunctive queries under XR-Certain semantics is a coNP-complete problem in data complexity. Moreover, this problem can be reduced in a natural way to cautious reasoning over stable models of a disjunctive logic program. Here, we explore how to effectively perform XR-Certain query answering for practical data exchange settings by leveraging modern sophisticated solvers for disjunctive logic programming. We first present a new reduction, accompanied by an optimized implementation, of XR-Certain query answering to disjunctive logic programming. We then evaluate this approach on a benchmark that we introduce here and which is modeled after a practical data exchange problem in computational genomics. Specifically, we present a benchmark scenario that mimicks a portion of the UCSC Genome Browser data import process. Our initial results, based on real genomic data, suggest that the solvers we apply fail to take advantage of some critical exploitable structural properties of the specific instances at hand. We then develop an improved encoding to take advantage of these properties using techniques inspired by the notion of a repair envelope. The improved implementation utilizing these techniques computes query answers ten to one thousand times faster for large instances, and exhibits promising scalability with respect to the size of instances and the rate of target constraint violations.