A Logical Approach to Graph Databases

Abstract

Graph databases are now playing an important role because they allow us to overcome some limitations of relational databases. In particular, graph databases differ from relational databases in that the topology of data is as important as the data itself. Thus, typical graph database queries are navigational, asking whether some nodes are connected by paths satisfying some specific properties.
While relational databases were designed upon logical and algebraic foundations, the development of graph databases has been quite ad-hoc. In this sense, the aim of this paper is to provide them with some logical foundations. More precisely, in previous work we introduced a navigational logic, called GNL (Graph Navigational Logic) that allows us to describe graph navigational properties, and which is equipped with a deductive tableau method that we proved to be sound and complete.
In this presentation we will introduce a new formal model for property graphs. Then, we will show how graph queries à la Cypher can be expressed using a fragment of GNL, defining for them a logical and an operational semantics, based on the inference rules for GNL. Finally, we show that both semantics are equivalent.

Date
Friday, March 24, 2023 15:00 Europe/Paris
Event
GReTA seminar
Zoom registration: click here! Please consider joining the meeting already within the 15min prior to the start of the seminar to ensure your setup is functioning properly. You may connect with either the Zoom web or Zoom desktop clients.

Please note that the meeting will be recorded and live-streamed to YouTube:

Elvira Pino
Elvira Pino
Associate Professor in Computer Science

Elvira Pino is an associate professor at the Universitat Politècnica de Catalunya, Spain, where she received her PhD in 1999. At the beginning of her research career, she worked on Logic Programming, specifically, on how categorical foundations together with a suitable algebraic formulation could contribute to solve some problems existing at that time. In recent years, her research has focused on graph transformation and synchronization and, more recently, on the definition of a navigational graph logic as a first step to provide algebraic and logical foundations for graph databases which is her present ongoing work.

Fernando Orejas
Fernando Orejas
Professor of Computer Science

Member of the ALBCOM Research Group of the Department of Computer Science, Technical University of Catalonia, in Barcelona. (These are the English translations of Departament de Ciències de la Computació and Universitat Politècnica de Catalunya.)