A cooperative treatment of the plethoric answers problem in RDF

摘要

When querying Knowledge Bases, users are faced with large sets of data, often without knowing their underlying structures. It follows that users may make mistakes when formulating their queries, therefore receiving an unhelpful response. In this paper, we address the plethoric answers problem, the situation where the user query produces significantly more results than the user was expecting. The common approach to solving this problem, i.e. the top-K approach, reduces the query’s result size by applying various criteria to select only some answers. This selection is performed without considering the causes producing plethoric answers, and can therefore miss an underlying issue within the query. We deal with this problem by proposing an approach that identifies the parts of the failing query, called Minimal Failure Inducing Subqueries (MFIS), that cause plethoric answers. As long as the query contains an MFIS, it will fail to reach a sufficiently low amount of answers. Thus, thanks to these MFIS, interactive and automatic approaches can be set up to help the user in reformulating their query. The dual notion of MFIS, called Maximal Succeeding Subqueries (XSS), is also useful. They provide queries with a maximal number of parts of the original query that return non-plethoric answers. Our goal is to compute MFIS and XSS efficiently, so that they may be used to solve the plethoric answers problem. We show that computing this information is an \(\texttt {NP}\)-hard problem. Thus, a baseline exhaustive search method cannot be used for most queries. We propose two algorithms that leverage properties of queries and data to compute MFIS and XSS efficiently for queries of reasonable size. We show experimentally that our two algorithms clearly outperform a baseline method on generated queries as well as real user-submitted queries.