The exact evaluation of queries over RDF data has been extensively studied. However, in a wide array of applications, RDF queries do not even terminate, due to performance reasons. To address this, in this demonstration, we present PING, a novel system built on top of Spark, which allows to progressively answer RDF queries. PING first builds a hierarchical schema structure, which is used for efective data partitioning, sub-partitioning, and indexing. Then, it employs a novel RDF query evaluation algorithm that directly locates the diferent levels of the hierarchy required for query answering. This also enables answering queries progressively, by sequentially visiting the various hierarchy levels. The demonstration explains the novelty of our system and shows its efectiveness and the eficiency, on both exact and progressive query answering (PQA).
CEUR ceur-ws.org
Graphs are simple yet powerful abstractions for representing and analyzing semantic relationships between real-world objects. Still, graph ecosystems face key challenges, such as data model heterogeneity and query answering eficiency on large, highly interconnected datasets.
The problem. While exact query answering on RDF data has received a lot of attention in
recent years, performance problems are widespread, as shown by empirical analyses of SPARQL
query logs [
Nonetheless, distributed big data infrastructures like Spark have emerged and ofer increased eficiency. Indeed, Spark has been exploited for eficient query answering [
CEUR
Workshop
Proceedings
data needed for query answering. Such works like SPARQLGX [
Our solution. To tackle this problem, in this demo, we present the novel PING system
that leverages schema information to eficiently identify the data fragments required to return
the first part of the answer and to progressively return the remaining parts, thus enabling
progressive query answering (PQA). While schemas have been successfully used to represent
RDF graphs [
We depict the global architecture of our PING system in Figure 1 (top). The framework comprises three main parts. The GUI allows users to select a pre-loaded dataset or add a new one, visualize statistics regarding their partitioning, write SPARQL queries, and inspect diagrams depicting the eficiency and accuracy of evaluating them with PING’s progressive query answering module. The query processor exploits the hierarchical partitioning in order to perform progressive query answering. The partitioner processes the chosen dataset, extracts its hierarchical schema, and generates hierarchical partitions, as well as sub-partitions and indexes. We will focus hereafter on the partitioner and query processor, which are PING’s core components.
Hierarchical Dataset Partitioning. For capturing the underlying structure of an RDF
dataset we leverage characteristic sets [
Sub-partitioning. On top of partitioning, we also implement, for each partition, a vertical partition (VP ) step, called sub-partitioning, in order to further reduce the size of the data touched at query answering. For this, we split the triples of each partition , into multiple vertical partitions [] , one per predicate . Each vertical partition contains the subjects and the objects
for a single predicate, enabling a more fine-grained selection of data at query time.
Indexing. To speed up query evaluation, we generate appropriate indexes, so that the necessary sub-partitions can be directly identified during query execution. PING constructs property, subject, and object indexes (VP, , and , respectively as shown in Figure 1(d)). Thus, we can directly identify to which partitions each such instances belong.
Progressive Query Answering and Visualization. In order to perform PQA, PING implements a novel algorithm. This iterates over all query triple patterns and inspects all their symbols. Depending on whether they correspond to a predicate, to a subject, or object constant, it then inspects the corresponding vertical partitioning and index structures to collect the set of all levels whose instances mention them. Note that a query can be (at least partially) answered on a particular set of levels, if the latter contains all its triple pattern symbols; we call this set a slice. Next, PING computes the minimal, duplicate-free, slice that covers all query symbols, by taking the intersection of all such slices. This is then used for query answering, by iterating over the cartesian product of its individual triple pattern levels.
As shown in Figure 1(e), the user can select to execute the query only on a subset of the levels, trading eficiency for accuracy, as only a subset of the results will be returned. To the best of our knowledge, the PING system is the first to enable this trade-of for performing PQA over KGs .
To demonstrate the functionalities of PING, we will use three synthetic datasets, i.e., Uniprot (3GB), WatDiv (13GB & 100GB), and LDBC Social Network Benchmark (18GB), and a real one, DBpedia (30GB). For each dataset, we will use 6 example queries of diferent shapes: 2 star, 2 chain, and 2 complex queries. The demonstration will proceed in six phases:
1. Overview. The demonstration will start by explaining the various choices made for data partitioning, sub-partitioning, and indexing. We will highlight that the characteristics of hierarchical partitioning are dataset dependent, by inspecting the partitioning of each dataset, the distribution of its triples across the various levels, as well as its sub-partitions and indexes.
2. Progressive Query Answering. We will then focus on PQA. Through the GUI, the user will be able to select example queries and also set the number of partitions on which this query will run. We will visualize the result and also we will discuss the trade-of between accuracy (percentage of returned results vs. the total results) and execution time. We will show that by increasing the number of visited partitions more data are added to the result and, thus, the query answering accuracy improves, albeit resulting in an increase in execution time as well.
3. Exact Query Answering. When all partitions are used, the query can be answered with 100% accuracy. We will discuss the impact of our partitioning/sub-partitioning/indexing scheme on answering queries considering the entire dataset. We will also show the comparative performance of PING with respect to the state-of-the-art S2RDF and WORQ systems, empirically establishing that our method boosts performance for all types of queries (star, chain, complex).
We illustrate the demonstration scenario in Figure 2. In the left screenshot, the user first chooses the WatDiv dataset, whose characteristics are computed and displayed in the right-hand side panel. As captured by the corresponding histogram, the dataset contains 1B triples and is partitioned by PING into 6 levels, of varying sizes. Next, the user selects, from the associated queries of diferent complexities, the chain-shaped Query 3, shown at the bottom of the screen. PING analyzes it and indicates in green which are the valid slices on which the query can be partially answered. PING can perform PQA on any subset of these slices and report the runtime, memory consumption, and accuracy (right screenshot). In our example, the user chose to evaluate on all 5 slices and can inspect the corresponding statistics. In general, slices can be freely added or dropped, following the desired balance between eficiency and accuracy.
To conclude, in this demonstration we present PING, the first system enabling progressive query answering over KGs. PING uses a hierarchical schema structure to partition KGs and enables progressive query evaluation. As such, it ofers minimal latency and allows trading query accuracy for eficiency.
This research project was supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “2nd Call for H.F.R.I. Research Projects to support Post-Doctoral Researchers” (iQARuS Project No 1147) and by the SafePolymed (GA 101057639) EU project.