Schema Discovery in Property Graphs Using Formal Concept Analysis

Abstract

In den letzten Jahren hat das Property-Graph-Datenmodell zunehmend an Popularität gewonnen, da es die Darstellung komplexer und stark vernetzter Daten ermöglicht. Ein wesentlicher Grund für die weitverbreitete Nutzung von Graphdatenbanken ist ihre inhärente Flexibilität. Sie erfordern in der Regel kein vordefiniertes Schema und unterliegen keiner starren Struktur. Diese Flexibilität macht sie besonders geeignet für sich schnell entwickelnde Umgebungen und unterstützt gleichzeitig eine skalierbare Datenverarbeitung. Allerdings bringt dieser schemafreie Ansatz auch verschiedene Herausforderungen mit sich. Er kann zu Inkonsistenzen führen, die Optimierung von Anfragen erschweren oder die Datenintegration komplizieren. Die manuelle Definition eines Schemas ist oft unpraktikabel, da sie umfangreiches Domänenwissen erfordert und Graphdatenbanken oft sehr groß sind. Dies führt zum sogenannten Schema-Discovery-Problem. In dieser Arbeit adressieren wir das Schema-Discovery-Problem in Property-Graphs und präsentieren eine neuartige Methode zur automatischen Schema-Extraktion auf Basis der "Formal Concept Analysis". Formal Concept Analysis ist ein mathematisches Framework, das primär für die Datenanalyse genutzt wird, dessen Werkzeuge sich jedoch auch für die Schema-Extraktion als besonders geeignet erweisen. Wir schlagen eine vollständig automatisierte Methode zur Schema-Extraktion für Property-Graphs vor und implementieren diese. Dabei nutzen wir Formal Concept Analysis, um Knoten- und Kantentypen anhand der Ähnlichkeit ihrer "Labels" und "Properties" zu identifizieren. Unsere Methode wird experimentell mit dem aktuellen Stand der Technik verglichen, und wir entwickeln einen Prozess zur synthetischen Graphgenerierung, um eine detaillierte Evaluierung zu ermöglichen. Darüber hinaus geht diese Arbeit auf die Herausforderung ein, Schemata für mehrere Property-Graphs zu extrahieren. Dazu wird ein Schema-Merging-Verfahren vorgestellt, das iterativ auf die extrahierten Schemata angewendet werden kann, um mehrere Graphen zu berücksichtigen.

In recent years, the property graph data model has gained increasing popularity due to its ability to represent complex and highly interconnected data. One of the key reasons for the widespread adoption of graph databases is their inherent flexibility. They typically do not require a predefined schema and impose no rigid structure. This flexibility makes them well-suited for rapidly evolving environments while also supporting scalable data processing. However, while this schema-less approach is desirable, it also presents several challenges. It can lead to potential inconsistencies, hinder query optimization or complicate data integration. Manually defining a schema is often impractical due to the required domain knowledge and the size of graph databases, giving rise to the schema discovery problem. In this thesis, we address the schema discovery problem in property graphs and present a novel schema discovery method based on Formal Concept Analysis. Formal Concept Analysis is a mathematical framework primarily used for data analysis, and its tools naturally lend themselves to schema extraction. We propose and implement a fully automatic schema discovery method for property graphs, leveraging Formal Concept Analysis to identify node and edge types based on the similarity of their labels and properties. Our method is experimentally evaluated against state-of-the-art approaches, and we develop a process for synthetic graph generation to facilitate a more intricate evaluation. Additionally, this thesis addresses the challenge of extracting schemas from multiple property graphs by introducing a schema merging method, which can be iteratively applied to the extracted schemas to accommodate multiple graphs.