Query containment is a fundamental operation used to expedite query processing in view materialization and query caching techniques. Since query containment is NP-complete for arbitrary conjunctive queries on RDF graphs, we have introduced a simpler form of conjunctive queries that we name f-graph queries. During the demo, we will show why containment checking for f-graph queries can be solved in polynomial time. We will present the mv-index, a novel indexing structure that allows for fast containment checking between a single RDF-conjunctive query and an arbitrary number of stored queries. The mv-index structure takes advantage of the interesting properties of f-graph queries. With the mv-index usage, the containment test against hundreds of thousands of queries that are indexed within our structure is performed in microseconds or less.
The growing popularity of graph-structured data in many real-world applications such
as Oil and Gas [
View materialization is directly related to the problem of query containment [
In this demo, we will present f-graph queries, a restricted form of conjunctive
queries that allows to solve the containment checking problem in PTime. Additionally
we will present an efficient indexing structure, the mv-index, for checking the
containment relation between a single f-graph query Qf and a set of indexed queries W in
PTime w.r.t. the combined size of the query and the index. We will further show how
we have extended mv-indices to evaluate containment for arbitrary conjunctive queries
on RDF graphs. This translates to microseconds or less for the containment test against
hundreds of thousands of queries that are indexed within the structure. The latter makes
mv-indices the perfect candidate to be combined with existing and novel materialization
and techniques. The corresponding demo is based on the work presented in [
We will now describe the fundamentals of our indexing structure that is build upon the f-graph class of queries.
F-Graph Queries & Query Containment. To solve the containment problem and build the corresponding indexing structure, we initially focus on its variation Qf v W where Qf belongs to a special class of conjunctive queries that we name f-graph queries and W belongs to the class of conjunctive queries that have only IRIs as predicates. What motivates the choice of f-graph queries in the left-hand side of a query containment is that: (i) containment for f-graph queries can be solved in PTime; (ii) f-graph queries appear in real- world query workloads; (iii) f-graph queries can be employed as representatives of arbitrary conjunctive queries.
An f-graph query Qf is a conjunctive query for which: (i) For every pair of terms
o1, o2 such that o1 6= o2, the triple patterns (s; p; o1), (s; p; o2) cannot both appear in
Qf ; (ii) For every pair of terms s1; s2 2 I [ X such that s1 6= s2, the triple patterns
(s1; p; o), (s2; p; o) cannot both appear in Qf . We name these queries f-graphs because
of the functional and inverse functional characteristics of their predicates. Note that
containment of such queries is polynomial due to the strong requirements for the
fgraph structure. Once a variable v in W has been mapped to a term v0 in Q, there is a
single deterministic choice for mapping the remaining variables appearing in W .
MV-Indices. In the case that we want to check for containment between a single
fgraph query Qf and a set of conjunctive queries W , it would be inefficient to make
each and every comparison. For that reason, we have introduced the
“MaterializedView Index” structure, denoted with mv-index, that allows to store a set of queries W
and use it to check for containment. Our structure is based on Radix trees, ordered tree
data structures that are used in string matching [
An mv-index M is a tree structure (V; E; L) where: (i) V is a set of vertices; (ii) E v V 2 is a finite set of edges; (iii) L is a labelling function that maps each edge to a nonempty ordered list of distinct elements (IRIs, literals, and parenthesis symbols) and each vertex to the serialized form of an f-graph query.
The intuition for this form of representation is that queries are represented by their serialized form in the mv-index structure, either as intermediate or leaf vertices, using the labelling function L. For a vertex in the mv-index structure, L( ) is its corresponding query in serialized form. The serialized form of the query represented by a vertex can be also obtained by following the path from the root of the mv-index to the specific vertex and concatenating the corresponding edge labels. Therefore, in our actual implementation we only store edge labels.
During the insertion phase, mv-indices are treated as regular Radix trees that instead
of strings or numbers are used to represent queries in their serialized form. Therefore,
instead of characters within a string, or digits within a number, mv- indices use IRIs,
Mv-Index: An Efficient Index for Graph-Query Containment
literals, variables and separators such as parenthesis symbols in order to represent
serialized queries. More information on how insertion works in Radix trees can be found
in the literature [
F-Graph Witnesses for Conjunctive Queries. For our algorithm to represent more expressive conjunctive queries, we have introduced f-graph witnesses. The intuition is that each conjunctive query can be represented in the form of an f-graph when checking for query containment.
For a conjunctive query Q, its corresponding f-graph witness can be obtained by merging terms that violate conditions (i), (ii) in the definition of f-graph queries. To perform the aforementioned task, we initially define the equivalence relation on variables, IRIs, and literals in Q such that o1 o2 when there exists a term s for which either the triple patterns (s; p; o1) and (s; p; o2) both appear in Q, or the triple patterns (o1; p; s) and (o2; p; s) both appear in Q. For a term s in Q, [s] denotes its equivalence class on the relation that contains all the terms that are merged with s. The f-graph witness Qw of the query Q is obtained by replacing each triple pattern (s; p; o) in the body of Q with a triple pattern ([s]; p; [o]) where s; o are terms, [s]; [o] their corresponding equivalence classes, and p is a predicate.
For a conjunctive query Q, its corresponding f-graph witness Qw and a conjunctive query W , the following implication applies: Q v W ) Qw v Q. The previous proposition conveys that we need to check for containment Q v W only when the containment relation for the witness of Q is satisfied, i.e., Qw v W . Checking Qw v W can be performed in PTime, while checking Q v W is in the worst case a NPcomplete problem. Therefore, we pay a PTime budget to solve specific instances of a NP-complete problem by “postponing” non-deterministic checks in favor of a proof, computed in PTime, that Q v W does not apply. 3
In the demo we will show how we have implemented our novel structures and algorithms and test their efficiency in a combined query workload consisting of DBPedia, WatDiv, BSBM, LUBM, and LDBC queries. We will evaluate insertion and containment performance with respect to different query and mv-index properties. The average
Mailis et al. time for query containment against an mv-index containing 397,507 distinct queries from all 5 workloads was between 0:0093 msec and 0:041 msec. A presentation of our work is available online.
Acknowledgements. This work was partially funded by the SIRIUS Centre, Norwegian Research Council project number 237898. T. Mailis was financed by EU Horizon2020, “DARE” project, Grant Agreement nr. 777413. Y. Kotidis was financed by the Research Centre of Athens University of Economics and Business, in the framework of the project entitled Original Scientific Publications.