Adding Data to Your Graph? Use of RDF Quads Guarantees Your Old Queries Remain Valid and Backward-Compatible with Your New Schema!

Oracle Database has support for Resource Description Framework (RDF) quadstore and Property Graph (PG). We compare, from a schema evolution and backward compatibility point of view, the handling of evolving real-world data modeled as graph using the following graph models:

1. RDF Graphs (W3C RDF 1.1 Recommendation, 25-FEB-2014)
   1. RDF-T: Triples-Only
   2. RDF-TQ: Triples+Quads
   3. RDF-Q: Quads-Only
2. Property Graphs (PG)

We will do a comparative analysis of the ways in which the different graph data models handle the types of additions, listed in the table below, in an evolving graph and their implications on pre-existing queries and schema for the graph.

The main finding that we will try to motivate and illustrate here is that the following ability – relevant to RDF triples, and for PG, to edges, edge-properties, and vertex-properties – is of critical importance for handling graph data addition in a query-preserving, backward-compatible manner:

• Assign a unique id to a relationship (and property-value association).
• Make use of that id as endpoints of a relationship
• Do the above:
  • without affecting pre-existing queries, and
  • while maintaining backward compatibility of the evolving schema (used for query design purposes)

Motivation: Consider the rather mundane everyday content shown in the first row and its evolution to accommodate addition of the somewhat sensational assertion in the second row of the table below:

Types of Transformation: We will make use of the following two types of transformation in the illustration below:

• Vertexification of an edge, edge-property, vertex-property, or RDF triple.
  • Edge: A new vertex – “edge-vertex” – is created to represent the edge. A vertex-property reflecting the edge-type of the original edge is added to the edge-vertex. Two new edges are created connecting the edge-vertex to the two endpoints of the original edge. The original edge is deleted.
  • Vertex-Property: A new vertex – “vp-vertex” – is created to represent the vertex-property. The target property-value pair is removed from the original vertex and added to the vp-vertex. A new edge is created connecting the original vertex to the vp-vertex.
  • Edge-Property: A new vertex – “ep-vertex” – is created to represent the edge-property. The original edge is replaced with two edges connecting the ep-vertex to its two endpoints. The target property-value pair is removed from the original edge and added to the ep-vertex. Finally, the steps used for vertexification of a vertex-property (as noted above) are followed for this newly added vertex-property of the ep-vertex.
  • RDF triple: (In RDF terminology, this step is essentially the same as reification.) A new resource (or vertex) – “triple-vertex” – is created to represent the original triple. The original triple is replaced with three new triples created with the triple-vertex as the subject, recording respectively the subject, predicate, and object components of the original triple.
• Quadification of an RDF triple: This is relevant for RDF-TQ only. A new resource (or vertex) – “triple-vertex” – is created to represent the original triple. A quad is created with the same subject, predicate, and object components as the original triple and the triple-vertex as the “named graph” component. The original triple is deleted. (Quadification is essentially the conversion of a triple or unnamed edge to a quad or named edge.)

Vertexification in PG and RDF-T: Representation of the original content in PG is shown on the left-side of the diagram below and that of the extended content on the right-side. (It will be quite similar for RDF Triples-Only model too.)

It is easy to see that a lot has changed in the schema to accommodate the small additional content. Two edge-types – “donatedTo” and “admittedTo” – have disappeared, and they have been replaced with two pairs of new edge-types <“donor” and “receiver”> and <”student” and “university”>, respectively. A new vertex-property, “event”, with value reflecting the original edge-type has been added. (In addition, a new edge-type, “helped”, has been added, but this is just an expected expansion of the original schema.)

What are the implications of this significant change in schema? Many original queries (e.g., “Who donated to Top University?”), that were designed based on the original schema, would not work anymore. Query designers have to familiarize themselves with the new schema and then rewrite the queries accordingly.

Ideally, in case of PG, adding a new edge of edge-type “helped” connecting the edge “e12: donatedTo” to the edge “e32: admittedTo”, should have been enough. Similarly, for RDF-T, a new triple connecting the “donatedTo” triple (as subject) to the “admittedTo” triple (as object) with “helped” as the predicate should have been enough.

However, that is not allowed in both PG and RDF-T. In PG, an edge cannot be an endpoint of an edge (and the same restriction applies to vertex-properties and edge-properties as well). In RDF-T, a triple cannot be the subject or object of another triple. In PG, even though every edge has a unique edge id, the edge id cannot be used for anything other than hanging edge-properties from the edge, and in RDF-T, there is no id for a triple.

These restrictions lead to the following: only vertices are allowed to be endpoints of an edge. The workaround that was used, therefore, to arrive at the right-side diagram above was to “vertexify” the relevant edges in PG to create new vertices (edge-vertices) to represent those edges, respectively, and then use those as the endpoints. Same workaround works for RDF-T too: to use an RDF triple as endpoint of an edge, i.e., as subject and/or object of a new triple, we must vertexify the triple to create a resource (triple-vertex) that will represent the triple and then use it in the new triple. (Note that vertexification is really similar to “reification”, but the word “vertexification” is probably more intuitive in the graph context.)

