Title: Spec-QP: Speculative Query Planning for Joins over Knowledge Graphs,
Abstract: Organisations store huge amounts of data from multiple heterogeneous sources
in the form of Knowledge Graphs (KGs). One of the ways to query these KGs is to
use SPARQL queries over a database engine. Since SPARQL follows exact match
semantics, the queries may return too few or no results. Recent works have
proposed query relaxation where the query engine judiciously replaces a query
predicate with similar predicates using weighted relaxation rules mined from
the KG. The space of possible relaxations is potentially too large to fully
explore and users are typically interested in only top-k results, so such query
engines use top-k algorithms for query processing. However, they may still
process all the relaxations, many of whose answers do not contribute towards
top-k answers. This leads to computation overheads and delayed response times.
We propose Spec-QP, a query planning framework that speculatively determines
which relaxations will have their results in the top-k answers. Only these
relaxations are processed using the top-k operators. We, therefore, reduce the
computation overheads and achieve faster response times without adversely
affecting the quality of results. We tested Spec-QP over two datasets - XKG and
Twitter, to demonstrate the efficiency of our planning framework at reducing
runtimes with reasonable accuracy for query engines supporting relaxations.