Graph data mining is highly versatile, as it applies not only to graph data but to relational data, as long as it can be represented as pairs of relationships. However, modeling RDBs as graphs using existing methods is limited in describing semantics of the relational data. In this paper, we propose a two-phased graph-modeling framework that converts any RDB to a directed graph with richer semantics than previously allowed. We implemented the framework and used it for analyzing medical records of diabetes patients.1
Graph data mining is a well-studied area of research because of numerous
applications in elds such as social data mining and biochemical analysis [
However, modeling relational databases as graphs is not straight-forward,
because it is challenging to devise appropriate models that expose underlying
semantics. W3C formalized the graph-modeling process by de ning a new
language, R2RML [
We propose a new framework to solve the current problem of modeling RDBs as graphs. The framework converts any RDB into a directed graph given some conversion rules (sec. 2). We have also implemented a program based on RDB2Graph (R2G) to analyze medicals records of diabetes patients. 1 This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea Government(MSIP) (No. 20110030812). Given a relational database D and a set of modeling rules, the framework generates a directed graph. The output of the framework is edge set E and vertex set V . Each vertex is a set of key-values, i.e. f(k1; l1); (k2; l2); : : : ; (kn; ln)g, where each key in k1; : : : ; kn corresponds to some attribute and each l in l1; : : : ; ln is some value in D. An edge e is directed and denoted by (vs; vt), where vs is the source vertex and vt is the target vertex. Both vs and vt are in V . Given some rule set and D, framework must return E and V such that elements satisfy the speci cations of . 2.1
The Two-Phase Conversion The conversion takes place in two phases | the rst phase discovers relationships within each tuple, while the second phase establishes additional relationships among the vertices constructed from the rst phase. Thus, is an union of 1 and 2, the rules for both phases respectively. Splitting in two phases is necessary because it allows incorporation of implicit relationships not apparent from the relational database itself.
Phase I: Tuples to Edges In order to create new vertices and edges from the relational database, a set of rules 1 must specify the followings: 1. a target relation (r) 2. two sets of attributes (Cs, Ct) from relation r to indicate which values of each tuple in r are stored as l in key-value pairs of source or target vertices 3. two sets of key aliases (Ks, Kt) to indicate k in key-value pairs of source or target vertices. 4. a bit (b) to indicate whether the edge is bidirectional or not 5. a selection predicate (p) to lter tuples.
For each c in Cs or Ct, the corresponding value u in each tuple is paired with the corresponding k in Ks or Kt to form a key-value pair (k, u), which is added to the generated source or target vertex. An example of edge generation is presented in gure 2.1.
The purpose of specifying the alias sets Ks and Kt is to combine semantically identical attributes together. For example, consider a case where relation r1 has a foreign key constraint that references a primary key of another relation r2. Their attribute names might be di erent, but they are identical semantically. By having the ability to give a common key for the attributes, we are able to generate common vertices. It is apparent from gure 2.1 that some vertices have common key con gurations (e.g. fid; dateg). We call such key con gurations vertex schemata.
Selection predicate p is similar to the counterpart of relational algebra. It can be directly used in SQL queries to lter out tuples. For each rule, the framework retrieves a set of tuples from T that satisfy the predicate and produces exactly one edge of (vs; vt), which is added to E. The framework will also attempt to add vs and vt into V , if they do not exist already. At the end of phase I, E and V are generated and passed to phase II.
Phase II: Vertices to Edges Given the graph constructed from the previous phase, E and V , and phase II rules 2, the framework constructs additional edges that satisfy 2. In this phase, each rule of 2 speci es the followings. 1. two sets of vertex schema (Ks, Kt) 2. a bit (b) to indicate whether the generated edge is bidirectional or not 3. a vertex selection predicate (q) to lter vertices
For each rule in 2, vertices with schema Ks or Kt are considered as source or target vertices of an additional edge. Given the vertices, the framework further lters them using vertex selection predicate q. An example of such edge generation is shown in gure 2.1.
q is di erent from p of 1 | in p, left-hand side variables are references to some attributes of a relation; in q, left-hand side variables are references to some keys of either Ks or Kt. Phase II produces E and V as well, but with additional edges that satisfy 2. Our implementation of the framework, SRCGraphModeler (SGM), is written in C#, and it connects to Oracle 11g based RDB. SGM converts each rule into PL/SQL procedures in order to run them on the database server, improving runtime e ciency. Using SGM, we converted medical records of diabetes patients into various graph models, then we applied graph analysis on the graphs to extract correlation among medications and symptoms. 3
We have presented a graph-modeling framework that enables semantically richer conversions than that attempted by previous works. As future works, we plan to study how transformation of RDB data to graph data a ects the information contained in it.