MonacGraph: A Monadic Second-Order Logic Extended Graph Database System with Community-Aware Storage

Abstract

Graph database systems play a vital role in graph structure analysis across a wide range of application domains. Queries with set-level constraints on community structures are increasingly demanded in real-world applications. However, existing graph databases lack native support for both efficient monadic second-order logic (MSOL) query processing and fast community retrieval, hindering their applicability to such analytical tasks. In this paper, we present Monac- Graph, a graph database system that enables practical MSOL queries. MonacGraph features an efficient two-phase execution engine that minimizes redundant first-order clause evaluations. We propose SO-Gremlin, an extension of the Gremlin graph traversal language with intuitive syntax for set quantification. The system adopts LSM-Community as its storage backend, enabling efficient queries over precomputed graph structures. Additionally, MonacGraph provides a user-friendlyWeb interface for composing complex set-level queries and visualizing results in real time. A demonstration video can be found at https://www.youtube.com/watch?v=Eezdq9tzbJE.