While mobile computing domains have illustrated the usefulness of mobile semantic data, improvements in mobile hardware are paving the way for local semantic data access. To support this, a number of tools have been developed for storing, querying and reasoning over local semantic data. However, recent benchmarks have shown that mobile hardware still imposes limitations on efficient local data querying. Additionally, mobile scenarios pose unique challenges due to their dynamic nature; making it difficult to replicate semantic data a priori for local querying. In this paper, we propose a graphbased query distribution approach, which efficiently distributes query execution across configured remote datasets. Importantly, our approach aims to identify subqueries that can be outsourced to remote datasets, thus reducing local joining work.
As shown by the Linked Open Data cloud [
For some time now, mobile devices have met the hardware requirements for managing and
querying Semantic Web data. Reflecting this evolution, various mobile computing domains
currently leverage semantic data, including augmented reality [
In particular, subqueries may be outsourced to relevant remote datasets, relieving the
mobile client of join processing. We also note that server hardware hosting these datasets are
better equipped, both hardware-wise and regarding data access optimizations (e.g., join
indices), to execute these subqueries to begin with. Moreover, less intermediate results are returned
to the device, reducing bandwidth usage. To allow identifying subqueries that are resolvable
by a particular dataset, we propose indexing graph patterns (i.e., graph structure with only
predicate edges) found in the dataset. For a given query and set of configured datasets, suitable
subqueries are found by determining subgraph isomorphism between the query subgraphs and
dataset graph patterns. Although subgraph checking is an NP-hard problem, it has reasonable
execution times for many real-world scenarios and is often used in graph databases [
In this paper, we present a graph-based, semantic query distribution approach, which outsources suitable subqueries via graph pattern indexing and matching. We apply a custom, back-tracking subgraph isomorphism algorithm, which is able to identify subqueries suitable to be executed on a particular remote dataset. We present an evaluation comparing our system to a predicate-based approach, using a real-world dataset.
Section 2 discusses the indexing of dataset graph patterns. Section 3 presents our query distribution approach. Section 4 shows an initial evaluation of our approach, while Section 5 discusses related work. Section 6 presents conclusions and future work. 2
To identify dataset graph patterns, our system first collects instance RDF graphs. Duplicate instance graphs and subgraphs are hereby ruled out by applying subgraph checks on the collected instance graphs, leaving only distinct graph patterns. Below, we show the pseudocode for this indexing step: 1. ← SELECT ∗ WHERE { ? s ? p ? o . }
← execute(q, dataset) 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
← [ 1] , 2) − 2 + 2 ℎ2 ℎ(
ℎ ℎ1,
ℎ2) ← _
ℎ ← ℎ ← ℎ + ℎ( ℎ − ℎ2, ℎ 2 ℎ 1 ℎ1) Code 1. Algorithm for extracting dataset graph patterns.
← 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. ! 27.
_
Lines 1-2 obtain all triples from the dataset. For each distinct result triple (lines 4-5), a new graph pattern is created (line 6), as well as a list of candidates for expansion, initially containing the result triple (line 7). Each candidate for expansion is added to the graph pattern (lines 8-9), and other triples linking to the current candidate (lines 10-11) are themselves added as candidates for expansion (line 13). This process continues until no more new expansion candidates are found, meaning a disjoint instance RDF graph has been identified.
Subsequently, the algorithm checks whether the collected graph is a subgraph of another, previously identified graph, or vice versa (lines 18-27). In case it is found to be a (non-proper) subgraph, the newly found graph is ignored (lines 20-22). In case a previously indexed graph is a subgraph of the new graph, the previous is removed & the new graph is added (lines 2425, 26-27). Else, the new graph is added to the index as a new graph pattern (lines 26-27).
In Section 3, we elaborate on the implementation of the is_subgraph function. We note that the matches function only considers certain types of links, to maximize the re-use of extracted graph patterns. Overall, the function may consider 4 links to extend an instance graph, as illustrated in Figure 1:
Two triples may be considered part of the same instance graph in case they represent a path (links (1) and (3), and if they share the same subject (link (2)) or object (link (4)). In practice however, we found that considering link (4) typically leads to cases where only a single (huge) graph pattern can be extracted (i.e., about the same size as the dataset). For instance, most resources will often be typed with owl:Thing, resulting in only one instance graph. Currently, we follow a pragmatic solution to this problem, by simply ruling out link (4); thus maximizing re-use of dataset graph patterns, and significantly reducing the size of extracted graph patterns. On the other hand, we note that this will lead to problems if the shared object itself is involved in other triples as subject. Tackling this issue more effectively is considered future work.
After extracting the graph patterns, they are added to an index keeping the graph patterns for each dataset. Ideally, the resource-intensive indexing process occurs on the dataset server, ruling out the need to communicate the entire dataset to another location. Subsequently, indexed graph patterns are communicated to the mobile systems, and updated each time significant changes occur that alter the previously indexed patterns. 3
Based on the dataset graph pattern index (see Section 2), query execution will be distributed across matching datasets. To cope with mobile device limitations, our main goal is to distribute coherent subqueries to relevant datasets, thus outsourcing the resource-intensive join work to 42. 43.
∷ true _ ( 1, 2)
Code 2. Custom, back-tracking subgraph isomorphism algorithm.
The compare function starts by checking for overlaps between the outgoing edges of n1 and n2 (neighbor_matches; line 22). In case n1 is not a leaf node and no overlaps are found, false is returned (lines 23-25). For each overlap, the function checks whether the e1 to-node is already mapped to a g2 node (line 30; to avoid infinite loops). If so, and if it was already mapped to the e2 to-node, edge e2 matches e1 (lines 37-38). If not, the e1 to-node is mapped to the e2 tonode (line 32), and the function recursively compares these two to-nodes (line 33). E.g., in case no overlapping edges are found, this call will return false; if n1 turns out to be a leaf node, it will return true. In case n1 and n2 recursively match, edge e2 matches e1 (line 33-34). If not, the previously assigned mapping is removed (line 35) and another edge e2 (if any) is tried2. Again, at this point, the algorithm could return false if no matches are found for e1 (at line 40), since all e1 edges need to be matched for a subgraph match. However, to allow identifying partial matches (i.e., involving a subgraph of g1), all e1 edges need to be tried; even if some have already failed.
The neighbor_matches function returns true in case n1 is a leaf node; since this means the n1 subgraph has been checked completely. Else, it collects the overlaps between the outgoing edges of e1 and e2: whereby two edges match in case both of them have the same label; either of them represents a variable; or the e1 label represents a subproperty of e2. If no matches are found for any edge e1, the function returns false; else, it returns the overlapping edges.
To track the largest matching subgraph of g1, a listener is notified when two edges are being compared (line 29), when two nodes are finished comparing (line 42), when a g1 node comparison failed (lines 11, 15) and when comparison is done (lines 7, 19). Upon finishing the subgraph comparison, the listener records the match by assigning dataset associated with the dataset edge to its matching query edge; together with an ID uniquely identifying the subgraph comparison3. 3.2
To achieve virtual data integration, query execution is distributed across the configured datasets, and the results integrated locally. In its simplest form , this involves splitting up a query into its smallest units (i.e., triple patterns), executing them on each individual dataset, and combining the results. In doing so, a query distribution system ensures that all results are returned, even for queries that are not resolvable by any single dataset. Initially, such a Query Distribution Plan (QDP) consists of nm query sets, each representing a particular result integration:
= [{ 1 → , … , → , … , → }, … ]
), 0 < < , 0 < , , <
2 Multiple e2 matches for e1 are possible, and vice-versa (e2 is only matched to one e1 at a time). 3 This unique ID is required by the query distribution algorithm (see Section 3.2).
Where → stands for an atomic subquery, i.e., executing a single triple pattern on dataset ; a set of subqueries between accolades forms a query set, standing for a particular integration of results; and the set of query sets make up the QDP, standing for all possible result integrations.
In our query distribution approach, graph patterns from an incoming query are compared to the set of dataset graph patterns (see Section 2), using subgraph isomorphism checks. After these checks, matching datasets are assigned to the query graph edges (see Section 3.1, last paragraph), indicating which query triples (each corresponding to an edge) are collectively resolvable by particular datasets. Based on these results, given a query set, multiple ti matched to the same Dy (during the same subgraph check) can be grouped into the same subquery: = { 1 → , … , , → , … , → } ), = ( ), 0 < , , < , 0 < , , <
Formula 2. Grouping subqueries in query sets based on their shared dataset.
In the query shown in Figure 3, subqueries 1, 2, 3 → , 2, 4 → , 1 → and 5 → can be distinguished into their respective query sets.
In this process, it is important to consider the particular subgraph check in which the matching dataset was found. For instance, consider the following cases:
In case (a), part of the query (t1, t3) was matched to a particular graph pattern (1) from A during one subgraph check, while the remainder (t2) was matched to a different graph (2) from A during another check. However, these two dataset graph patterns are disjoint; no single instance graph exists that covers both graph patterns4. As such, this particular query set will never yield any results, and need to be removed from the QDP. Case (b) illustrates that this reasoning is only valid when considering connected query triples (i.e., with shared variables). 4 Else, they would have been combined during the graph extraction process (see Section 2). Here, an intermediate query triple t2 is executed on dataset B, which may yield results that connect t1 with t3 ; in other words, an instance graph, integrated from both datasets, may exist that connects all 3 query triples.
Further, we note that triple patterns executed on the same dataset, but not sharing any variables, should ideally be kept separate. Putting these into the same subquery will lead to a Cartesian product, resulting in a huge number of results returned by the remote dataset; whereas the associated local computational work is comparatively low.
Below, we show the pseudocode for post-processing the QDP, based on subgraph matches: 1. 1: 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
2:
Code 5. Processing the QDP based on subgraph matching results.
For each query set, query triples are grouped into subqueries based on assigned dataset and shared variables (lines 1-2). If one of these subqueries involves two query triples, assigned to the same dataset but associated with a different dataset graph pattern (lines 4-6), the query set is removed from the QDP (lines 7-8).
After generating a QDP, it is passed to the execution engine. For each subquery, the engine creates and executes a SPARQL query on the associated remote dataset. To integrate subquery results from a single query set, we apply a hash join. Results from multiple query sets are combined via a union operation. Since the same subquery-on-dataset combination will occur in multiple query sets (see Formula 1), the engine caches previous results for later re-use. 4
This section presents a preliminary evaluation of our query distribution approach. In our evaluation, a client app poses a query that requires data from two datasets to be integrated. To illustrate the usefulness of graph-based query distribution, we compare our approach to a straightforward predicate-based approach, which distributes incoming queries solely based on query predicates and indexed dataset predicates. For each query triple, the approach checks which datasets contain its concrete predicate; and then executes the query triple (potentially grouped in a subquery) on the found datasets.
Below, we elaborate on the evaluation setup, including current implementation components. Then, we discuss the results of each query distribution approach. 4.1
Dataset
Query 1. SELECT ∗ WHERE { 2. 3. 4. 5. 6.
We ran all experiments 10 times, and took the average of the performance times. Below, we elaborate on other relevant aspects: datasets are relatively small, we will show that these a) already result in non-trivial execution times and b) indicate significant differences in performance between the evaluated approaches. Respectively, 7 and 2 distinct graph patterns were found in the extracted DBPedia and Our evaluation executes the following query, selecting the label, type, coordinates and website of geographic entities (namespaces omitted for brevity): ? ? ? ? ?
. }
This query returns 51 results on the integrated dataset.
Dataset
Mobile
Both datasets were made accessible using the Apache Fuseki [
For the predicate-based approach, we consider two configurations: a configuration where joins are not outsourced (no-outsource); and a configuration where, per query set, query triples assigned to the same dataset are grouped into the same subquery (outsource). In Table 1, we indicate the number of query sets, remote query executions and total number of individual query results to be joined.
# query sets # query exec. # indiv. results
The overall number of query executions is relatively low, since an internal cache is kept to avoid re-sending the same subquery (see discussion after Code 5). We also note that, when outsourcing queries, additional subqueries will be constructed. Therefore, the potential for reusing cached results is reduced, and the overall number of query executions is comparatively increased (see predicate-based > outsource column). However, the local join work is reduced, as illustrated by the total number of individual query results.
Table 2 shows the performance results, where ID stands for identifying relevant datasets and QDP for constructing the dataset (see Code 5):
Since less queries are sent to the datasets, executing queries takes much less time for graphbased. Since pred-based > outsource and graph-based both outsource join work to the remote dataset, locally joining results is much faster as well. Despite its extra overhead when identifying relevant datasets and constructing the QDP, our graph-based query distribution approach outperforms either predicate-based approach.
Creating the graph index and predicate index takes ca. 4431ms and 80ms, respectively. We note that that the graph creation process only needs to be applied in case the dataset contents are updated significantly, causing a change in its graph patterns. 5
The Distributed ARQ (DARQ) [
The approach in [
In this paper, we presented a graph-based query distribution approach, focusing on outsourcing subqueries to relevant remote datasets. We presented a mechanism for indexing graph patterns in remote datasets; a custom, backtracking subgraph isomorphism algorithm; and our graph-based query distribution mechanism. Our evaluation shows that our approach has the potential to significantly reduce the number of queries to be sent to remote datasets, as well as minimize the resulting local join work.
Many avenues for future work exist. By keeping summary data on graph pattern nodes (cfr.
[
To allow identifying partial subgraph matches, our subgraph checking algorithm drops a
number of optimizations that may result in serious performance gains. Studying other methods
of efficiently determining partial query matches is future work. Furthermore, although
subgraph isomorphism checking is known to be an NP-hard problem, many algorithms have been
proposed over the years that solve it in a reasonable time [