Graph data mining is a well-studied area of research because of numerous applications in fields such as social data mining and biochemical analysis [1]. Recently, there has been a growing interest in applying graph mining techniques to relational databases, as viewing them as graph data exposes inherent semantics [3] [4]. Since relational databases are a de facto standard in data warehousing, applying graph mining techniques to mine latent information from the massive relational data seems even more attractive.
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 defining a new language, R2RML [2], but the language is limited in describing some semantic aspects of graph conversion. For example, it cannot used to describe a vertex that combines several attributes (fig. 1). It also fails at describing semantics not apparent in relational schemata, such as events that could be connected in chronological order (fig. 2).
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.
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. {(k 1 , l 1 ), (k 2 , l 2 ), . . . , (k n , l n )}, where each key in k 1 , . . . , k n corresponds to some attribute and each l in l 1 , . . . , l n is some value in D. An edge e is directed and denoted by (v s , v t ), where v s is the source vertex and v t is the target vertex. Both v s and v t are in V . Given some rule set Γ and D, framework must return E and V such that elements satisfy the specifications of Γ .
The conversion takes place in two phases -the first phase discovers relationships within each tuple, while the second phase establishes additional relationships among the vertices constructed from the first 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. For each c in C s or C t , the corresponding value u in each tuple is paired with the corresponding k in K s or K t 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 figure 2.1. The purpose of specifying the alias sets K s and K t is to combine semantically identical attributes together. For example, consider a case where relation r 1 has a foreign key constraint that references a primary key of another relation r 2 . Their attribute names might be different, 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 figure 2.1 that some vertices have common key configurations (e.g. {id, date}). We call such key configurations vertex schemata.
Selection predicate p is similar to the counterpart of relational algebra. It can be directly used in SQL queries to filter out tuples. For each rule, the framework retrieves a set of tuples from T that satisfy the predicate and produces exactly one edge of (v s , v t ), which is added to E. The framework will also attempt to add v s and v t 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 specifies the followings.
1. two sets of vertex schema (K s , K t ) 2. a bit (b) to indicate whether the generated edge is bidirectional or not 3. a vertex selection predicate (q) to filter vertices For each rule in Γ 2 , vertices with schema K s or K t are considered as source or target vertices of an additional edge. Given the vertices, the framework further filters them using vertex selection predicate q. An example of such edge generation is shown in figure 2.1. q is different 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 K s or K t . 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 efficiency. 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.
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 affects the information contained in it.