smart-KG: Partition-Based Linked Data Fragments for querying knowledge graphs

2.1.RDF and SPARQL

The Resource Description Framework (RDF) [74] is a graph-based data model to represent information about web resources (e.g. documents, people, sensors, etc.) and their relationships in the form of triples (subject, predicate, object) ∈(U∪B)×U×(U∪B∪L), where U, B, L are infinite, mutually disjoint sets of IRIs, blank nodes, and literals, respectively [32].

Let t be a single RDF triple belonging to the RDF knowledge graph G. We use subj(t), pred(t), and obj(t) to denote the components of t, which represent RDF terms including URIs/IRIs, blank nodes, and literals. The RDF knowledge graph G is a finite set of such triples, where subj(G), pred(G), and obj(G) represent the subjects, predicates, and objects contained within G.

RDF graphs can be queried using the SPARQL [34] query language, which relies on graph pattern matching. The atomic expression of SPARQL is a triple pattern tp from (U∪V)×(U∪V)×(U∪L∪V) where elements from a set V of variables are permitted, which are disjoint with the previously mentioned RDF terms U, B and L.

Note that, in the context of our introduced work, without loss of generality – and similar to [78] – (i) we do not consider explicitly blank nodes in query patterns, which are just synonyms for (non-distinguished) variables in query patterns, and also (ii) assume blank nodes in the graphs G just as constants like IRIs, leaving out the intricacies of blank node matching in the definition of the SPARQL specification [34].

A Basic Graph Pattern (BGP) consists of a conjunction of triple patterns also represented as a set {tp1,…,tpn}. We denote (left-linear join order) query execution plans using sequences (…), i.e., for instance, (tp1,…,tpn) denotes a left-linear query execution plan (…(tp1⋈tp2)⋈…)⋈tpn) where ⋈ denotes a join operator.

Apart from BGPs, we will also consider in some discussions in this paper FILTER patterns, i.e., if P is a BGP and ϕ is a FILTER condition, then P FILTER ϕ is called a filtered graph pattern (FGP). For the sake of this paper, we restrict ourselves to simple filter conditions of the form ϕ=(termθconst), where term is a subject, predicate, or object of triples, and θ is a comparison operator such as <,>,=,⩽,and⩾. In the general case, FILTER conditions could possibly contain multiple terms connected by the logical connectors such as ¬, ∨, and ∧, etc. For any (BGP or FGP) query pattern Q over an RDF graph G, we denote by var(Q) its variables. Additionally, subj(Q), pred(Q), and obj(Q) denote the subjects, predicates, and objects extracted from the query, respectively.

The solutions of a query pattern Q over a KG G are denoted as ⟦Q⟧G=Ω, where each ω∈Ω denotes a substitution from the variables in Q matching triples in G. The solutions are given as sets Ω of bindings, i.e., mappings of the form, ω:var(Q)→R to the set R of RDF terms appearing in G, such that G⊧ω(Q), i.e., ω(Q) forms a (sub)graph entailed by G. If there are no result mappings, then ⟦Q⟧G=∅, whereas a solution to a variable-free pattern is indicated by a single solution, i.e., ⟦Q⟧G={ω∅}, with ω∅={} being the empty mapping.

For BGPs and FGPs, ⟦·⟧G can be defined as follows, cf. [63]. Let P be a BGP and ϕ be a FILTER condition, then:

Two mappings ω1, ω2 are compatible [63], denoted as ω1‖ω2, if for any v∈dom(ω1)∩dom(ω2), ω1(v)=ω2(v).

Since the main focus of this paper is on BGPs, we omit further details about the other patterns which in essence can be constructed on top of the base retrieval functionality of BGPs (cf. [63]). Note that FGPs and also other patterns e.g. UNION, OPTIONAL, etc. are mostly expected to be executed on the client-side in the approaches we discuss further. In future work, we look into the direction of distributing the execution of other patterns between server and client to further increase the efficiency of our approach.

2.2.RDF HDT compression

For efficient storage and querying of RDF graphs, we will herein particularly rely on HDT [25], a well-known compressed format for RDF graphs that permits efficient triple pattern retrieval over the compressed data. HDT has three main components: (i) a dictionary maps RDF terms to IDs, such that (ii) the triples component encodes the resulting ID-graph (i.e. a graph of ID-triples after replacing RDF terms by their corresponding dictionary IDs) as a set of adjacency lists, one per different subject in the graph. In addition, (iii) the header provides descriptive metadata (publishing information, basic statistics, etc.) about the RDF graph.That is, an HDT file of a graph G consists of a header H, a dictionary D and triples T, i.e., HDT(G)=(H,D,T), stored in compressed, queryable encodings: Both the HDT dictionary and triples are self-indexed to support efficient retrieval operations. The dictionary implements prefix-based Front-Coding compression [58], which allows for high compression ratios and efficient string-to-id and id-to-string operations. Triples are indexed by subject (in SPO order) using bitmaps [25].

RDF graphs compressed with HDT can be queried loaded in memory or mapped from disk without prior decompression. HDT exhibits competitive performance for scan queries as well as triple pattern execution when the subject is provided. In addition, HDT compressed graphs are typically enriched with a companion HDT index file [59]. This additional file includes two inverted indexes on the ID-triples (in OPS and PSO order) to achieve high performance for resolving all SPARQL triple patterns.

In fact, HDT has been used as an efficient backend for many implementations of Linked Data Fragments query interfaces, which we will discuss next.

2.3.Linked Data Fragments (LDF)

In this section, we characterize existing Web KGs querying interfaces following the foundations set by the Linked Data Fragments framework (LDF) [78]. LDF has been designed to abstractly model Web KG querying interfaces with a higher or lesser degree of expressivity and balance for distributing the query processing load between clients and servers. In essence, LDF characterizes interfaces that enable live querying to fragments of a KG G based on a limited range of query patterns (e.g, single triple patterns or star patterns) that a client is allowed to request from the server. Generally, the aim of different LDF interfaces is to mitigate the expensive server-side computation load and to enable efficient reusable caching for these limited patterns, while shifting the processing of more complex patterns to the client. Several LDF interfaces also support additional controls. For instance, a control parameter to transfer intermediate bindings together with query patterns, or a control to specify the page size to determine the “chunk size” of results batched in each server response.

