A Model and Query Language for Property Graph Databases

Abstract

Graph databases are increasingly being used for modeling complex networks using the property graph data model, which annotates nodes and edges in a graph with property-value pairs. However, existing research primarily focuses on static graphs, overlooking the crucial temporal aspects necessary for accurately representing dynamic, real-world environments. This dissertation addresses this limitation by introducing a novel approach for managing and analyzing changes across time in graph databases. The main contribution of this work is the development of a temporal graph model, denoted T-PG, which comes equipped with a high-level graph query language denoted T-GQL. T-PG extends traditional graph databases to include temporal dimensions, allowing nodes and edges to be timestamped and enabling the representation of time-series data as node properties. T-GQL facilitates querying temporal graph data in an elegant and concise way. For example, we can express queries asking for the friends of friends of a specific individual who lived in the same location during overlapping time periods, along with the time when this occurred. To validate the proposal, this dissertation includes a proof-of-concept implementation using Neo4j, a leading graph database system. This implementation features a client-side interface for querying Neo4j with T-GQL, showcasing the effectiveness of our approach. Additionally, the dissertation applies this model to a real-world case study over transportation networks equipped with sensors (also called sensor networks). The dynamics of these networks can be naturally captured by temporal graph models, allowing an effective analysis of many problems of interest for researchers and practitioners. Further, paths are first-class citizens in graph data models. Therefore, we explore various classes of temporal paths, and identify and characterize the classes of temporal paths that can be defined in sensor networks using Allen’s temporal algebra. This work shows that, out of the 8192 possible interval relations in the algebra, only eleven satisfy two critical properties defined in this work: transitivity and robustness. These properties ensure that the temporal paths are both consistent and applicable to real-world problems. The relevance of these properties is illustrated through an example analyzing salinity levels in the Scheldt river in Flanders, Belgium, in sections close to the North Sea during high tides. In summary, this dissertation introduces T-PG and T-GQL, addressing the temporal aspects of graph data and enhancing the analysis of dynamic networks. The proposed framework is validated through implementation and real-world application, bridging the gap between static graph models and the evolving nature of real-world data