Graph databases implementing the property graph model provide schema-flexible storage and support complex, expressive queries like shortest path, reachability, and graph isomorphism queries. However, both the flexibility and expressiveness in these queries come with additional costs: queries can result in an unexpected, empty answer. To understand the reason of an empty answer, a user normally has to create alternative queries, which is a cumbersome and time-consuming task. To address this, we introduce di↵-queries, a new kind of graph queries, that give an answer about which part of a query graph is represented in a data graph and which part is missing. We propose a new algorithm for processing di↵-queries, which detects maximum common subgraphs between a query graph and a data graph and computes the di↵erence between them. In addition, we present several extensions and optimizations for an established maximum common subgraph algorithm for processing property graphs, which are the foundation of state of the art graph databases.
['Elena Vasilyeva', 'Maik Thiele', 'Christof Bornhövd', 'Wolfgang Lehner']
GraphMCS: Discover the Unknown in Large Data Graphs