Tractable Query Answering Under Probabilistic Constraints
Antoine Amarilli, Pierre Bourhis, Pierre Senellart · 2014
Large knowledge bases such as YAGO [SKW07] or DBpedia [BLK+09] can be used to answer queries in various domains. However, as they are automatically harvested from Web sources, they may be incomplete: important facts may be missing because they were not materialized in the original sources, or could not be extracted correctly. To mitigate this problem, approaches such as association rule mining [GTHS13] can extract statistical rules from the data which hold in most situations. For instance, people are usually nationals of the country where they are born; people who died in a place are often buried there. The application of such rules allows us to infer some of the missing facts, which may help mitigate the issue of incompleteness. Hence, we study the problem of query answering on large-scale knowledge bases under the constraints of such probabilistic deduction rules. As such rules only represent statistical tendencies, one needs to keep track of uncertainty on rule con-sequences when reasoning about them. There is a large body of work on probabilistic data manage-ment [SORK11]; yet, in that setting, many important tasks are intractable. For example, fixed conjunctive queries may be #P-hard [DS07] to evaluate on a probabilistic instance, even in the very simple tuple-independent database (TID) model [LLRS97]. To work around such hardness results, existing work has already investigated which query classes are tractable over all data instances, with a complex dichotomy