In the following, we slightly adapt the original specification of the LDF framework [38,78] to align formal definitions and notations to uniformly describe the current KG APIs, while we leave out herein details in LDF such as metadata sent along with query results and hypermedia controls:

For BGP queries Q, we define two specific variants of selector functions, s(·) and s∗(·), which differ essentially in terms of returning either a single graph containing all triples relevant to any solution or one subgraph per solution ω∈⟦Q⟧G:

Note that, whenever the set of bindings Ω is not considered (i.e. only empty binding sets Ω=∅ are expected) in a particular selector function, we will conveniently also just write short σ(G,Q) (or s(G,Q), s∗(G,Q), resp.) instead of σ(G,Q,Ω) (or s(G,Q,Ω), s∗(G,Q,Ω), resp.) in the following.66 As we will see, all existing LDF APIs considered in this paper and summarised in Table 1 can be expressed in terms of one of the two standard selector functions s(·) and s∗(·), whereas we will extend and modify those – in terms of partition-based LDF – in the following.

The general paging mechanism Φ we use in this paper enables the ability to retrieve the result in batches e.g., for the cases where Γ (or, resp., Γ∗) is overly large, or, resp. when only partial results are required or to enable incremental results. Hence, we assume that Φ(n,l,o) simply defines a mechanism to divide Γ into a set of partitions (or pages) Γ∗={Γ0,…,Γk−1}, where for each page Γi it is guaranteed that |Γi|<n (i.e. Γi does not contain more than n triples), and l and o, resp. would allow to request the pages from Γo to Γo+l−1. We assume l to default to l=1, o to default to o=0, and finally n=∞ signifying that whole graph Γ (or, resp., Γ∗) should be returned. “Pagination”, i.e., retrieving Γ∗ in chunks of l pages could then be achieved in terms of iteratively calling the LDF API with Φ(n,l,o) with increasing o, starting from o=0 in steps of o:=o+l. As such l, o could be viewed analogous to the SPARQL LIMIT and OFFSET modifiers but applied to pages instead of individual solution mapping; we note here, that we define Φ and likewise Γ∗ in a more general way than the original LDF paper [78],77 allowing parameters to both specify a maximum page size n, and the number of pages l retrieved per request as separate parameters, starting from a page index offset o, in order to allow flexible interpretations of the LDF “metaphor”, fitting various interfaces and partitionings. We also note that in the following – as opposed to and generalizing [78] – we do not necessarily consider Γi and Γj disjoint for i≠j.

3.1.Vertical partitioning (VP)

VP [2] creates a partition for each unique predicate in pred(G), i.e., in our terms,

Next, admissible queries are any single triple pattern queries Q={tp} where

That is, for any triple pattern query Q, either a single predicate partition corresponding to the query predicate, or all predicate partitions would be returned.

Many RDF processing systems (cf. Table 2) report achieving a high query performance using vertical partitioning. Yet, as a partitioning mechanism for partition-based LDFs interfaces, this approach only works well for triple pattern queries with bounded predicates, whereas other triple patterns require shipping all predicate partitions. Along these lines, assuming all predicates in Q are bound, a strict lower bound for the number of shipped partitions is |pred(Q)∩pred(G)|, because only the partitions for predicates mentioned in the query that also occur in G are shipped.

A second drawback of using vertical partitioning in the context of partition-based LDF interfaces is that it only supports single triple queries while any joins or more complex patterns would need probably to be fully evaluated on the client side. Also, full vertical partition shipping has potential downsides compared with TPF or brTPF, which solves any binding in triple patterns directly on the server side. For all these reasons, we will in our proposed approach rather use (br)TPF directly for single triple queries.

3.2.Horizontal/range/sharding partitioning

In the context of distributed relational databases, horizontal partitioning involves splitting a relation horizontally (i.e. row-wise) into sub-relations based on selections to enhance the load balancing. Analogously, RDF management systems have adopted horizontal partitioning strategies to distribute the triples of an RDF graph into multiple partitions based on certain selection criteria. In these strategies, the selection is typically used to generate horizontal subsets of the RDF triples for very common predicates (such as e.g. rdf:type, which often does not lend itself well to vertical partitioning techniques), where each subset consists of all the triples that satisfy a predetermined selection condition on the objects or subjects. Herein, we exemplify horizontal partitioning based on object ranges; that is, we assume partitions per n object ranges (e.g. from a histogram) can be split into a set of ordered values {v0,…,vn}. Given the RDF model, this is not an unreasonable assumption, indeed, both literals and likewise URIs could be assumed to be ordered with respect to their string representations, and – even if many real-world RDF graphs do not contain blank nodes – also blank nodes could, while not ordered in the RDF model itself, be canonicalised [45] and ordered, respectively. Accordingly, we can define

Object-based horizontal partitioning could be used for partition shipping, where any BGP query Q is admissible that consists of triples with the same object, i.e., obj(Q)={o} (which of course includes single triple queries with bounded object), but, again, for unbounded objects, the entire partitioning G would need to be shipped:

Horizontal partitioning could be analogously defined for bound subjects, or be combined with vertical partitioning (i.e. be used to further subdivide vertical partitions); in fact, vertical partitioning as defined above could be viewed as a “special form” of horizontal partitioning on the predicate position, with “predicate ranges” corresponding to the single predicates in pred(G).

Variations of horizontal partitioning have been used successfully by several RDF systems, especially in distributed environments (cf. Table 2), where partitions are allocated to different nodes while minimizing the communication cost among the nodes (by placing jointly queried data together) and balancing the node workload (by placing highly requested partitions in different nodes). In general, horizontal partitioning supports efficient querying for queries that require shipping a single partition based on the FILTER condition that defines the shipped partitions. As such, there are similar (dis-)advantages as for vertical partitioning: for our example of horizontal partitioning on the object, whenever the object is unbound, all partitions would need to be retrieved. Likewise, depending on the choice of ranges (v1 to vn) to “split” the partitions and data distribution, the matching partitions could contain potentially large amounts of irrelevant data or different horizontal partitions could contain a prohibitively large superset of the answers of the query, e.g., by including further predicates which are not requested in the query. The latter could be remedied by combining more sophisticated forms of vertical and horizontal partitioning. For example, family-based partitioning techniques described in Section 3.6 and Section 3.7 can be seen in a sense as vertical partitioning and a combination of vertical and horizontal partitioning, respectively.

