Graph Data Model and Graph Query Language Based on the Monadic Second-Order Logic

With the wide application of graphs in various fields, graph query languages have attracted more and more attention. Existing graph query languages, such as GraphQL and SoQL, mostly have similar expressive power as the first-order logic or its extended versions, and are limited when used to express various queries. In this paper, since the graph data model is the base of the graph query language, we propose a new graph data model with the expressive power of monadic second-order logic (abbr. MSOL), and then present a more expressive SQL-like declarative graph query language named <inline-formula><tex-math notation="LaTeX">$SOGQL$</tex-math></inline-formula> to support more common queries efficiently. Specifically, a new graph calculus is first proposed based on MSOL for attributed graphs. Then, the new graph data model is proposed. Its graph algebra, which operates on graph sets, has seven fundamental operators such as union, filter, map, and reduce. Next, the graph query language <inline-formula><tex-math notation="LaTeX">$SOGQL$</tex-math></inline-formula> is proposed based on the graph data model. Since the graph algebra has the same expressive power as the graph calculus, <inline-formula><tex-math notation="LaTeX">$SOGQL$</tex-math></inline-formula> has the expressive power of MSOL, and can express queries with constraints on subgraphs. Moreover, applied with <inline-formula><tex-math notation="LaTeX">$SOGQL$</tex-math></inline-formula>, a prototype system named <inline-formula><tex-math notation="LaTeX">$SOGDB$</tex-math></inline-formula> is implemented. <inline-formula><tex-math notation="LaTeX">$SOGDB$</tex-math></inline-formula> is applied with <inline-formula><tex-math notation="LaTeX">$SOGQL$</tex-math></inline-formula>, and the experimental results show its efficiency.