论文标题
基于规则的图形查询语言的操作语义
A Rule-based Operational Semantics of Graph Query Languages
论文作者
论文摘要
我们考虑图形查询的核心语言。这些查询被视为相对于面向图形的数据库解决的公式。为此，我们首先定义一个图形代数，其中指定了图形和图形同构的某些操作。然后，引入了模式的概念，以代表图形上递归定义的公式。提供了模式的语法和形式语义。之后，我们提出了一种新的声音和完整的演算来解决模式。这种基于重写系统的演算仅开发每个模式的派生。我们的演算是通用的，因为只要图形和图形同构（匹配）的概念得到很好的定义，就可以适应不同种类的图形数据库。
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.