3.3.Hash partitioning (HP)

Hash-based partitioning is a common partitioning strategy among RDF distributed systems. For instance, position-based hashing is a lightweight partitioning strategy that applies a hash function to a particular position (e.g. subject-based hashing) in triples, distributing the RDF triples according to their hash values into a fixed number of n bins. Thus, all the triples with the same value in this position (e.g. same subject) are allocated to one partition. Hash partitioning is computationally inexpensive plus the hash operation can be efficiently computed in parallel. However, as usual with hashing, hash collisions may cause skewed partition sizes. Hash-based partitioning could be defined in a very similar manner as above, exemplified here for subject-based hashing with n partitions. Assuming a suitable hash function h(·):

For position-based hashing (analogously to position-based horizontal partitioning explained above), any basic graph patterns sharing the same value in the respective position, e.g. subjects, would be admissible patterns. For such admissible queries σ(G,Q) could again be analogously defined based on the hash function h(·) of the resp. position, that is e.g. based on h(subj(Q)), as above, with the same problems of retrieving all G whenever the subject is unbound. Likewise, these definitions can easily be extended to object, predicate, or even triple-based hashing (based on a “ternary” hash function h(s,p,o)).

Position-based hashing can be extended by specific hash functions, e.g. prefix-hashing [48], to ensure that subjects (or other position terms) with the same prefix end up in the same partition, which can be exploited in range queries. Another extension is k-hop hashing which could cater for certain path queries, by creating (potentially overlapping) partitions that extend simple hash-based partitions with the k-hop neighborhoods of the hashed triples [52].

3.4.Workload-aware partitioning

Workload-aware partitioning makes use of query workloads in order to partition RDF graphs. Ideally, the query workload includes representative queries extracted from a real-world or a synthetic/simulated query log.

Several RDF distributed systems rely on workload-aware partitioning such as Partout [27], chameleon-db [10], WARP [46], and WORQ [56]. Bonifati et. al [19] has conducted an analytical study of end users’ queries harvested from real-world query logs of SPARQL endpoints. According to the analysis of the graph structure of queries, tree-like shapes such as single triple patterns, chains, stars, trees, and forests are the most observed shapes. We consider the aforementioned observation especially star queries in family partitioning technique introduced in Section 3.6.

In our context, workload-aware partitioning could be seen as a form of “caching”, where subgraphs containing a superset of or exactly the results of particularly common sub-queries could be stored as separate partitions. However, in order to make use of such caching, complex queries would need to be analyzed whether they contain any of these “cached” subqueries or respectively subqueries subsumed by the cached queries. Since such a form of partitioning is rather related to index-learning from query logs, a concrete formalization depends on formalizing/extractable common query patterns from such query logs. We see various options here and consider them as somewhat complementary and orthogonal to our current work. For instance, the answers of repetitive queries can be precomputed and stored within dedicated partitions, that can be shipped directly to clients. This approach serves to mitigate the computational load imposed by recurrent queries [57]. Bonifati et al. [18] observed that robotic queries are frequently duplicated and the server computation can be reduced by materializing partitions for such queries. In the present paper, we restrict the scope to partitioning definable by the (characteristics of the) graph only. We therefore leave a concrete formalization/implementation of partition-based LDF following this idea to future work.

3.5.K-way partitioning (KP)

Similarly, K-way partitioning is not directly amenable to our framework: K-way partitioning algorithms, such as [50] strive to partition the graph into roughly equal-sized smaller graphs with the intention of minimizing the number of edges linking vertices from different partitions and thus could be viewed rather as a “clustering” technique for RDF graphs than partitioning based on/or specifically used for evaluating particular query patterns. As such, we also leave it open for future work on how/whether such techniques could be used for computing a partitioning G that allows deriving an easy-to-compute selector function σ.

3.6.Family-based partitioning of RDF graphs

After having discussed various existing partitioning techniques, primarily in the context of single triple queries, we herein would like to focus on a novel partitioning technique, that we previously introduced [15]. The overall idea of this partitioning technique is to serve partitions that cater for efficient evaluation of star-shaped (sub-)queries on the client-side, somewhat orthogonal to the above-mentioned SPF LDF interface on the server-side.

The intuition here is that real-world RDF graphs commonly exhibit an inherent structure due to the recurring occurrence of identical subject descriptions forming such common star-structures, i.e., many subjects of the same type share the same combinations of predicates. The assumption here is that in real-world RDF graphs, subjects with similar characteristics are described in the same fashion forming such common star-structures, i.e., many subjects of the same type share the same combinations of predicates. For instance, predicates describing Films (e.g., director, starring, launchDate, language, etc.) are different than those describing Persons (e.g., birthday, nationality, etc.) in DBpedia. In the literature, so-called characteristic sets [29,62] have been defined to capture these latent structures that eventually construct a “soft schema” from the entities that are semantically similar in a graph.

The structures described by Neumann and Moerkotte [29,62] are effectively represented using the concept of characteristic sets, commonly referred to as predicate families [26] (or simply families). We define the predicate family of a subject s, F(s), as the set of predicates related to the subject s, that is:

Analogously, we denote as F(G) or just F, to the set of all different predicate families occurring in G, as follows:

Indeed, predicate families imply a partitioning

We will refer to this partitioning as family-partitioning; slightly abusing notation we will simply write Gi for GFi in the following. Next, the admissible queries for family-partitioning are star-shaped query patterns, i.e., BGPs composed of k triple patterns form Q={(s,pi,oi)|1⩽i⩽k,s∈V∪U,pi∈U,oi∈V∪U∪L} with a single common subject s, where

