RDF is a data model that allows to describe relationships between arbitrary entities in the form of subject-predicate-object. While representing data in such form is convenient, its e cient processing poses a number of challenges. Therefore, at present it is highly active research venue with lots of existing approaches. One of such approaches is based on characteristic sets. Essentially, it is a collection of records that describes an entity together with its properties. Usage of characteristic sets was shown to signi cantly speed up RDF query processing. In this paper we present a research proposal for a post-graduate project related to partitioning of tables obtained by characteristic set extraction. Our goal is to design a partitioning method that would be bene cial to processing of a such tables. In this report we survey existing RDF processing systems approaches, brie y describe our vision of partitioning approach and present a plan for further studies.
The Resource Description Framework (RDF) is a data model, developed by W3C consortium for the Semantic Web. The main idea of the RDF is to describe realworld entities and relationships between them in a machine-readable form. A relationship between two entities in RDF is represented in a triple form (subject, predicate, object ). This allows us to visualize an RDF dataset as a graph G = (V; E) ; where V is the set of all entities and E is the set of all predicates. A simple RDF graph is shown on Fig. 1.
SPARQL is a query language for RDF. Just like the RDF data, any SPARQL query can also be represented as a graph. A query in SPARQL uses the so-called patterns to declare the constraints for query results. As shown in Fig. 2, a pattern is a graph with variables in some nodes. In order to execute a SPARQL query we need to somehow match the data with a pattern.
The goal of an RDF management system is to store the RDF data and to perform SPARQL queries in the most e cient manner. In order to reach that goal, a large variety of systems have been developed, each of them has its own purpose and features.
foaf:name \Johnny Lee Outlaw" Male foaf:gender foaf:mbox peter@example.org
foaf:mbox J L Outlaw foaf:friendOf P Goodguy foaf:gender Male
foaf:name \Peter Goodguy"
foaf:gender foaf:name ?name ?X
foaf:friendOf foaf:mbox ?mbox And with a graph representation in mind, one can de ne a Characteristic Set (CS) of a vertex as a set of all edges connected to it.
Designed initially to estimate the cardinality of queries with joins [25], Characteristic Sets can be used as indexes [23] or as a base unit for a relational schema [24, 30, 30]. A simple CS appears to be not su cient for both of the cases, therefore complex CS-based structures emerge. In [23] Extended CSs are de ned and used as an index structure, re ecting the complex inherent dependencies in RDF data. A Schema [29, 30] of an RDF dataset is designed to be its human-readable relational form. A single table in the Schema is composed of several CSs of the same subject, merged together. A similar idea is suggested in [24], but this solution uses di erent merging strategy and does not necessary produce a human-readable relational schema.
All of the above mentioned CS-based solutions are centralized systems, which do not employ any advanced partitioning strategy. The utilization of some form of relational partitioning may greatly increase performance of a system, making it possible to compete with native relational solutions.
In this proposal we present our ongoing research of RDF physical design methods. We also state some preliminary results we obtained, in form of a short state of the art survey. We have composed an evaluation plan of the research that we intend to follow over the next three years of the PhD study. By following this plan we hope to develop a solution comparable to other modern RDF management systems.
This proposal has a following structure: in Section 2 we brie y describe some of the modern RDF management systems with an emphasis on their physical design. Section 3 contains the problem statement and our considerations. In Sections 4 and 5 we describe our research process and its key stages.
There is a large number of RDF stores, both centralized and distributed. In Table 1 are listed some of the systems and their distinctive features. We brie y describe them below.
Centralized systems are meant to be run on a single computer and largely
do not support any data partitioning. Jena [
Distributed/standalone systems implement their own distribution
algorithms and are often an extension of some centralized system. TriAD [
Distributed/federated systems are essentially a number of centralized
systems, tied together by a custom mediator. DREAM [
Distributed/Hadoop systems use Hadoop framework for distributed query
processing. The main idea is to partition the data across multiple nodes, and then
execute queries in a MapReduce manner: split the initial query into subqueries
and then merge the local results together. CliqueSquare [
In Section 2 we have described some of the modern RDF management systems. Among them there are only two that use characteristic sets to e ciently process star pattern queries. However, none of them uses any kind of data partitioning, and both are centralized systems. At the same time current studies show that storing RDF graph using relational schema representation is competitive to the native RDF approach, and, thus, is of research interest.
Our primary research question is the following: is it possible to devise and
implement an e cient horizontal partitioning strategy for a CS-based system, both
for centralized and distributed cases? Currently, CS approach is in its infancy |
research is primarily concentrated on generating relational schemes [24, 29, 30].
Physical design issues are yet to be addressed. At the same time, there are lots
of physical design options for classic relational systems [
An example of such option is a horizontal data partitioning. There are several types distinguished: (i) range data partitioning; (ii) hash data partitioning; (iii) list partitioning and (iv) column partitioning. The rst two partition the data according to values of partitioning attribute or its hash respectively. The third implies that each fragment is de ned by the list of values the partitioning attribute has. The last has a virtual attribute added into the relation. Then it is partitioned by any method using the virtual attribute as the partitioning attribute.
Our hypothesis is the following: some tables containing one or several merged CS would be queried more frequently than others. In this case they can be partitioned in order to provide (i) data pruning during query execution, e.g. not all fragments would be scanned; (ii) data distribution with fragment-based data replication. We presume that attribute-based composite multi-attribute partitioning would be of use in this case.
Workload-awareness is another dimension that was not addressed for the CS approach. A special partitioning strategy for CS tables is only the rst step. In order to reap maximum bene ts from CS this strategy should be automatically
Wfo nU d e ; h egy ten A s i l
m W b t u ra t p t a
s re s a g t w in l
a n ic
e em ito p ts it s g y r s a e p th ta sr i
o r a ta it a d S tr e y ; a |d
n |i
n a P r|ign lon a n w e o o Y it d ;e itr r m a fo a P e n ; l s d ab ' e l em su ia
v ts s a y e se exd rsce sex th in u e so d n
I || s
| m e e x e ty ed od l. s
p
C e S In ; .s ;s
m m d e e o ts tssy teh sy ta
a t m gn D n n i e o l m it y r re ea e a d Y g a lic n n p u a re eh m l t F ia D ce | R p g . s n
i 1 le l. ] ] ] 8 ed 23 [4 [3 z [ e
r s D ] ] e / R 6 0 / [2 [1 B m d E te ] b p d s n o a e n y e x
B e e
F r nBD 2RD tsao []a5 tn F t x n o
X so so D 3 o o i e u u
t D ir ir u 1 b [ r r t o s t i s
t D e r e a r dP toS ir r
A in
d
e
f
/ ]
d ]
a 2
H [
] ] 4 9 3 or semi-automatically applied to the data. Therefore, on the next step we aim to create an advisor that would accept a prospective workload and recommend a number of bene cial con gurations that would consist of aforementioned partitions. CS tables not only have di erent access frequencies, but also di erent in terms of rows, number and type of attributes and so on. Thus, we would have to create a cost-based model to use inside our advisor.
Another direction of our study is the application of column-stores for
CSbased RDF processing. Column-store [
Thus, our prospective step is to try to apply our partitioning for a centralized column-store system. In case of the success we will explore the applicability of our partitioning in the distributed environment. 4
Step 1: test our main hypothesis: whether CS-tables are unevenly \heated" by a workload or not. Run experimental evaluation.
Input: some CS-based system (either row- or column-store) and a benchmark. Output: heat patterns.
Step 2: outline a class of bene cial partitioning schemes. Using this information devise a partitioning method or methods. Then, evaluate these methods by manually applying them to the same data in order to verify performance improvement.
Input: heat patterns.
Output: partitioning methods and evaluation results.
Step 3: implement an automatic advisor for our partitioning methods. We need to develop a cost model and an enumeration algorithm to select an appropriate partitioning strategy.
Input: partitioning methods, evaluation results.
Output: cost model, automatic advisor.
Step 4: evaluate our partitioning for a centralized column-store system. In case
of success move to a distributed column-store system to evaluate distributed
processing and to try replication. PosDB [
Output: implementation in a column-store system.
Given the problem and the research method, we can compose the following plan: 1. Select a suitable RDF management system that supports characteristic sets.
Modify its source code to gather information regarding CS table usage: relative \heat" for each relation, number of scanned rows, number of rows passed through ltering predicates and so on. 2. Perform evaluation for some standard benchmark data (currently we aim for
LUBM [
So far we have performed a survey of RDF processing systems and formulated a general idea of our approach. Using this survey we have demonstrated its novelty and discussed its prospects. We have also selected systems that are candidates to be used during the rst steps of our study. 6
Designing Systems for processing RDF data is a highly active area of research. Both academy and industry are interested in development of an e cient RDF query engine. There are more than thirty systems built on a di erent principles and exploiting various ideas.
Characteristic sets is a promising approach to speed-up the processing RDF queries that involve selection of entities which satisfy some predicates. Its core idea is to detect star patterns in the graph data and translate them into dedicated relational tables. Then, these tables can be combined with each other.
In this paper we have outlined a plan for our study that aims to devise a partitioning method for characteristic sets. We have presented a comparison table of existing approaches and brie y discussed them. Then, we described a justi cation of our approach and presented possible directions of our project.
In the future we plan to continue our studies by executing the steps outlined in the Section 4. [19] Hose, K., Schenkel, R.: WARP: Workload-Aware Replication and Partitioning for RDF. In: ICDEW'13. pp. 1{6 [20] Huang, J., Abadi, D.J., Ren, K.: Scalable SPARQL Querying of Large RDF
Graphs. PVLDB 4, 1123{1134 (2011) [21] Idreos, S., et al.: MonetDB: Two Decades of Research in Column-oriented
Database Architectures. IEEE Data Eng. Bull. 35(1), 40{45 (2012) [22] Lee, K., Liu, L.: Scaling Queries over Big RDF Graphs with Semantic Hash
Partitioning. Proc. VLDB Endow. 6(14), 1894{1905 (Sep 2013) [23] Meimaris, M., Papastefanatos, G., Mamoulis, N., Anagnostopoulos, I.: Extended Characteristic Sets: Graph Indexing for SPARQL Query Optimization. In: ICDE'17. pp. 497{508 [24] Meimaris, M., Papastefanatos, G.: Hierarchical Characteristic Set Merging, https://2018.eswc-conferences.org/wpcontent/uploads/2018/02/ESWC2018 paper 126.pdf [25] Neumann, T., Moerkotte, G.: Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins. In: ICDE'11. pp. 984{994 [26] Neumann, T., Weikum, G.: The RDF-3X Engine for Scalable Management of RDF Data. The VLDB Journal 19(1), 91{113 (Feb 2010) [27] Papailiou, N., et al.: H2RDF+: High-performance Distributed Joins over
Large-scale RDF Graphs. In: ICBD'13. pp. 255{263 [28] Peng, P., et al.: Processing SPARQL Queries over Distributed RDF Graphs.
The VLDB Journal 25(2), 243{268 (Apr 2016) [29] Pham, M., Boncz, P.A.: Exploiting Emergent Schemas to Make RDF Systems More E cient. In: ISWC'16. pp. 463{479 [30] Pham, M., Passing, L., Erling, O., Boncz, P.: Deriving an Emergent Relational Schema from RDF Data. In: WWW'15. pp. 864{874 [31] Ravindra, P., Deshpande, V.V., Anyanwu, K.: Towards Scalable RDF
Graph Analytics on MapReduce. In: MDAC'10. pp. 5:1{5:6 [32] Rohlo , K., Schantz, R.E.: Clause-iteration with MapReduce to Scalably
Query Datagraphs in the SHARD Graph-store. In: DIDC'11. pp. 35{44 [33] Schatzle, A., Przyjaciel-Zablocki, M., Berberich, T., Lausen, G.: S2X: Graph-Parallel Querying of RDF with GraphX. In: Biomedical Data Management and Graph Online Querying. pp. 155{168 [34] Schatzle, A., Przyjaciel-Zablocki, M., Lausen, G.: PigSPARQL: Mapping
SPARQL to Pig Latin. In: SWIM'11. pp. 4:1{4:8 [35] Schatzle, A., Przyjaciel-Zablocki, M., Neu, A., Lausen, G.: Sempala: Interactive SPARQL Query Processing on Hadoop. In: ISWC'14. pp. 164{179 [36] Schatzle, A., Przyjaciel-Zablocki, M., Skilevic, S., Lausen, G.: S2RDF: RDF
Querying with SPARQL on Spark. PVLDB 9(10), 804{815 (2016) [37] Stonebraker, M., et al.: C-store: A Column-oriented DBMS. In: VLDB'05.
pp. 553{564 [38] Weiss, C., Karras, P., Bernstein, A.: Hexastore: Sextuple Indexing for Semantic Web Data Management. PVLDB 1(1), 1008{1019 (Aug 2008) [39] Yang, S., Yan, X., Zong, B., Khan, A.: Towards E ective Partition Management for Large Graphs. In: SIGMOD'12. pp. 517{528 [40] Zeng, K., et al.: A Distributed Graph Engine for Web Scale RDF Data. In: PVLDB'13. pp. 265{276