We consider a core language of graph queries. These queries are seen as formulas to be solved with respect to graph-oriented databases. For this purpose, we first define a graph query algebra where some operations over graphs and sets of graph homomorphisms are specified. Then, the notion of pattern is introduced to represent a kind of recursively defined formula over graphs. The syntax and formal semantics of patterns are provided. Afterwards, we propose a new sound and complete calculus to solve patterns. This calculus, which is based on a rewriting system, develops only one derivation per pattern to be solved. Our calculus is generic in the sense that it can be adapted to different kinds of graph databases provided that the notions of graph and graph homomorphism (match) are well defined.
翻译：我们考虑图表查询的一种核心语言。 这些查询被视为在图形导向数据库方面需要解决的公式。 为此, 我们首先定义一个图形查询代数, 用于指定图形和图形同质性图集上的某些操作。 然后, 引入模式的概念, 以代表图解上的一种反复定义的公式。 提供了模式的语法和正式语义。 之后, 我们提出一个新的声音和完整的微积分来解模式。 这个基于重写系统的微积分只开发一个要解的图案。 我们的微积分是通用的, 因为它可以适用于不同类型的图形数据库, 前提是图表和图形同质性( 匹配) 的概念得到了很好的界定 。
相关内容
微信扫码咨询专知VIP会员