Obviously, for any star-shaped query, σ(G,Q) contains all relevant triples from G to compute the answers.

Fig. 1.

KG example.

To illustrate the previous definitions consider the KG G shown in Fig. 1, and the predicate families shown in Fig. 2. Following the definition of predicate family in Eq. (8), the subjects s1 and s2 belong to the same family F1, as they have the same predicates. The subject s2 belongs to family F2. For the KG G, there are two families denoted F(G), i.e., F1 and F2. Lastly, each of these families induces a partition over G. For example, GF2 contains all the triples of subjects that belong to family F2, which in this case is triples t8 and t9. Lastly, the set of partitions computed for G, denoted G are GF1 and GF2.

Fig. 2.

Predicate families and typed families for the KG shown in Fig. 1.

In our concrete implementation in Section 4, we will also exploit the fact that predicate families or characteristic sets as the basis for family partitioning have been used successfully for query execution and join evaluation: the ability of characteristic sets to provide an inherent partitioning of an RDF graph has been utilized for (i) cardinality estimation [29,62] for SPARQL join optimization, (ii) improving RDF graph compressibility [43], and (iii) building an indexing scheme such as in AxonDB [60] which extends the notion of characteristic sets also to object nodes to speed up SPARQL query performance of AxonDB.

3.7.Typed family-partitioning

While – as we will see – family-partitioning provides a solid basis for partition-based LDF, unfortunately, family partition sizes can be significantly skewed for very popular classes (with a large number of instances), or, respectively, very large partitions could be further subdivided by the different (sub-)classes occurring for subjects. For instance, common attributes {rdf:type,:director,:starring} for subjects of the class Film, would also occur for each of the subclasses of Film. Intuitively, one can further subdivide each family partition “horizontally”, by the different rdf:types per subject. Further, we note that, based on observations of query logs for common public SPARQL query services, a large number of user queries include rdf:type predicates with a bound object: to back up this claim, we analyzed the real-world DBpedia LSQ [67] query log and found out that the percentage of queries with at least one star query with a rdf:type predicate with a bound object is 88% (excluding single triple queries).

Based on these observations, we propose an extension of family-based partitioning, called typed family-partitioning. Assuming (without loss of generality) that the set of class URIs and predicate URIs are disjoint,88 we can extend the concept of (predicate) families to typed families as follows:

Analogously, we extend the other notions from above, i.e., the set of typed families for a graph G:

To illustrate the previous definitions consider the KG G shown in Fig. 1, and the typed families shown in Fig. 2 Following the definition of typed-family in Eq. (12), the subject s1 belongs to family F1typed, the subject s2 belongs to family F2typed, and the subject s3 belongs to family F3typed. Note that in predicate families, the subjects s1 and s2 were in the same family; this is no longer the case, as their set of classes is different. For the KG G, there are three typed families denoted Ftyped(G), i.e., F1typed, F2typed and F3typed. Lastly, each of these families induces a partition over G. For example, F2typed contains all the triples of the subject s2, which in this case is triples t8 and t9. Lastly, the set of partitions computed for G, denoted G are GF1typed, GF2typed, and GF3typed.

4.1.Design and overview

smart-KG⁺ (cf. Fig. 3), which extends the original approach presented in [15], combines shipping HDT compressed family partitions with the shipping of intermediate results from evaluating a given sub-(query) over the existing LDF interfaces. As such, smart-KG⁺ relies on both shipping intermediate results from executing single-triple patterns using a brTPF LDF interface on the server, as well as using a (typed) family-partition-based LDF interface for star-shaped subqueries (which will be evaluated on the client side, based on the shipped partition). The rest of SPARQL complex patterns other than triple or star-patterns will be evaluated on the client side.

Fig. 3.

Overall architecture for the smart-KG⁺ client and server.

Initially, the smart-KG⁺ server constructs the family-based partitions (cf. Section 4.2 see the practical partition generator) for a given knowledge graph. The generated KG partitions are materialized as HDT files in the storage module together with family catalog that summarizes metadata information about the KG partitions including structural and statistical metadata. In addition, smart-KG⁺ API offers access to the KG based on two operators: one to execute a single triple pattern and the other to ship the requested partition to smart-KG⁺ client.

Upon receiving a BGP Q from smart-KG⁺ clients, the smart-KG⁺ server decomposes the input query into a set of o star-shaped subqueries where the server query planner devises an annotated query plan Π that decides for each pattern whether to be executed using brTPF or partition shipping. The client then evaluates the annotated query plan received from the server based on the specified subquery ordering.

As a side note, getting back to our original formalization of LDF and the fact that we do not consider “paging” (Φ) in relation to partition-based LDF: note that it would not make sense to decompose family-based partitions into chunks since chunking up the HDT-compressed partitions would require decompression.

4.2.smart-KG⁺ partition generator

In this section, we detail how the smart-KG⁺ server, upon loading an RDF KG, processes it into partitions G1,…,Gm per family, as described in Eq. (15) and stores those partitions as HDT compact files format. In practice, however, real-world RDF graphs such as DBpedia and Yago can potentially generate a relatively large number of partitions due to the high semi-structured nature of these RDF graphs. Thus, we introduce the concept of predicate-restricted families, where we control some particular predicates during the process of generating families.

Predicate-restricted families. Let us consider a restricted set of predicates, PG′⊆pred(G). The predicate-restricted family of a subject s w.r.t. PG′, denoted F′(s), is defined as F′(s)=PG′∩F(s).

Analogously, we denote as F′(G)={F1′,F2′,…,Fm′′}, or just F′, the set of different predicate-restricted families for G, where m′=|F′(G)|. These families correspond to a set G′={G1′,G2′,…,Gm′′} of partitions of a subgraph of G based on the PG′-restricted families, with

The prior definitions carry over to predicate-restricted typed-family partitions and typed-partitions, i.e., F′typed and GFi′typed can be defined analogously, where we additionally restrict the classes by a set CG′. Note that, however G′ is no longer a full cover of G, but the graph G′=∪Gi′ only contains the “projection” of G to PG′, with the intention that predicates other than PG′ (or, resp. classes other than CG′) are delegated to brTPF.

