Research by IMFD researchers awarded at SIGMOD/PODS

June, 2023.- Each year, the Association for Computing Machinery (ACM) -founded in 1947 as the first scientific and educational society in the field of computing- organizes the SIGMOD/PODS Conference. Currently, the event is considered one of the most important international forums in the field of data management, where researchers gather to explore new ideas, results, techniques, and experiences. It is in this context that the best papers presented are also awarded: in the 2023 edition, held from June 18 to 23 in Seattle (USA), one of these awards goes to a study co-authored by Domagoj Vrgoč, a professor at the Instituto de Ingeniería Matemática y Computacional de la P. Universidad Católica de Chile and researcher at the Millennium Institute Foundational Research on Data (IMFD), and Renzo Angles, a professor at the Departamento de Ciencias de la Computación de la Universidad de Talca and IMFD researcher

According to the organizers, the study titled “PG-Schema: Schemas for Property Graphs” was chosen as the “Best Industry Track Paper” due to its exceptional quality, originality, and contribution to the field of graph databases, and is the result of joint work by researchers from several higher education institutions such as the University of Warsaw (Poland), the University of Bayreuth (Germany), the University of Edinburgh (Scotland), and companies such as Amazon Web Services, TigerGraph, Neo4J, and RelationalAI, among others.

“SIGMOD/PODS is one of the largest conferences in the world and one of the most prestigious in the field of databases. Every year it brings together nearly 2,000 participants. It has one section called SIGMOD, which covers the more practical side, and PODS, which focuses on the more theoretical field,” says Domagoj Vrgoč, PhD in Computer Science from the University of Edinburgh (Scotland). Regarding the paper itself, he explains that the award reflects the fact that the study is “work with considerable impact on industry and done in collaboration with people from industry. In fact, it’s a paper with more than 20 authors, which represents a very large collaboration that took quite a long time and solves a concrete problem that exists in the field.”

Renzo Angles mentions that this article was developed by members of the “Property Graph Schema Working Group” within the Linked Data Benchmark Council (LDBC). “In mid-2019, we began discussing the characteristics of graph-based data models, and the absence of a standard way to represent their structure or schema. In this sense, the article proposes a formalism for specifying schemas for property graphs, that is, a language that allows precisely describing the types of nodes, edges, and properties existing in a graph-based database, as well as specifying simple and complex constraints on these types and their relationships.”

The potential of the study

In the field of databases, there is a very important branch known as graph databases, in which data is modeled conceptually. “Every entity you want to represent, such as a person, a city, or a workplace, becomes a node in your graph. And when you want to link data, you use edges that indicate the connection between the different entities. This means it’s a model that doesn’t have a fixed structure; when you want to add a new entity, you simply connect it through edges,” says Vrgoč.

This characteristic means there is no need for a fixed structure, as occurs in the more classical area of this research field, which covers relational databases. “Graph databases don’t have a schema, understood as a description that tells you ‘everything looks like this,’ which does exist very strongly in the world of relational databases,” comments the academic. On the other hand, he adds, in a graph database there can be “nodes representing people, but some include only name and country, while others show only a name and age. That’s why not everything needs to be structured. In relational databases, however, everything must have the same attributes.”

According to Vrgoč, this feature gives graph databases a lot of flexibility, but it can also create a problem “when there is a very large knowledge graph, where a schema is indeed needed to tell you what type of data you have.”

The study helps fill that gap. “The paper is called PG-Schema because it refers to a language that allows defining the schema for a graph database format widely used in industry called ‘property graphs.’ And that’s exactly what the work is, a language that allows compactly describing what type of data I have in my database without having to show all that data. It is based on a certain syntax, develops a semantics, and makes that definition easier.”

Vrgoč’s contribution to the paper consisted of establishing a grammar for that language: “The work I did with a subgroup of that international team, mainly with Filip Murlak (University of Warsaw, Poland) and Wim Martens (University of Bayreuth, Germany), was to design a base language that allows describing what I have in a node, what I can have on an edge, how they connect, and what my graph looks like overall. Then, together with the rest of the team, we developed several extensions that ultimately led to this language.”

“The development of the article took quite a long time because there was a discussion between the real needs raised by the group members working in industry, and the theoretical foundations put forward by the members from academia. The final result is a schema specification language that allows representing graph schemas with different types of constraints, while respecting important theoretical conditions,” says Renzo Angles, who is confident the article will impact the development of schema specification languages for graph-based database systems.

The researchers hope that, given its potential, this language will be incorporated into a new ISO standard for the graph query language. “Our work is a proposal that provides input for the group defining that standard, but it is not yet something established in industry. For now, it is a research work,” states Domagoj Vrgoč.

All the authors of the study are: Renzo Angles (Universidad de Talca); Angela Bonifati (Univ. of Lyon); Stefania Dumbrava (ENSIIE); George Fletcher (Eindhoven University of Technology the Netherlands); Alastair Green (Mr); Jan Hidders (Birkbeck, University of London)*; Bei Li (Google); Leonid Libkin (University of Edinburgh & RelationalAI); Victor Marsault (UPEM / CNRS); Wim Martens (University of Bayreuth); Filip Murlak (University of Warsaw, Poland); Stefan Plantikow (Neo4j); Ognjen Savkovic (Free University of Bozen-Bolzano); Michael Schmidt (Amazon Web Services); Juan Sequeda (data.world); Sławek Staworko (RelationalAI); Dominik Tomaszuk (University of Bialystok); Hannes Voigt (Neo4j); Domagoj Vrgoc (Pontificia Universidad Catolica de Chile); Mingxi Wu (Tigergraph inc); Dušan Živković (Integral Data Solutions)

Source: IMC UC