Quadification in RDF-TQ: Representation of the original content in RDF-TQ is shown on the left-side of the diagram below and that of the extended content on the right-side. (For simplicity, the value triples – equivalent of vertex-properties – are shown as boxes, attached to the subject node, containing the predicate-value pair.)

The change in this case looks much simpler. For each of the two relevant RDF triples that need to be connected (that is, used as the endpoints of an edge, or in RDF terminology, used as the subject or object component of a new triple), we can simply “quadify” it, that is, replace the triple with a quad that has the same subject, predicate, and object components as the original triple and has a newly created resource or vertex (triple-vertex) as its “named graph” component. The two triple-vertices created for the quadification of the two RDF triples are shown above as v4 and v5, respectively. We show only the relevant triples and quads (generated upon quadification) in the table below.

Most important thing to note here is that the original schema was not modified, but only expanded to include the new relationship type “helped”. The two relationship types “donatedTo” and “admittedTo” still continue to exist – they did not disappear. The triples that were converted to quads are still present – now as part of the quads – and pre-existing queries (such as, “Who donated to Top University?”) would continue to work without any change. A query designer does not need to re-learn a new version of the original schema to rewrite the original queries. (If interested in designing new queries, the query designer may want to learn about the newly added “helped” relationship type.)

RDF-Q does NOT need vertexification or quadification: Note that in an RDF Quads-Only model (that contains quads only, no triples), if the “named graph” component of a quad is used as a name that represents the triple portion of the quad, neither vertexification nor quadification is relevant. Since RDF does not impose any restrictions on use of such names of triples, the complex situations identified above – using triples as subject and/or object components of other triples – do not pose a problem in RDF-Q model.

Note: Although use of the “named graph” component of a quad in RDF-TQ and RDF-Q for representing edge-id conflicts with its use for partitioning of RDF data into a single unnamed and multiple named graphs, we do not address it in this article because PG also does not allow such partitioning of graphs. Nonetheless, we are currently exploring mixed use of the RDF “named graph” component – both as edge-id and for graph partitioning.

Related Work

Our March 2014 EDBT paper [1] discussed three approaches for representing property graphs in RDF: reification, named graphs, and subproperty (i.e., rdfs:subPropertyOf) based. The two types of transformation discussed here – vertexification and quadification – map directly to the methods utilizing reification and named graphs, respectively. The subproperty-based approach, very similar to the singleton-property based approach [2] introduced around the same time, is not discussed here in the interest of brevity because, with respect to schema backport-compatibility in an evolving graph, it has similar drawbacks as the reification-based (and hence, vertexification) approach, unless one (redundantly) stores the same triple in two different forms to allow old queries to continue to work.

Unlike [1], this article focuses mainly on the schema evolution and backward-compatibility problem for evolving graphs and explains with examples (see Appendix section below) how the quadification (named graph) based approach is able to guarantee backward-compatibility even as the schema evolves due to new data getting added to an existing graph.

Summary and Conclusion

First, based on the discussion above about the two types of transformation – vertexification and quadification – we can summarize their implications in the following table:

Also, the following table shows when to use which of these two types of transformations. We used the case of adding an “edge as endpoint of an edge” (listed in row #4 in the table below) earlier to show why and how vertexification is used for the RDF Triples-Only and Property Graph models whereas use of the (much simpler) quadification transformation was sufficient for the RDF Triples+Quads model. The Appendix section below will go through a complete example to illustrate each of the types of addition listed in the table below for the Property Graph and RDF Triples+Quads models.

Based on the discussions above (summarized in the two tables here), we posit that, with respect to maintaining backward compatibility of the evolving schema in the face of data additions to an existing graph, the following is a reasonable ranking of the different graph models:

RDF Triples-Only < Property Graph < RDF Triples+Quads < RDF Quads-Only

or, simply:

RDF Triples < Property Graph < RDF Quads

References

1. Das, S., Srinivasan, J., Perry, M., Chong, E., Banerjee, J. A Tale of Two Graphs: Property Graphs as RDF in Oracle. Published in Proc. Of 17th International Conference on Extending Database Technology (Athens, Greece, March 24–28, 2014) EDBT’14, on OpenProceedings.org.
2. Nguyen, V., Bodenreider, O., Sheth, A. Don’t Like RDF Reification? Making Statements About Statements Using Singleton Property. Published in Proc. of 23rd International Conference on World Wide Web WWW’14. April 2014.

Appendix: A Complete Example

To illustrate handling of change in graph data using both PG and RDF-TQ, we show below the steps involved in handling the cumulative content additions in the table shown at the beginning of this article. The changes for each step are shown in red color in the diagram. 

(Note: To avoid clutter in the diagrams below, RDF “value” triples, that connect subject resources to values, are shown like vertex-properties in PG. If the subject resource (vertex), due to quadification, represents a triple, then the value triples for that subject are shown like edge-property in PG.)