Serving predicate-restricted families allows a smart-KG⁺ publisher to select PG′ (and CG′) depending on (i) the cardinality of the predicates (i.e. the number of occurrences in the graph), and (ii) the importance of predicates (and combinations) in actual query workloads. We will describe a concrete method to pick PG′ (and CG′) based on the cardinality of predicates and classes in Section 4.2.2.

4.2.1.Family grouping

Relying on restricted families enables the publisher to control the number of generated families and reduce the generation of infrequently queried families to some degree, however, the number and the size of partitions are still driven by entities’ distribution in the graph. In practice, many RDF graphs are skewed in the sense that there exist “dominant” families with large corresponding partitions, as opposed to several small, very similar families of much smaller sizes. This phenomenon arises due to the semi-structured nature of RDF, where entities of the same type could potentially have different attributes representing diverse relationships. Thus, alongside predicate-restricted families, the introduced partition shipping strategy merges (i.e. groups) similar families into a single family. For instance, all disjoint families containing a certain set of predicates e.g. F1={foaf:name,dbo:birthPlace,dbo:almaMater} and F2={foaf:name,dbo:birthPlace,dbo:occupation} can be merged into a single family F{1,2}={foaf:name,dbo:birthPlace}. The intuition behind family grouping is to materialize families representing overlapping predicate subsets which may be frequently present in query patterns as predicate families. Therefore, smart-KG⁺ server can send a single compact partition representing the smallest merged families required to resolve a star query pattern rather than serving the union of partitions which have two main downsides: first, it requires on average extra data transfer due to shipping needless predicates to the star query pattern; second, it requires to locally union the shipped partitions on the client-side. While typed-based families can in theory also be grouped, a preliminary study of ours showed that considering different combinations or even hierarchies of classes would drastically increase the number of materialized partitions, which might benefit only a set of specific queries. For this reason, in the remainder of this work, we focus on only grouping predicated-restricted families.

Note that, in order to define the notion of a merge of families and respective (predicate-restricted) partitions we refer to particular families in F′(G)={F1′,F2′,…,Fm′′}, by their index {1,…,m′}. Using this notation, formally, for an index set I∈2{1,…,m′}, we define the merge FI′ of the set of families {Fj′|j∈I} as follows:99

(18)FI′=⋂i∈IFi′

Analogously, the corresponding merged partition GI′⊆⋃i∈IGi′ can also be defined as:

(19)GI′={(s,p,o)∈G|FI′⊆F(s)}

if G1′ and G2′ are merged into G{1,2}′, then to evaluate a query pattern that involves the predicates foaf:name and dbo:birthPlace, we only transfer G{1,2}′ rather than G1′∪G2′. Note that the most important consideration is that all the subjects are a matching result for those queries only involving the predicates in G1,2′.

Following similar premises, Gubichev and Neumann [29] establish a hierarchy of characteristic sets, in each step removing one element of the set and keeping only the one that minimizes the query costs (i.e. cost can be understood as cardinality, in this context). For instance, in the previous example, the approach by Gubichev and Neumann will inspect all combinations of two predicates, F{1,2}1={foaf:name,foaf:birthPlace}, F{1,2}2={foaf:name,dct:title}, etc., to select the one with smallest cardinality, e.g. F{1,2}2, for query planning.

We use a similar idea, but the main differences with the previous work are that (i) we do not compute all predicate subsets of a given family (this is mainly to estimate the cost of join operations [29]) but only those subsets that represent merges, corresponding to non-empty intersections with other families, and (ii) we keep all these intersections in a map, irrespective of their cardinality.

Algorithm 1:

Family grouping

To create the map of merged families for all potentially non-empty intersections of sub-families, we start from F′(G)={F1′,…Fm′}, and iteratively construct a partial map μ such that, given a set of predicates f, μ(f) returns (whenever f corresponds to a non-empty intersection) a set of indexes of all original families that contain subjects contributing to f, as shown in Alg. 1. We initialize μ with F′(G) (lines 2–3), and then, iteratively, until μ does not change anymore (lines 4–13), create mappings (corresponding to a merged family) collecting all indexes, for each non-empty intersection of families (lines 9–12). If there already is a (merged) family corresponding to the intersection found, i.e., f∪g appears already in the domain of μ (line 9), then also the corresponding index(es) are considered (line 10) and the mapping is updated, otherwise, a new mapping is created (line 12). Note that, as opposed to this pseudo-code, our actual implementation is using a hashmap for the (merged) families and avoids revisiting the same intersections repeatedly.

Then, μ(·) is used to compute the partitions served by the smart-KG⁺ server, denoted Gserv, where G′ is replaced with a set of partitions obtained from the merged families:

(20)Gserv={Gμ(f)′|f∈dom(μ)}

Note that the elements in Gserv are no longer non-overlapping, i.e., formally, they are not partitions anymore but fragments of the graph G. However, for the sake of readability, we abuse notation and refer to these fragments as merged partitions (or simply partitions). The advantage of serving these merged partitions is that the client can determine a unique minimal matching partition among Gserv to answer a query using the mapping μ.

4.2.2.Family pruning

Note that, in practice, the cost of fully materializing the partitions generated from all potential merges (intersections) of all families in G could be prohibitive. For instance, as we will show in our evaluation, in the DBpedia graph, a naive merge would create +600k partially very large families, which are unfeasible to serve.

To this end, we present a family pruning strategy for restricting the number of materialized partitions, where we (i) restrict considered predicates in PG′ based on their cardinality, (ii) restrict considered classes based on their cardinality in generating typed families, (iii) avoid the creation of small families that deviate only slightly from other overlapping, “core” families, and (iv) avoid materialization of families over a certain size.

(i) Restrict predicates based on cardinality. The cardinality of predicates is a key factor in determining the number and size of shipped partitions. Therefore we distinguish between infrequent and frequent predicates in the KG.

