Storage and navigation operations on graphs in relational DBMS
| Grant number: | 16/17330-1 |
| Support type: | Scholarships in Brazil - Doctorate |
| Effective date (Start): | December 01, 2016 |
| Effective date (End): | November 30, 2019 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science |
| Principal Investigator: | Caetano Traina Junior |
| Grantee: | Lucas de Carvalho Scabora |
| Home Institution: | Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil |
Abstract The amount of modern applications using graph structures to represent data has increased significantly. In these structures, the data elements, i.e. the entities, are stored as vertices along with a network of interrelationships, representing the interactions among the entities as edges. The current Database Management Systems (DBMS) based on the Relational Model make no distinction between the data elements that are identifiable (i.e. the vertices) and the elements that represent only interrelationships (i.e. edges). Therefore, Graph Management Systems (GMS) are being developed following the Graph Theory, but not necessarily adopting the Relational Model. Consequently, such GMS cannot employ the standard access language SQL, typical of Relational DBMS (RDBMS). Often referenced as a kind of NoSQL (Not only SQL) manager, the GMS are used because they offer tools that not only speed up the development of new applications, but also facilitate the declaration of complex queries. However, up to now, none of them has a conceptual model to provide the representation and to formalize the data manipulation. Hence, a GMS is not necessarily compatible with other GMS, making portability among applications practically nonexistent. This brings long-term uncertainties to the institutions that rely on those tools since there is no guarantee that the GMSs will remain applicable in the future, not even that they will continue to exist. Considering this gap, this research project aims at developing data management solutions that meet the requirements of graph-based modern applications, while maintaining the Relational Model as a conceptual reference. Briefly, we start from the premise that the RDBMS can provide not only graph modeling, but also meet technical requirements to support the navigation among relationships, providing: (i) the modeling of vertex sets and edge sets of a graph as special cases of sets; and (ii) techniques and tools to process queries over graphs. Such queries can be declared by commands from an SQL extension, yet without changing its essence. In this context, this project aims at defining and developing the concept of linkage, in order to promote the management and manipulation of relationships among objects, both based on the Relational Model. Finally, we will also target the development of the required modules for extending an RDBMS, in order to evaluate and validate the new concepts. | |