Analysis of Complex Networks

9.9 Subgraph Isomorphism Solution in SQL

The concept of organizing data into relations was first proposed by Codd in 1970 [111] together with rules for integrity constraints and operators for the manipulation of data. These relational operators form the basis of SQL, which is standard across different database platforms today. The relational model is versatile and many problems can be tackled using it in preference to custom-written applications or algorithms. One such problem is subgraph isomorphism for which data can be visualized as a hypergraph [112] defined by a pair (X, E), where X is a set of vertices and E is a set of hyperedges, each of which is a nonempty subset of X. Thus one hyperedge can connect with more than one pair of vertices. In relational database terms, X is a set of attributes describing the application fields and E is a set of relations (tables without ordered rows). Chemical graphs where edges and vertices have attributes, like bond type and element type, can be represented as hypergraphs and therefore can be stored in a relational database using two tables: atoms and bonds. The atoms table contains vertices and their attributes, while the bonds table contains data on pairs of atoms and the attributes associated with their bond type. These tables are shown below:

As the graph is nondirectional, the bonds table must have two records for each pair of atoms. ...