Infrequent predicates are those that occur rarely in the KG compared to the most commonly occurring predicates. Infrequent predicates may be scattered across various subjects in the KG, leading to the creation of multiple small families. In this case, a TPF/brTPF call efficiently evaluates a single triple pattern with an infrequent predicate without the need to transfer large intermediate results (i.e. unnecessary materialization of small family partitions).

Frequent predicates can be part of almost all families such as dbo:wikiPageExternalLink in DBpedia leading to an undesirable increase in the size of each family, especially if they are rarely mentioned in queries.1010

Note specifically that although rdf:type is a typically frequent predicate, we do not exclude it at this point, as we will tackle this issue separately in (ii), in the handling of typed partitions.

To control predicates cardinalities, we use thresholds τplow, τphigh with 0⩽τplow<τphigh⩽1, to delimit the minimum and maximum percentage of triples per predicate, and define PG′ accordingly based on these two thresholds:

(21)PG′={p′∈pred(G)|τplow⩽|(s,p′,o)∈G||G|⩽τphigh}

(ii) Restrict classes cardinality based on cardinality to generate typed-families. As discussed when introducing typed partitions, rdf:type is a natural horizontal partitioner for predicate families, which plays an essential role in reducing the size of the shipped families; plus, as also mentioned above, rdf:type is a heavy hitter in real-world queries, since it is a frequently used predicate in log queries as shown in Table 4.

Therefore, similar to issue (i), the cardinality of classes contributes to the number and size of the shipped partitions: firstly, rare classes occurring as rdf:type objects in triple patterns are by nature selective: such triple patterns are better handled through a TPF/brTPF/SPF call without shipping a typed family; secondly, frequent classes can be potentially present in many of the families (for instance owl:Thing) and, in practice, are rarely used in queries.1111

We address the aforementioned issues, similar to issue (i), by excluding these classes, and maintaining minimum (τclasslow) and maximum (τclasshigh) thresholds for the percentage of triples per class. We rely on these two thresholds to define the set of classes CG′ for restricting the created typed partitions:

(22)CG′={c∈types(G)|τclasslow⩽|(s,rdf:type,c)∈G||G|⩽τclasshigh}

(iii) Avoid the creation of small families. To address this issue, we aim at considering only “core” families for the partition merging process, i.e., we select predicate combinations (i.e. families) that are used by a proportionally large number of subjects, above a threshold αs. That is, we define these core families as

(23)Fcore′={Fi′∈F′||subj(Gi′)||subj(G)|⩾αs}

with the respective index set Icore={i|Fi′∈Fcore′} and predicate set Pcore′={p∈Fi′|Fi′∈Fcore′}. Intuitively, these core families represent the structured parts of the graph, i.e., star-shaped sub-graphs where entities are described with the same attributes.

(iv) Avoid the creation of large families. Finally, we avoid the materialization of overly large (e.g. hundreds of millions of triples in DBpedia) merged partitions GI with size above a threshold αt. In order to only take core families into account for the creation of partitions, and limit merged families to sizes below αt, it is sufficient to modify Equation (20) as follows:

(24)Gserv=Gμ(f)′f∈dom(μ)∧μ(f)∩Icore≠∅∧∑i∈μ(f)|Gi′|⩽αt︸Merged partitions∪{G{i}|Fi′∈F′}︸Non-merged partitions ∪{Gi,class|class∈CG′,Fi′∪{class}∈Ftyped}︸Typed partitions

In the conditions in the first part of Equation (24), line 2 addresses issue (iii)1212 and line 3 addresses issue (iv).1313 The second part ensures that, despite pruning, the non-merged partitions of families in F′ remain being served.

Due to these pruning steps, no longer all the partitions corresponding to families in dom(μ) will be materialized in Gserv. Therefore, in practice, we define another mapping function, μG, that allows us to directly map families from dom(μ) to “minimal” sets of matching partitions in Gserv. In practice, we compute the partitions Gserv along with μG in one go. That is, we build a mapping μG:dom(μ)↦22{1,…,m} that maps a family f to a set of index sets {I1,…Ik} representing (lists of) materialized matching partitions, i.e., where μG(f)={I|GI′∈Gserv≺(f)}. For Gμ(f)′∈Gserv, i.e., if the respective partition is materialized, then μG(f)={μ(f)}. In this case, Gserv≺(f) is defined as: let Gserv(f)={GI′∈Gserv|f⊆μ−1(I)} be all materialized partitions matching a family f, then Gserv≺(f) is the ≺-minimal subset of Gserv(f) with ≺ defined as: GI1′≺GI2′ iff μ−1(I1)⊂μ−1(I2). That is, as the partition merging can result in no longer disjoint partitions in Gserv, the intuition is to pick, at query time, the partitions that are “subset-minimal with respect to their corresponding families”. In practice, smart-KG⁺ materializes the partitions in Gserv as HDT files.

Fig. 4.

Example of processing a SPARQL query with the smart-KG⁺ client.

4.3.smart-KG⁺ query processing

In this section, we detail how the smart-KG⁺ server and client work together to process SPARQL queries. In particular, we describe how the query processing is performed on the server-side and on the client-side.

4.3.1.smart-KG⁺ server

In this section, we describe how smart-KG⁺ server query planner creates a query execution plan for a submitted BGP. In addition, we detail how smart-KG⁺ server enables the clients to access the partitions constructed by the partition generator described in Section 4.2 and to evaluate single triple patterns using brTPF.

Query decomposer First, smart-KG⁺ splits parsed Basic Graph Patterns (BGPs) into stars as follows: given a BGP Q, with subjects subj(Q), a decomposition Q={Qs|s∈subj(Q)} of Q is a set of star-shaped BGPs Qs such that Q=⋃s∈subj(Q)Qs:

(25)Qs={tp∈Q|tp=(s,p,o)}

Analogous to graphs, we can also associate a family to each star query Qs:

(26)F(Qs)={p|∃o:(s,p,o)∈Qs,p∈U}

Typed-families for a query Ftyped(Qs) can be computed analogously to graphs.

