A Pseudo-Boolean Formulation for Graph Database Queries

Abstract

Graph queries such as neighborhood exploration, friend-of-a-friend, and path finding are fundamental operations in graph databases. Traditionally, these queries are implemented using procedural traversal algorithms tightly coupled to the underlying graph structure. In this paper, we present a declarative formulation of graph database queries using pseudo-Boolean constraints. Vertices and edges are mapped to Boolean variables, and traversal semantics are enforced through cardinality constraints that regulate vertex roles and edge selection. The proposed formulation encodes first-degree queries, friend-of-a-friend queries, and shortest path queries as instances of constraint satisfaction or optimization problems. Preliminary experimental results indicate that the encoding is consistent and scales linearly with respect to the number of vertices and edges, although it is not yet competitive with specialized graph traversal algorithms in execution time. Nevertheless, the experimental analysis highlights clear directions for improvement, including solver specialization, incremental constraint generation, and optimized model enumeration, suggesting that pseudo-Boolean techniques can become a viable alternative for declarative graph querying.