Storage and Navigation Operations on Graphs in Relational DBMS

• Grant number: 16/17330-1
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: December 01, 2016
• End date: November 30, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Caetano Traina Junior
• Grantee: Lucas de Carvalho Scabora
• Host 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.

Scientific publications

(11)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

CAZZOLATO, MIRELA T.; RAMOS, JONATHAN S.; RODRIGUES, LUCAS S.; SCABORA, LUCAS C.; CHINO, DANIEL Y. T.; JORGE, ANA E. S.; DE AZEVEDO-MARQUES, PAULO MAZZONCINI; JR, CAETANO TRAINA; TRAINA, AGMA J. M.. The UTrack framework for segmenting and measuring dermatological ulcers through telemedicine. COMPUTERS IN BIOLOGY AND MEDICINE, v. 134, JUL 2021. (18/24414-2, 16/17078-0, 16/17330-1, 20/07200-9, 20/11258-2, 20/10902-5)

OLIVEIRA, PAULO H.; SCABORA, LUCAS C.; CAZZOLATO, MIRELA T.; OLIVEIRA, WILLIAN D.; PAIXAO, RAFAEL S.; TRAINA, AGMA J. M.; TRAINA, CAETANO. Employing Domain Indexes to Efficiently Query Medical Data From Multiple Repositories. IEEE JOURNAL OF BIOMEDICAL AND HEALTH INFORMATICS, v. 23, n. 6, p. 2220-2229, NOV 2019. (16/17078-0, 15/15392-7, 16/17330-1)

FLOREZ, ALEXANDER Y. C.; SCABORA, LUCAS; ELER, DANILO M.; RODRIGUES-JR, JOSE F.; ALMEIDA, JR; GONZALEZ, AR; SHEN, L; KANE, B; TRAINA, A; SODA, P; et al. APEHR: Automated Prognosis in Electronic Health Records using multi-head self-attention. 2021 IEEE 34TH INTERNATIONAL SYMPOSIUM ON COMPUTER-BASED MEDICAL SYSTEMS (CBMS), v. N/A, p. 6-pg., 2021-01-01. (16/17330-1, 18/17620-5, 16/17078-0)

ZABOT, GUILHERME F.; CAZZOLATO, MIRELA T.; SCABORA, LUCAS C.; TRAINA, AGMA J. M.; TRAINA-, CAETANO, JR.; IEEE. Efficient Indexing of Multiple Metric Spaces with Spectra. 2019 IEEE INTERNATIONAL SYMPOSIUM ON MULTIMEDIA (ISM 2019), v. N/A, p. 8-pg., 2019-01-01. (18/24414-2, 16/17078-0, 16/17330-1)

ZABOT, GUILHERME F.; CAZZOLATO, MIRELA T.; SCABORA, LUCAS C.; FAICAL, BRUNO S.; TRAINA, AGMA J. M.; TRAINA, CAETANO, JR.; IEEE. UCORM: Indexing Uncorrelated Metric Spaces for Concise Content-Based Retrieval of Medical Images. 2019 IEEE 32ND INTERNATIONAL SYMPOSIUM ON COMPUTER-BASED MEDICAL SYSTEMS (CBMS), v. N/A, p. 6-pg., 2019-01-01. (18/24414-2, 16/17078-0, 18/06228-7, 16/17330-1)

CHINO, DANIEL Y. T.; SCABORA, LUCAS C.; CAZZOLATO, MIRELA T.; JORGE, ANA E. S.; TRAINA, CAETANO, JR.; TRAINA, AGMA J. M.; HOLLMEN, J; MCGREGOR, C; SODA, P; KANE, B. ICARUS: Retrieving Skin Ulcer Images Through Bag-of-Signatures. 2018 31ST IEEE INTERNATIONAL SYMPOSIUM ON COMPUTER-BASED MEDICAL SYSTEMS (CBMS 2018), v. N/A, p. 6-pg., 2018-01-01. (14/25125-3, 16/17078-0, 16/17330-1)

CAZZOLATO, MIRELA T.; SCABORA, LUCAS C.; NESSO-JR, MARCOS R.; MILANO-OLIVEIRA, LUIS F.; COSTA, ALCEU F.; KASTER, DANIEL S.; KOENIGKAM-SANTOS, MARCEL; DE AZEVEDO-MARQUES, PAULO MAZZONCINI; TRAINA-JR, CAETANO; TRAINA, AGMA J. M.. dp-BREATH: Heat maps and probabilistic classification assisting the analysis of abnormal lung regions. COMPUTER METHODS AND PROGRAMS IN BIOMEDICINE, v. 173, p. 27-34, MAY 2019. (16/17078-0, 16/17330-1, 18/24414-2)

SCABORA, LUCAS C.; SPADON, GABRIEL; OLIVEIRA, PAULO H.; RODRIGUES-JR, JOSE F.; TRAINA-JR, CAETANO; ACM. Enhancing recursive graph querying on RDBMS with data clustering approaches. PROCEEDINGS OF THE 35TH ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING (SAC'20), v. N/A, p. 8-pg., 2020-01-01. (16/17078-0, 16/17330-1, 18/17620-5, 18/20360-5, 17/08376-0, 19/04461-9)

CAZZOLATO, MIRELA T.; RAMOS, JONATHAN S.; RODRIGUES, LUCAS S.; SCABORA, LUCAS C.; CHINO, DANIEL Y. T.; JORGE, ANA E. S.; DE AZEVEDO-MARQUES, PAULO MAZZONCINI; TRAINA JR, CAETANO; TRAINA, AGMA J. M.; DEHERRERA, AGS; et al. Semi-Automatic Ulcer Segmentation and Wound Area Measurement Supporting Telemedicine. 2020 IEEE 33RD INTERNATIONAL SYMPOSIUM ON COMPUTER-BASED MEDICAL SYSTEMS(CBMS 2020), v. N/A, p. 6-pg., 2020-01-01. (16/17078-0, 20/07200-9, 17/23780-2, 18/24414-2, 16/17330-1)

CHINO, DANIEL Y. T.; SCABORA, LUCAS C.; CAZZOLATO, MIRELA T.; JORGE, ANA E. S.; TRAINA-, JR., CAETANO; TRAINA, AGMA J. M.. Segmenting skin ulcers and measuring the wound area using deep convolutional networks. COMPUTER METHODS AND PROGRAMS IN BIOMEDICINE, v. 191, JUL 2020. (16/17078-0, 16/17330-1, 14/25125-3, 18/24414-2)

NESSO-, MARCOS R., JR.; CAZZOLATO, MIRELA T.; SCABORA, LUCAS C.; OLIVEIRA, PAULO H.; SPADON, GABRIEL; DE SOUZA, JESSICA A.; OLIVEIRA, WILLIAN D.; CHINO, DANIEL Y. T.; RODRIGUES-, JOSE F., JR.; TRAINA, AGMA J. M.; et al. RAFIKI: Retrieval-Based Application for Imaging and Knowledge Investigation. 2018 31ST IEEE INTERNATIONAL SYMPOSIUM ON COMPUTER-BASED MEDICAL SYSTEMS (CBMS 2018), v. N/A, p. 6-pg., 2018-01-01. (13/21378-1, 17/08376-0, 16/17330-1, 15/15392-7, 16/17078-0)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

SCABORA, Lucas de Carvalho. Storage and Navigation Operations on Graphs in Relational DBMS. 2021. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.