Given the SPARQL query in Fig. 4a, the BGP is decomposed into Q={Q?film,Q?actress,Q?city} around the three subjects (cf. Fig. 4b). Each of the star families F(Qs) that can be mapped to existing predicate families in dom(μG) on the server that has a non-empty answer. For example, Q?film = {(?film, dbo:starring, ?actress), (?film, foaf:name, ?filmName), (?film, rdf:type, dbo:Film)} has F(Q?film)={dbo:starring,foaf:name,rdf:type}. Note that Q?film contains rdf:type which will be distinguished by the query planner and optimizer while devising the query plan.

Algorithm 2:

Query optimizer and planner: optimizePlan

Shipping-based query planner & optimizer In smart-KG⁺, the query planner and the optimizer are executed at the server-side to provide more efficient query plans based on pre-computed characteristic set cardinality estimations and the server’s partition metadata. When the smart-KG⁺ server receives a request Plan(Q) for a BGP Q from a client, the server query planner devises an annotated query plan to specify which interfaces are used per subquery. The interfaces are denoted with superscripts to represent triple pattern shipping using brTPF and partition shipping using SKG to describe the interfaces as Qsinterface.

Given Q, PG′, and CG′ as input, the query optimizer devises a query plan ΠQ where the resp. algorithm to compute Plan(Q,PG′,CG′) is shown in Alg. 2. If the estimated cardinality of a given star-shaped subquery Qs is zero (i.e., empty result set), then the result set of the query Q will be empty, therefore, the query planner returns an empty plan (lines 4–5). Then, the optimizer finds the star-subquery Qsi with the lowest cardinality estimation using the function card(Qs,ΠQ) (line 6); in our running example, this would order Q?actress, followed by Q?films, and lastly the triple pattern in Q?city.

Next, Qsi is annotated with a label that corresponds to the interface that will be utilized to evaluate the subquery: SKG label and brTPF label. Therefore, the optimizer characterizes each Qsi to decide whether to use partition shipping or triple pattern (for parts) of Qsi, as follows:

Partition Shipping. Shipping relevant partitions to evaluate a star Qs∈Q requires considering the materialized partitions at the server. Since graph partitions are generated based on the pruned families (cf. Section 4.2), only stars with F(Qs)⊆PG′ can be fully evaluated by served partitions. Therefore, the optimizer partitions each Qsi∈Q into the disjoint sets Qsi′ and Qsi″, where Qsi′ is the part of the star that can potentially be evaluated over the served partitions (line 7), whereas the remaining triple patterns in Qsi″ are delegated to brTPF requests (line 8). Note that Qsi″ also includes triple patterns with predicate variables, i.e., p∈V. Then, optimizer checks (lines 9–12) for each triple pattern tp with rdf:type predicate whether the class o belongs to the restricted set of classes CG′. Note that this also captures the case with o∈V. In the negative case, there is no materialized typed-family partition to serve Qsi, therefore, this tp will be pushed to Qs″ to be evaluated using brTPF (line 11). Then, the optimizer considers heuristics that partition shipping is only followed if |Qsi′|>1 where Qsi′ is annotated with the respective label for partition shipping SKG (lines 15–16). As in practice, the transfer of graph partitions to resolve a single triple pattern usually takes longer than delegating to a brTPF request directly (line 18).

Triple Pattern Shipping. Qs with a single triple pattern, triple patterns with infrequent predicates, and triple patterns with predicate variables will be annotated with brTPF label (lines 17). These subqueries will be eventually evaluated using a brTPF request to the server.

Lastly, the optimizer reorders the triple patterns with the function reorder in the sub-plans based on their cardinality estimations; this allows for an efficient evaluation at the client side. Then, the optimizer attaches the sub-plans with the append function to build the final plan ΠQ. The resulting query plan ΠQ comprises sub-plans annotated with the corresponding shipping strategy. We describe a full annotated query plan as sequences of patterns being interpreted as left-linear query plans, that is, we write query plans that evaluate patterns as permutations of the decomposed stars in Q. For our example shown in Fig. 4a, the annotated plan could be written as Π=(Q?actress′SKG,Q?actress″brTPF,Q?filmSKG,Q?citybrTPF), describing an execution plan at the level of joining star patterns as follows: (((Q?actress′⋈Q?actress″)⋈Q?film)⋈Q?city). Figure 4c shows the shipping strategies for each sub-plan from our example. The query optimizer first starts with the subquery Q?actress which is the most selective subquery. For Q?actress, the optimizer creates Q?actress′SKG⋈Q?actress″TPF, as the triple pattern tp4 in Q?actress is evaluated using triple pattern shipping as the optimizer determined that the predicate dbo:wikiPageExternalLink is not in PG′. Next, the query optimizer evaluates Q?film via partition shipping on the client based on a family-based partition. Finally, Q?city is added to be executed as a single triple pattern using brTPF.

Server operators The smart-KG⁺ server provides operators to ship partitions and their metadata, or to respond to brTPF requests. These operators are defined in the following interface calls to access a KG G:

• – A brTPF LDF API interface brTPF(Qs,Ω) which returns σbrTPF(G,Qs,Ω)=s(G,Qs,Ω), that retrieves the answers for a single triple pattern Qs while taking into consideration the attached bindings Ω, i.e., the smart-KG⁺ server returns the triples from G that match Qs based on brTPF requests.

• – A SKG LDF API interface SKG(Qs,∅) that handles star-shaped queries Qs and returns σSKG(G,Qs,∅)=σ(G,Qs), i.e., the set of typed-family partitions if exists, otherwise the family partitions, of which ⟦Qs⟧G can be computed and joined on the client-side.

• – Plan(Q) to create a query plan for the received BGP Q. Unlike the initial smart-KG⁺ prototype [15], where the query plan was inaccurately created on the client-side, we propose shifting the query execution planning from the client to the server to compute better query plans as the server has access to more accurate cardinality estimations to determine the order of stars and triple patterns.

4.3.2.smart-KG⁺ client

The primary focus of this work is on evaluating BGPs as the essential retrieval functionality of the SPARQL query language. However, our introduced interface is able to process a full SPARQL query including operators such as UNION and OPTIONAL, FILTER, etc., which are all evaluated locally on the client-side. Herein, we introduce the general approach for processing a SPARQL query, as follows:

