Lineage-enabled Query Answering in Uncertain Knowledge Bases

We present a unified framework for query answering over uncertain RDF knowledge bases. Specifically, our proposed design combines correlated base facts with a query driven, top down deductive grounding phase of first-order logic formulas (i.e., Horn rules) followed by a probabilistic inference phase. In addition to static input correlations among base facts, we employ the lineage structure obtained from processing the rules during grounding phase, in order to trace the logical dependencies of query answers (i.e., derived facts) back to the base facts. Thus, correlations (or more precisely: dependencies) among facts in a knowledge base may arise from two sources: 1) static input dependencies obtained from real-world observations; and 2) dynamic dependencies induced at query time by the rule-based lineage structure of the query answer. Our implementation employs state-of-the-art inference techniques: We apply exact inference whenever tractable, the detection of shared factors, shrink- age of Boolean formula when feasible, and Gibbs sampling in the general case. Our experiments are conducted on real data sets with synthetic expansion of correlated base facts. The experimental evaluation demonstrates the practical viability and scalability of our approach, achieving interactive query response times over a very large knowledge base. The experimental results provide the success guarantee of our presented framework