Characteristic sets (CS) organize RDF triples based on the set of properties associated with their subject nodes. This concept was recently used in indexing techniques, as it can capture the implicit schema of RDF data. While most CS-based approaches yield significant improvements in space and query performance, they fail to perform well when answering complex query workloads in the presence of schema heterogeneity, i.e., when the number of CSs becomes very large, resulting in a highly partitioned data organization. In this paper, we address this problem by introducing a novel technique, for merging CSs based on their hierarchical structure. Our method employs a lattice to capture the hierarchical relationships between CSs, identifies dense CSs and merges dense CSs with their ancestors, thus reducing the size of the CSs as well as the links between them. We implemented our algorithm on top of a relational backbone, where each merged CS is stored in a relational table, and we performed an extensive experimental study to evaluate the performance and impact of merging to the storage and querying of RDF datasets, indicating significant improvements.
The Resource Description Framework1 (RDF) and SPARQL Protocol and RDF Query Language2 (SPARQL) are W3C recommendations for representing and querying data on the semantic web.
The semantic web has been established as a source of diverse
datasets from a multitude of domains, such as life sciences,
statistics, finance, open science and health. Wide adoption has led
to increasingly larger dataset sizes, and at the same time
complex analytical queries have started to emerge, reflecting the ever
increasing recognition of value of analytical processing in the
modern data-centric economy. In light of this, RDF data
management methods are calling for improvements in the performance
of RDF storage and querying engines, as has been discussed in
recent works, where state-of-the-art RDF engines are found to be
very eficient in simple workloads, but not eficient enough when
it comes to more complex query workloads [
In response to this limitation, recent works have shown that
extraction and exploitation of the implicit schema of the data can
be beneficial in both storage and SPARQL query performance
[
cs(s) = {p | ∃o : (s, p, o) ∈ D}
In plain words, a CS is the set of attributes (or RDF properties)
of a given subject node. Abstracting from RDF triples to their
CSs, an RDF graph can be represented on the structural level by
a graph containing CSs as nodes, and links between CSs as edges,
where a link between two CSs exists whenever a link between
two subject nodes exists in the original RDF graph. Due to the
ability to represent all of the properties of a subject node with a
single set, rather than multiple triples, CSs have been thoroughly
used as a means to optimize query planning, storage, indexing
and query processing [
However, a mapping from RDF to the relational space is not always helpful, as the structural looseness that is allowed in the RDF world can translate to multiple, heterogeneous CSs that represent skewed distributions of triples. For example, instead of the homogeneity of the graph in Figure 1, where all of the nodes share the structure, i.e., the same CS, consider the case of Figure 2(a) where nodes are described by four diferent CSs.
In fact, it is frequent,that there exist many diferent CSs within
the same dataset, representing varying internal structure for
the nodes of the source graph. This schema heterogeneity in
loosely-structured datasets is indeed frequently found in the real
world (e.g., Geonames contains 851 CSs and 12136 CS links),
imposing large overheads in the extraction, storage and
diskbased retrieval[
In these cases, we end up with a lot of CSs, each of which may actually represent very few nodes. There are two antagonizing approaches in creating a relational schema from a set of CSs. (i) Creating a relational table for each diferent CS would result in a large numbers of relational tables with few tuples in each of them, as shown in Figure 2(b) that require a very large number of joins to answer queries; (ii) on the other hand, creating a single, "universal" table, accommodating the CS’s of all the nodes of the graph would create a very wide relation, as in Figure 2(c), which is practically overly empty (i.e., too many NULL values) and space ineficient, due to the fact that diferent tuples would have very diferent cells populated.
There are two factors that afect or constrain the design choices we have. First, one could wonder "why not splitting the universal relation in the traditional manner?". Unfortunately, the traditional decomposition via functional dependencies is neither available, or enforceable to the source data. It is very possible that the incoming data to be stored are not necessarily accompanied by metadata descriptions that prescribe functional dependencies.
Even if a DBA would design them, it is also possible that the
data violate them. Thus, in the context of this paper, we proceed
with an automated design that assumes that no functional
dependencies are available and all schema dependencies are online
detected by the incoming data. Second, the desired analysis and
the expected workload we consider in this paper play a
significant role in the determination of the appropriate structure. Most
SPARQL queries involve complex graph patterns, i.e., query
conditions, which must be evaluated on the diferent CSs[
? x s u p e r v i s e s ? z . ? z h a s B i r t h d a y ' 2011 −02 −24 ' . ? z i s M a r r i e d T o ?w .
?w h a s N a t i o n a l i t y ' GR ' } Assuming a design with a "universal" relation (Figure 2c), the query evaluation over the relational schema (see Section 4 for the details on the SPARQL-to-SQL query evaluation) would require one self-join for each one of the worksFor , supervises and isMarriedT o query conditions (hasBirthday and hasN ationality conditions are executed as select operations in SQL). At the same time, there is a price of NULL values, too, as (Figure 2c) shows.
At the other end of the spectrum, in the multiple CS tables case (Figure 2b), each one of the three query conditions would require one self join and additionally three joins between each CS table and all other CS tables in the database – i.e., 4 joins per table.
Thus, despite its space eficiency, the latter case imposes performance overheads due to the large number of joins the query must perform to fetch data from multiple tables. This number can become significantly large in real-world datasets, as shown in the second column of Table 1.
In this paper, we tackle the problem of mapping heterogeneous RDF datasets to a relational schema with the aim to facilitate the processing of complex analytical SPARQL queries, by automating the decision of which tables will be created in order to host the incoming data, such that there are no overly empty tables and extremely large numbers of joins.
Interestingly, the problem is both open and hard to solve. The current approaches to address the problem do not avoid the problems that we have mentioned before and include approaches to store data generically as triples, as property tables (practically one table per CS) or as attribute value pairs as vertical partitions (see Section 2 for a detailed discussion). All these solutions are found in the extremes of the dilemma between empty space and query performance without achieving a "sweet" compromise between the two forces. Therefore, the state of practice and the state of the art provide room for improvement, and in fact, to the best of our knowledge, this is the first efort to address the problem. At the same time, the problem is hard to solve: as we show in Section 4, the complexity is exponential, and therefore, brute force methods are not adequate.
In our approach, we introduce an algorithm to automate the design process. We start by considering that each CS is a single table and by exploiting their hierarchical relationships, we merge related CSs into the same table. Moreover, we define a density-based cost function that help us stop the merging process for CSs that contain a large numbers of triples. In this way, we achieve merging of CS based on the structural similarity as well as the number of triples they contain. We follow a relational implementation approach by storing all triples corresponding to a set of merged CSs into a separate relational table and by executing queries through a SPARQL-to-SQL transformation. Although alternative storage technologies can be considered (key-value, graph stores,etc), we have selected well-established technologies and database systems for the implementation of our approach, in order to take advantage of existing relational data indexing and query processing techniques that have been proven to scale eficiently in large datasets and complex workloads. To this end, we present a novel system, named raxonDB, that exploits these hierarchies in order to merge together hierarchically related CSs and decrease the number of CSs and the links between them, resulting in a more compact schema with better data distribution. raxonDB, built on top of PostgreSQL, provides significant performance improvements in both storage and query performance of RDF data with respect to the state of the art techniques presented in Section 2. In short, our contributions are as follows: • We introduce a novel CS merging algorithm that takes
advantage of CS hierarchies, • we implement raxonDB, an RDF engine built on top of a relational backbone that takes advantage of this merging for both storing and query processing, (a) Four subject nodes, s1, s2, s3, s4 with their properties and their CSs (left) and the resulting CS hierarchy graph (right). (b) Edge case where each CS becomes a relational table. No NULL values exist in any of the tables. (c) Edge case where all CSs become one universal table. NULL values exist in this table.
(d) Merging c1, c3, c4 together and leaving c2 unmerged.
• we perform an experimental evaluation that indicates significant performance improvements for various parameter configurations.
Roadmap. In Section 2, we present the background and related work for this paper. In Section 3, we provide preliminary definition and delineate the problem, and in Section 4 we present algorithms towards its solution. In Section 5, we discuss the experimental evaluation of the paper. We conclude the paper in Section 6, with a summary of our findings and future work. 2
Due to the tabular structure that tends to implicitly underlay RDF
data, recent works for RDF data management systems have been
implemented in relational backbones. They generally follow three
storage schemes, namely (a) triples tables, (b) property tables,
and, (c) vertical partitioning. A triples table has three columns,
representing the subject, predicate and object (SPO) of an RDF
triple. This technique replicates data in diferent orderings in
order to facilitate sort-merge joins. RDF-3X [
Property Tables places data in tables with columns
corresponding to properties of the dataset, where each table identifies a
specific resource type. Each row identifies a subject node and
holds the value of each property. This technique has been
implemented experimentally in Jena [
Vertical partitioning segments data in two-column tables. Each
table corresponds to a property, and each row to a subject node
[
In distributed settings, a growing body of literature exists, with
systems such as Sempala [
Due to the high heterogeneity in the schema during the
integration and analysis of multiple RDF datasets, latest state of
the art approaches rely on implicit schema detection in order
to index/store triples based on their schema. In our previous
work [
RDF triples consist of a subject s, a predicate p and an object o.
An RDF dataset is represented as a directed labelled graph where
subjects and objects are nodes, and predicates are labelled edges.
Formally, let I , B, L be infinite, pairwise disjoint sets of URIs,
blank nodes and literals, respectively. Then, (s, p, o) ∈ (I ∪ B) ×
(I ) × (I ∪ B ∪ L) is a triple. RDF does not enforce structural rules
in the representation of triples; within the same dataset there
can be largely diverse sets of predicates emitting from nodes
of the same type [
Although each real world measurement can have its very own characteristic set, for all practical purposes, the information stored in RDF triples typically refers to recurring concepts and their features. Thus, some co-occurrences of features are common, e.g., to triples coming from the same source and representing "records" pertaining to the same "concept" (e.g., triples for events, pertaining to the concept Event come with the same set of features like datetime and description. All event instances from the same source are likely (albeit not obliged) to carry overlapping subsets of these features. At the same time, despite the commonalities, there are diferences too, typically produced by the heterogeneity of data sources and the lack of structural restrictions in RDF data. For example, an RDF dataset containing information about people, is likely to associate a name property for each instance of a Person class, while a isFatherOf property would not be associated with all instances for obvious reasons. Thus, there is a possibility to define subset relationships between the features of similar concepts. To this end, we introduce the notion of subsumption and the notion of hierarchy of subsumed property sets.
Definition 1 . (Property Sets and Property Tables). In its more general form, a CS is a property set Pi , i.e., a set of RDF predicates and the set of all property sets is denoted with P . A Property Table (also: CS Table) Ti for a given property set Pi is a relational table comprising an identifier sid for the subject node s and |Pi | columns, where Pi = {pi,1, pi,2, . . . , pi,n } are the predicates emitting from s. Ti contains the set ri of tuples that instantiate the values of the properties for sid, i.e., Ti = (sid ∪ Pi , ri ). A tuple can hold values for the predicate columns in I ∪B ∪L ∪ NU LL, i.e., each cell in the relational table can either have a standard value of an RDF triple object, or NU LL when the subject node identified in sid does not have a property in any of its triples. In Figure 2(a), four subject nodes, s1, s2, s3, s4, are shown. These have four diferent CSs based on their property sets, namely c1, c2, c3, c4.
Definition 2 . (CS Subsumption). Given two CSs, ci and cj , then ci subsumes cj , or ci ≻ cj , when ci is a subset of cj , or ci ⊂ cj . This subsumption forms a parent-child relationship. For example, consider c1, c2 that describe human beings, with c1 = {type, name } and c2 = {type, name, marriedT o}. It can be seen that c1 ⊂ c2 and therefore c1 subsumes c2. CS subsumption relationships can be seen in Figure 3(a) as directed edges between nodes. In the example of Figure 2(a), the four CSs exhibit strong subset-superset relationships between their properties, For instance, c1 and c2 have property sets that are supersets of both c3 and c4, while c3 also subsumes c4. The set of all parent-child relationships defines a CS hierarchy.
Definition 3 . (CS Hierarchy and Inferred Hierarchy). CS
subsumption creates a partial hierarchical ordering such that
when ci ≻ cj , then ci is a parent of cj . Formally, a CS hierarchy
is a graph lattice H = (V , E) where V ∈ C and E ∈ (V × V ). A
directed edge between two CS nodes c1, c2 exists in H , when
c1 ≻ c2 and there exists no other ci such that c1 ≻ ci ≻ c2.
The directed edge stems from the parent node and arrives at
the child node. An example CS hierarchy can be seen in Figure
3(a). Given a hierarchy H , we denote the hierarchical closure of H
with Hc , so that Hc extends H to contain inferred edges between
hierarchically related nodes that are not consecutive, e.g. a node
and its grandchildren. Intuitively, for every set of features c that
describes some concept in the dataset, we introduce a node in
our graph. Every strict superset of features of c is a descendant
of c, and every strict subset of features of c is a superset of c. An
example inferred hierarchy can be seen on the right of Figure 2(a),
with the inferred relationships in dashed lines as well as in Figure
3(c) for a sub-graph of the graph in Figure 3(a). In the remainder of
this paper, we refer to Hc as the inferred hierarchy of H . The lattice
resembles the traditional OLAP cube lattice (see [
Definition 4 . (CS Ancestral Sub-graphs). Given an inferred hierarchy Hc = (V , E), a CS cbase , a set of CSs c1, . . . , ck , and a sub-graph Hcabnacse = (V ′, E′ ) with V ′ ⊆ V and E′ ⊆ E, we say that Hcabnacse is an ancestral sub-graph over cbase when ∀i ∈ [1..k], it holds that ci ≻ cbase and (ci , cbase ) ∈ E′ . Intuitively, any set of ancestors of a node cbase forms an ancestral subgraph. More than one ancestral sub-graphs can be defined over cbase , as any subset of its parents is considered an ancestral sub-graph over cbase . For instance, in Figure 3(c), nodes c7, c4, c2 form an ancestral sub-graph over c7. Similarly, nodes c6, c4, c2 and c6, c5, c2 form ancestral sub-graphs over c6.
Having defined the hierarchy of characteristic sets and the respective graph, we are now ready to provide the foundation for the core of the problem of this paper. Basically, the goal is to ifnd a way to store data in a way that balances two antagonizing goals: (a) the number of NULL values and the unnecessary space increase, vs., (b) the resulting decrease in query processing time that would result from the fragmentation of stored data in multiple nodes and the need to join them. To address this issue, we can attempt to merge diferent nodes into one, paying the price of empty space to avoid the price of joins. There exist two edge cases here, namely (i) assign a table to each CS in the incoming data, resulting in as many tables as CSs, and (ii) assign one universal tables for all CSs. This table would contain all of the properties found in the input dataset. The two edge cases for the running example of Fig. 2 can be seen in Fig. 2(b,c).
Definition 5 . (Hierarchical CS Merge). Given an ancestral subgraph a = (V ′, E′ ), where V ′ = {c1, c2, . . . , ck } as defined above, and the set of property tables T (V ′ ), then hier _merдe(a, T (V ′ )) is a hierarchical merge of a that results in a single table Ta = (cbase , ra ). As cbase is the most specialized CS in a, the columns k of Ta are exactly the properties in cbase , while ra = iÐ=1 ri′ is the union of the records of all CSs in V ′ , where ri′ is the projection of ri on the properties in cbase . Consequently, ri′ contains NULL values for all the non-shared properties of cbase and ci . In essence, this is an edge contraction operator that merges all tables of the nodes of an ancestral sub-graph into one and keeps the signature (i.e., the properties) of the base CS cbase . For instance, assume that V ′ = {c0 = (P0, r0), c1 = (P1, r1), c2 = (P2, r2)} is the set of vertices of an ancestral sub-graph with three CSs, with P0 = {pa, pb }, P1 = {pa, pb , pc } and P2 = {pa, pb , pc , pd }. Thus, c0 ≻ c1 ≻ c2. The output of the merging process for our running example can be seen in Figure 2(d). Hierarchical merging can be seen in Figure 4. rnull represents the ratio of null values to the cardinality of the merged table. The numerator of the fraction represents the total number of cell values that will be null, as the product of the number of non-shared properties and the cardinality of the parent CS. The denominator represents the resulting cardinality of the table.
In order to assess an ancestral sub-graph, we use a generalized version of rnull that captures the NULL value efect on the whole sub-graph: д rnull (д)|Td = Íi|д=|1 |cd \ ci | × |ri | |rd | + Í|д | i=1(|ri |) Here, Td = (cd , rd ) is the root of sub-graph д. However, merging a parent to a child changes the structure of the input graph, as the cardinality of the merged child is increased. Thus, we define a cost function that works on the graph level, as follows: Definition 5 . (Merge Graph). Given an inferred CS hierarchy Hc = (V , E), a merge graph is a graph H ′ = (V ′, E′ ) that consists of a set of n ancestral sub-graphs, and has the following properties: (i) H ′ contains all nodes in H such that V ′ ≡ V , i.e., it covers all CSs in the input dataset, (ii) H ′ contains a subset of the edges in H such that E′ ⊂ E, (iii) each node is contained in exactly one ancestral sub-graph ai , (iv) all ancestral sub-graphs are pair-wise disconnected, i.e., there exist no edges between the nodes of diferent ancestral sub-graphs. Thus, each ancestral subgraph can be contracted into one node unambiguously, using the hier _merдe operator. Also, the total number of relational tables will be equal to the number of ancestral sub-graphs in the merge graph.
The primary focus of this work is to improve the eficiency of storage and querying in relational RDF engines by exploiting the implicit schema of the data in the form of CSs. The two extreme approaches – i.e., (a) a separate table for each CS, on the one end of the spectrum, or, (b) merging all the data into a universal table with a schema expressed as the union of the individual features of the diferent CS’s, at the other end of the spectrum, have the following drawbacks, respectively: (i) multiple joins of separate tables at query processing, if many tables are used, and (ii) bad utilization of disk space if nodes are excessively merged into a very small number of tables (due to excessive empty space with NULLs).
Problem Formulation. Given an inferred CS hierarchy Hc = (V , E), the problem is to find a merge graph H ′ = (V , E′ ) in the form of a set of disconnected ancestral sub-graphs, that provides a good way to merge CS nodes. In other words, the problem is to find the best set of ancestral sub-graphs from an inferred hierarchy Hc that minimize an objective cost function cost (x ). 4
What makes the problem hard, is the complexity of finding a sweet spot in the Pareto equilibrium between conciseness of the relational schema (few tables) and internal density (with respect to the empty space they contain).
Schema conciseness. To start with the arguments in favor of reducing the number of nodes via merging, we can see that, by reducing the number of CS, the number of joins between them is also reduced. Furthermore, merging together CSs leads to a less skewed distribution of data to relational tables. Ultimately, this results in a drastically decreased disk-based I/O cost, as less tables are fetched, positively afecting query processing as well.
Density. On the contrary, merging tables results in the
introduction of NULL values for the non-shared columns, which can
degrade performance. Specifically, merging CSs with diferent
attribute sets can result in large numbers of NULL values in the
resulting table. Given a parent CS table T1 = (sid ∪ c1, r1) and a
child CS table T2 = (sid ∪ c2, r2) with |c1 | < |c2 | and |r1 | >> |r2 |,
the resulting |c2 \ c1 | × |r1 | NULL cells will be significantly large
compared to the total number of r1 + r2 records, thus
potentially causing poor storage and querying performance[
Thus, choosing dense CSs as bases is a seeding process that aims to minimize this NULL value efect by making sure that a large fraction of the input records will not be extended with NULL values. This is true because a CS base and its resulting merged table will have exactly the same properties (columns) and thus introduction of NULL values will not be needed for the records of the CS base.
The problem of selecting ancestral sub-graphs for the merge
is computationally hard, as mentioned earlier. For this reason,
we rely on heuristics in order to seed the process and provide an
initial set of ancestral sub-graph bases for the final merged tables.
The CS bases will be the only relational tables in the output, with
the remaining tables merged into them. For this, we identify dense
CS nodes in the hierarchy (i.e, with large cardinalities) and use
these nodes as the bases of the ancestral sub-graphs. While node
density can be defined in many diferent ways, in the context
of this work we define a ci to be dense, if the cardinality of its
relational table is larger than a linear function of the maximum
cardinality of CSs in D, i.e., a function d : N → R, with d(Ti ) =
m × |rmax |. Here, m ∈ [
Given this cost model and a predefined set of dense nodes, our algorithm will find the optimal sub-graph for each dense node. An inferred hierarchy graph can be converted to a set of connected components that are derived by removing the outgoing edges from dense nodes, since we are not interested in merging children to parents, but only parents to children. An example of this can be seen in Figure 3(b). For each component, we can compute cost (д) as the sum of the costs of these components. The main idea is to identify all connected components in the CS graph, iterate through them, enumerate all sub-graphs within the components that start from the given set of dense nodes, and select the optimal partitioning for each component.
The algorithm can be seen in Algorithm 1. The algorithm works by first identifying all connected components of the inferred hierarchy (Line 2). Identifying connected components is trivially done using standard DFS traversal, and is not shown in the Algorithm. Then, we iterate each component (Line 3), and for each component, we generate all possible sub-graphs. Then, we calculate the cost of each sub-graph (Line 7) and if it is smaller than the current minimum, the minimum cost and best sub-graph are updated (Lines 8-9). Finally, we add the best sub-graph to the ifnal list (Line 11) and move to the next component.
To generate the sub-graphs, we do not need to do an exhaustive generation of 2n combinations, but we can rely on the observation that each non-dense node must be merged to exactly one dense node. Therefore, sub-graph generation is reduced to finding all possible assignments of dense nodes to the non-dense nodes. An example of this can be seen in Figure 3. In the figure, nodes c2, c4, c5 are non-dense, while nodes c6, c7, c8 are dense. All possible and meaningful sub-graphs are enumerated in the table at the right of the figure, where we assign a dense node to each of the non-dense nodes. An assignment is only possible if there exists a parent-child relationship between a non-dense node and a dense node, even if it is an inferred one (e.g. c2 is an inferred parent of c7). Hence, the problem of sub-graph generation becomes one of generating combinations from diferent lists, by selecting one element from each list. The number of lists is equal to the number of non-dense nodes, and the elements of each list are the dense nodes that are related to the non-dense node.
Complexity Analysis. Assuming that a connected component д has k non-dense nodes and d dense nodes, and each nondense node ki is related to e(ki ) dense nodes, then the number of sub-graphs that need to be enumerated are Îk i=1 e(ki ).
In the example of figure 3, the total number of sub-graphs is e(c2) × e(c4) × e(c5) = 3 × 2 × 1 = 6. In the worst case all k nodes are parents of all d nodes. Then, the number of total subgraphs is dk , which makes the asymptotic time complexity of the algorithm O(dk ). 4.1
For very small d, k (e.g. d, k < 4), the asymptotic complexity of O(dk ) is acceptable. However, in real-world cases, the number of connected components can be small, making d and k large. For this reason, we introduce a heuristic algorithm for approximating the problem, that does not require enumerating all possible combinations, relying instead on a greedy objective function that attempts to find the local minimum with respect to the defined cost model for each non-dense node.
Data: An inferred hierarchy lattice Lc as a adjacency list , and a set of dense CSs D Result: A set of optimal ancestral sub-graphs 1 init f inal List ; 2 connectedComponents ← f indConnectedComponents(Lc ); 3 for each connectedComponent do 4 init min ← MAX _V ALU E; 5 init bestSubдr aph ; 6 while next ← connectedComponent .дener ate N extSubдr aph() do 7 8 9 10 11 12 end 13 return f inal List ; if cost (next ) < min then min ← cost (next ); bestSubдr aph ← next ; end f inal List .add(bestSubдr aph);
The main idea behind the algorithm is to iterate the non-dense nodes, and for each non-dense node, calculate rnull and find the dense node that minimizes this function for the given non-dense node. Then, the cardinalities will be recomputed and the next non-dense node will be examined. The algorithm can be seen in Algorithm 2. In the beginning, the algorithm initiates a hash table, merдeMap, with an empty list for each dense node (Lines 1-4). Then, the algorithm iterates all non-dense nodes (Line 5), and for each dense node, it calculates the cost rnull of merging it to each of its connected dense nodes (Lines 5-13), keeping the current minimum cost and dense node. In the end, the current non-dense node is added to the list of the dense node that minimizes rnull (Line 14). Notice that we do not need to split the hierarchy into connected components in order for дreedyMerдe to work.
Complexity Analysis. Given k non-dense nodes and d dense nodes, where each non-dense node ki has e(ki ) dense children, the дreedyMerдe algorithm needs Ík i=1 e(ki ) iterations, because it requires iteration of all e(ki ) nodes for each ki . In the worst case, every ki is related to all d dense nodes, requiring kd iterations. Assuming a constant cost for the computation of rnull , then the asymptotic complexity of the greedy algorithm is O(kd), which is a significant performance when compared to the exponential complexity of optimalMerдe.
Data: A hash table p mapping non-dense CSs to their dense descendants, a set of dense CSs D, and a set of non-dense CSs K
Result: A hash table mapping dense CSs to sets of non-dense CSs to be merged 1 init merдeMap; 2 for each d ∈ D do 3 merдeMap.put (d, newList ()); 4 end 5 for each k ∈ K do 6 min ← MAX _V ALU E; 7 init best Dense; 8 for each dk ∈ p .дet (k) do 9 cost ← rnull (k, dk ); 10 if cost < min then 11 min ← cost ; 12 best Dense ← dk ; 13 end 14 merдeMap.дet (best Dense).add(k); 15 end 16 return merдeMap;
This process does not necessarily cover all CSs of the input dataset. For example, some CS nodes might not have any dense children. Given this, the percentage of the dataset that is covered by this process is called dense CS coverage. The remainder of the CSs are aggregated into one large table, Tr est , containing all of their predicates. If the total coverage of the merging process is large, then Tr est does not impose a heavy overhead in query performance, as will be shown in the experiments. Finally, we load the data in the corresponding tables. 4.2
We implemented raxonDB as a storage and querying engine that supports hierarchical CS merging, and can be deployed on top of standard RDBMS’s. Specifically, we used PostgreSQL 9.6, but raxonDB can be adapted for other relational databases as well.
CS Retrieval and Merging. The processes of retrieving and
merging CSs take place during the loading stage of an
incoming RDF dataset. CS retrieval is a trivial procedure that requires
scanning the whole dataset and storing the unique sets of
properties that are emitted from the subject nodes in the incoming
triples, and is adopted from our previous work in [
Indexing. We deploy several indexes in raxonDB. First of,
we index the subject id for each row. We also build foreign-key
indexes on object-subject links between rows in diferent CSs, i.e.,
when a value of a property in one CS is the subject id of another
CS. Next, we use standard B+trees for indexing single-valued
property columns, while we use PostgreSQL’s GIN indexes, which
apply to array datatypes for indexing multi-valued properties.
This enables fast access to CS chain queries, i.e., queries that apply
successive joins for object-subject relationships. Furthermore,
we store these links on the schema level as well, i.e., we keep an
index of CS pairs that are linked with at least one object-subject
pair of records. These links are called Extended Characteristic
Sets (ECSs) and are based on our previous work in [
Query Processing. Processing SPARQL queries on top of
merged CSs entails (i) parsing the queries, (ii) retrieving the query
CSs, (iii) identifying the joins between them, and (iv) mapping
them to merged tables in the database. Steps (i)-(iii) are inherited
from our previous work in [
We implemented raxonDB on top of PostgreSQL3. As the focus of this paper is to improve RDF storage and querying eficiency in relational settings, we rely on existing mechanisms within PostgreSQL for I/O operations, physical storage and query planning. In this set of experiments, we report results of implementing hier _merдe with the greedy approximation algorithm, as experimenting with the optimal algorithm failed to finish the merging process even in datasets with small numbers of CSs.
Datasets. For this set of experiments, we used two synthetic
datasets, namely LUBM2000 (≈300m triples), and WatDiv (≈100m
triples), as well as two real-world datasets, namely Geonames
(≈170m triples) and Reactome (≈15m triples). LUBM [
Loading. In order to assess the efect of hierarchical merging
in the loading phase, we performed a series of experiments using
all four datasets. For this experiment, we measure the size on
disk, the loading time, the final number of merged tables, as well
as the number of ECSs (joins between merged tables) and the
percentage of triple coverage by CSs included in the merging
process, for varying values of the density factor m ∈ [
Query Performance. In order to assess the efect of the
density factor parameter m during query processing, we perform a
series of experiments on LUBM, Reactome and Geonames. For
the workload, we used the sets of queries from [
In order to assess the performance of raxonDB and establish
that no overhead is imposed by the relational backbone, we
performed a series of queries on LUBM2000, Geonames and
Reactome, assuming the best merging of CSs is employed as captured
by m with respect to our previous findings. We also compared
the query performance with rdf-3x, Virtuoso 7.1, TripleBit and
the emergent schema approach described in [
In this paper, we tackled the problem of automatically mapping heterogeneous RDF datasets to a relational schema by considering the implicit schema in RDF triples. We presented a method that extracts the Characteristics Sets, i.e., the set of properties describing the diferent classes of RDF instances in the data and exploits the hierarchical relationships between diferent CSs in order to merge and map them to relational tables. We have provided two algorithms, an optimal (exhaustive) one which selects ancestral sub-graphs of CS for merging in exponential time and greedy one, which via the use of heuristics improves the performance to polynomial time. We have implemented our methods on top of a standard RDBMS solution, i.e., PostgreSQL for extracting, indexing and query processing of SPARQL queries. Finally, we have experimented with two synthetic and two real-world datasets, all of them exhibiting high heterogeneity in their schemas, we compared with various alternative RDF engines and the results for the performance of indexing and querying showed that our system outperforms for various types of workloads.
As future work, we will study computation of the optimal value for m, taking into consideration workload characteristics as well as a more refined cost model for the ancestral paths. Furthermore, we will study and compare our approach to a graph database setting, as well as experiment with a column-stored relational DB, in order to further scale the capabilities of raxonDB.
Acknowledgments. This work is partially funded by the projects VisualFacts (#1614 - 1st Call of the Hellenic Foundation for Research and Innovation Research Projects for the support of post-doctoral researchers), and "Moving from Big Data Management to Data Science" (MIS 5002437/3)- Action "Reinforcement of the Research and Innovation Infrastructure" (funded by Greece and the European Regional Development Fund).