• 1. Upon receiving a SPARQL query, the query parser translates the input query string into the corresponding SPARQL algebra expressions.

• 2. Initially, the client sends a request Plan(Q) to retrieve from the server an optimized query execution plan ΠQ for the extracted BGP Q.

• 3. The query executor evaluates the received plan and iteratively combines the results using a dynamic pipeline of iterators, following brTPF [37], where each iterator deals with a certain annotated subquery Qsc that request a partition or performs a brTPF request.

• 4. The results serializer translates the locally joined results into the specified format. Note that the downloaded partitions from the smart-KG⁺ server during query evaluation can be locally stored in the family cache to be reused in the upcoming queries.

We describe in detail the algorithms that implement the query executor in a recursive manner in Alg. 3 and Alg. 4. The function evalPlan recursively evaluates the received plan Π by traversing the left-tree of sub-plans (cf. Alg. 3). The query executor initially evaluates the first and most selective subquery Qs1c1 (line 1). Then, the algorithm traverses the rest of the plan (lines 2–6). The base case is when the plan is associated with a single star pattern Qsc (line 2). In this case, the executor evaluates the star using evalc(Qsc,Ω′) while considering the intermediate results from earlier subqueries Ω′ (for details, cf. Alg. 4). Otherwise, the query executor will recursively call the evaluation of the remaining subtree and join them with the set of bindings retrieved from the previous calls (line 5). The final output of the query executor is the query result set Ω of a given plan (line 6). In practice, the executor implements an iterator to push intermediate results of evaluating one sub-plan to the next operator in the plan. This allows the smart-KG⁺ client to incrementally stream query results once computed.

Alg. 4 presents the function evalc(Qsc,Ω′), which calls the corresponding interface (i.e. the respective smart-KG⁺ server operators for the shipping strategy determined by the server query plan). The first case c=SKG is to evaluate a star pattern using a shipped partition on the client-side. The second case c=TPF involves calling the brTPF interface which directly returns the result bindings. In the following, we explain the two cases in detail:

Case SKG. Each sub-plan QsSKG is evaluated (cf. Alg. 4, lines 2–5) by retrieving HDT partitions using the server operator for partition shipping SKG(Qs,∅). This operation returns a set of partitions G∗ which is either a set of family-based partitions or a set of typed-family partitions (cf. Alg. 4, line 2). The query executor evaluates each triple pattern tp of the star pattern QsSKG (lines 4–5) over the partitions (using the SPARQL algebra union operator when several partitions are retrieved). The results of each tp are joined to produce the final results of the star pattern.

Case: brTPF. Each sub-plan QsbrTPF involves a single triple pattern which is executed by calling the server operator brTPF(tp, Ω′) which is a brTPF interface that directly returns the result bindings (cf. Alg. 4, lines 6–7).

Algorithm 3:

Query executor: evalPlan

Algorithm 4:

Query executor: evalc

The evaluation of SPARQL BGP queries with smart-KG⁺ is correct, as stated in the following proposition. The proof can be found in Appendix A.

Proposition 1.

The result of evaluating a BGP Q over an RDF graph G with smart-KG⁺, denoted smart−eval(Q,G), is correct w.r.t. the semantics of the SPARQL language, i.e., smart−eval(Q,G)=⟦Q⟧G.

5.1.Experimental setup

In this section, we present the experimental setup, including the characteristics of the compared systems, the benchmark KGs, the query workloads, the hardware and software configurations, and the evaluation metrics.

5.2.Creation of family-based partitions

Table 5 presents the thresholds used for creating the family-based partitions for each KG G. Note that the configuration (αs,αt,τplow,τphigh,τclasslow,τclasshigh)=(0,|G|,0,1,0,1) corresponds to full materialization of all families. For the smallest dataset WatDiv-10M, we tested this configuration. Then, we assess the impact of the smart-KG⁺ family pruning strategies with the following set up. We empirically set αt=0.05|G| for all datasets, to avoid large families containing more than 5% of the triples in G. Then, we use αs=0 for WatDiv to allow all families (even small ones), but αs=0.01/100 for DBpedia to create families where the predicates appear in at least 0.01 of the subjects in the graph. Likewise, we fixed τplow=0.01/100 for all G, while we set τphigh=0.1/100 for DBpedia, as we empirically tested that the resultant predicate set filters out both infrequent and heavy hitters. We refer to [15] for a study on DBpedia on the number of families with different values of our parameters. Lastly, for typed families, we tested the parameters τclasslow=0.01/100 and τclasshigh=0.1/100 for DBpedia, applied to 376 classes selected based on an empirical test that the resultant class set filters out heavy hitter classes as well as infrequent classes.

For each graph G, Table 3 also shows the number of restricted and core predicates (|PG′|, |Pcore′|), core families, |Fcore′|, and the materialized partitions after grouping/pruning, |Gserv|, as well as the total computation time (including family computation, pruning, and partition generation). Table 3 also shows that |Fcore′|, |Gserv|, and the computation time are sub-linearly increasing with the graph sizes. In WatDiv, Fcore′=F′(G), whereas in DBpedia, the initial number of PG′-restricted2121 families |F′(G)| is >600K: the family pruning strategy allows smart-KG⁺ to identify |Fcore′|=35 core families, which are merged into ∼30K materialized partitions. We provide an analysis of the impact/coverage of different parameter values for the case of DBpedia in our online repository¹⁴. Lastly, Appendix B presents the results of family creation in further real-world KGs, i.e., Yago2, WordNet, and DBLP.

5.3.Ablation study: Assessing the impact of the smart-KG⁺ components

In this section, we conduct an ablation study to evaluate the performance of each individual contribution made to smart-KG⁺. The goal is to gain insights into the significance of each change introduced w.r.t. the earlier version. For this purpose, we developed three configurations of the interface:

To assess the performance of these configurations, we conduct a performance evaluation using watdiv-btt and watdiv-sts on watdiv10M; results are presented in Table 6 and Table 7.