Symbolic Graph Query Solving

Dominique Duval (1) , Rachid Echahed (2)

1 CASC - Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie
2 CAPP - Calculs algorithmes programmes et preuves

Property graphs play an important role in representing data bases in modern graph query languages. In this paper we focus on a particular class of graph queries known as Graph-to-Graph or CON-STRUCT queries. Such queries return graphs instead of tables when applied to actual Property Graphs. We propose a symbolic graph query solving procedure which combines rewriting techniques for goal solving as well as graph transformation techniques. The proposed procedure is proven sound and complete.

Mots clés: Operational semantics; Rewrite systems; Graph query languages

Domaines: Informatique [cs]

Dominique Duval, Rachid Echahed. Symbolic Graph Query Solving. 10th International Symposium en Symbolic Computation in Software Science, Aug 2024, Tokyo, Japan. pp.96-113, ⟨10.1007/978-3-031-69042-6_6⟩. ⟨hal-04772426⟩