图查询：从图中提取具有特定结构的子图的新形式查询

电子笔记在理论计算机科学50第3期（2001年）。GT-VMT 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html10页查询类图数据S.弗莱斯卡湾Furfaro，S.GrecoDEIS，卡拉布里亚大学，87036 Rende（CS），Italyfflesca，furfaro，grecog@si.deis.unical.it摘要最近的研究已经深入研究了半结构化数据和可以通过图表示的数据（例如，面向对象数据、XML数据等）的查询问题通常，对图类数据的查询（称为路径查询）是通过表示图中路径的正则表达式来路径查询的结果是通过指定正则表达式表示的路径可到达的节点集在本文中，我们研究的问题，提取一个子图满足给定的性质，从一个给定的图表示一些信息。我们提出了一种新形式的查询，称为图查询，其答案是（标记）具有特定结构的图，从源图中提取。我们表明，一个简单的形式的图文法可以protably用于DE NE图查询。在数据库D上使用文法G进行图查询的结果是D的标记子图与从G导出的图“匹配”。 我们考虑不同类型的图语法，可用于查询图形类数据，并考虑其表现力和复杂性。1介绍网络的广泛使用重新引起了人们对已经在其他环境中以不同目的研究的问题的兴趣，特别是在查询图形数据的问题中。事实上，图可以作为一个抽象模型来表示各种各样的数据，如半结构化文档，面向对象的数据，XML数据等[1，2，6，18]。 许多在关系数据库上可以很容易表达的查询在图类数据上就不那么自然了。搜索这种类型的数据通常需要在图形中导航，以搜索所需的信息。最近，已经提出了几种语言和原型来搜索像Web这样的图形数据[1，4，5，8，13，19，20，22]。所有这些语言都允许我们表达（声明性）导航查询，称为路径查询，其答案是 图是从某个节点通过一个路径Speci可达的图。c2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2GT-VMT 2001 {S.弗莱斯卡湾Furfaro和S.Greco[2019 - 04 - 19]【2019 - 04 - 19 00：01：00】然而，这种导航查询并不完全令人满意，因为在许多情况下，我们希望表达验证图是否具有给定结构（例如，树或链）的查询，或者从源图中提取满足某些性质的子图。本文研究了从给定的数据图中抽取满足某些性质的子图（节点和边的一致子集）的问题。我们提出了一种新的形式的查询，称为图查询，其答案是（标记）具有特定结构的子图。图查询基于图语法[12]，用于定义必须提取的子图的结构属性。图文法是由一组重写规则（或产生式）组成的图重写系统。就像标准文法的产生式定义如何用字符串替换非终结符（或一组符号）一样，图文法的产生式定义如何用子图替换图中的节点（或边）。图文法定义了一类具有共同结构性质的图（例如完全图类，树类等）：这样的类被命名为图形语言。讨论一个图是否属于某种图语言，就等于讨论这种图的结构是否满足该语言的结构性质。例如，我们可以通过简单地定义一个生成树的图语法，然后证明该图属于由该语法生成的语言，来声明某个图是一棵树。我们的范例允许定义一个查询，搜索在一个给定的图属于一个给定的图语法定义的语言的子图。这是一种新奇的方式：虽然其他查询语言打算在图中找到一些节点，使得这些节点中的每一个具有特定属性（例如，作为路径查询的答案的节点的集合），但是我们的模型搜索整个子结构。让我们考虑下面的例子。假设我们想从一个包含java文档的网站上提取所有关于swing类的在线书籍。特别是，我们有兴趣在提取网页有一个层次结构，如以下gure所示：路径查询无法识别以这种方式结构化的在线图书，而使用图语法很容易描述这样的结构3GT-VMT 2001 {S.弗莱斯卡湾Furfaro和S.Greco在下面的部分中，我们通过引入节点替换上下文无关图文法的限制形式[12]来定义我们的图查询语言，称为解析图文法，并指定这些文法如何识别原始数据图的子图。我们指出，我们的范例也可以用来创建新的图形。然而，在本文中，我们只考虑子图的提取。2NR图文法节点替换（NR）图文法生成标记有向图。NR图文法的产生式是X！（D; C）其中X是非终结节点标签，D是图，C是连接指令集。根据这样的产生式，图H的重写步骤包括从H中移除标记为X的节点u，将D添加到H，以及在D和H之间添加边，如由C中的连接指令指定的对（D; C）可以看作是一种新的对象类型，重写步骤可以看作是用图H中的（D; C）替换节点u。直觉上，这些对象是非常自然的：它们是可以嵌入到环境中的图形。它们的正式定义如下。设是节点标签的字母表和边标签的字母表。一个有嵌入的图是一个图对K =（D; C），其中D是和上的图，CNfin; outg是K的连接关系。 每个元素（;1;2; v; d）2 C是K的连接指令，并且通常被写为（;1=2; v; d）。一个图的具有嵌入K的分量将被表示为NK; EK;K和CK。直观地说，对于一个有嵌入K的图，连接指令（;1=2; v; out）的含义如下：如果有一条1-标号的边从一个被K取代的节点u到一个-标号的节点w，那么嵌入机制定义了一条2-标号的边从v到w。类似地，连接指令（;1=2; v; in）的含义如下：如果从一个标记的节点w到一个节点u有一条1标记的边，该边已被K取代，则嵌入机制定义从w到v的一条2标记的边代替边标签的特征称为动态边标签。设H是和上的图，K是嵌入在相同字母表上的图，v 2 NH.用K代替H中的v记为H[v=K]。在下面的形式（;=; v; a）的连接规则（即不重新标记边的规则）被简单地写为（;; v; a）。412H1v;pHGT-VMT 2001 {S.弗莱斯卡湾Furfaro和S.Greco例2.1由以下产生式1和2定义的文法G（或者，等同地，由生产0 和0）描述了一种语言，链：0 和0 分别具有相同的含义，和，但在0和01 21 21 2连接规则用图形表示下图说明了通过G产生的链推导：定义2.2节点替换（NR）文法是元组G =（;; P;S），其中是标签的字母表，是终端标签的字母表，P是产生式的集合，S2是初始的非终端符号。 一个产品的形式是X！（D）其中X 2且（D; C）是具有嵌入的图。2出现在产品右侧的图形可以是空的，并且是X！（;）将被简单地表示为X！............................... 让G=（;;P;S）是一个NR文法. 设H和H0是两个图，设v2N，设p：X！ （D;C）是G. 那么，我们就去那里 如果（v）=X和H0，则直接从H导出（并写作H）H0，或仅为H）H0） =H[v=D]。更重要的是，我们是一个H0 是从H导出的，如果有一个nite序列H）H））H0。因此，图文法定义了一类具有共同结构性质的图。由PG生成的图的集合称为图语言，记为L（PG）。3查询数据图我们首先定义一个简单的图形模型的字母表与两种不同类型的符号：常数和变量。变量可以取任何值，因此它可以与任何常量相关联。 在下文中，常量由以数字或小写字母开头的字符串表示（例如b1），变量名由以美元开头的字符串表示（例如$b1），非终结符由以小写字母开头的字符串表示（例如X）。5GT-VMT 2001 {S.弗莱斯卡湾Furfaro和S.Greco定义3.1给定一个字母表，上的图是一个元组G =（N; Ei），其中N是一组节点，Ei f（u; v）ju; v 2 N; 2 g是一组标记边，并且：N！是一个节点标记函数。如果G只包含常数，则称G为数据图，否则称G为查询图。2（一般）图所使用的字母表也可以包含非终结符符号，而不是终结符符号（变量和常数）。因此，数据图只包含常数，它们用于表示输入数据库，查询图用于表示可以“映射”到数据图上的图，一般图用于推导过程的中间状态。图文法可以用来表示来自给定数据图的子结构。给定一个图，我们将用T_err（）表示通过删除用非终结符标记的节点和连接到被删除节点的弧而导出的子图。注意，如果图是连通的，并且所有的终端符号都没有向外的弧，那么T erados（）也是连通的。例3.2由图1的产生式构成的图文法G定义了一种由树构成的语言。Fig. 1. 图文法德宁树图2示出了借助于G产生式的树导出。 注意到图二. 图推导该文法所定义的语言中的树的根节点具有特定的数据标号（n1），内部节点具有标号$i，叶节点具有标号$l。2由于在这种情况下，我们对生成新的图不感兴趣，而只对识别给定数据图的子图感兴趣，因此我们将不考虑由语法生成的整个语言，而只考虑包含识别输入数据图的某个部分的图的子集。为此，我们定义了一个映射从查询图到子图的一个给定的数据图。6GT-VMT 2001 {S.弗莱斯卡湾Furfaro和S.Greco定义3.3让 =（N; E;）是在 和D =（ND; ED;D）上的数据图。从到D的映射是分别将N中的节点映射到ND中的节点以及将E中的边映射到ED中的边的全函数映射，使得i）对于每个n 0 de n2N，（n）=（n（n））或（n）是变量标签，ii) 对于每个arc（u;v）2E，re是arc（'（u）;;'（v））2ED，使得或者=或者是变量，以及iii）不存在两个节点u和v使得（u）=（v）并且“（u）=”（v）（即， 具有相同标签的两个节点不能关联到相同的节点）。2如果存在从S到查询图（S）的导出和从S到D的映射，则数据图D由图语法PG识别。由PG识别的数据图的集合被表示为DL（PG）。由PG识别的给定数据图D的子图的集合表示为DL（PG; D）。定义3.4L和D是一个数据集。D上的映射对是pair（;'）其中，是一个通用图，'是从T err（）到D的数据映射。2注意，T eradication（）是一个查询图，即节点标号可以是常量或变量的图与嵌入式图一样，映射对可以被视为一种新类型的对象，它由映射到给定数据图上的查询图（源自图语法）组成查询图的推导从解析语法可以扩展到映射对。 设D是一个数据图，PG 是一个文法，（;'） 是 D 上 的 一个 映射对. 本文证明了映射对（;） 是通过P G（andwrite（;'））（ ;））的一个乘积直 接 从 （ ;' ） 导 出 的 ， 当 且 仅 当 ） 和 扩 展（;'）。1更进一步，我们认为映射对（n;“n）是从数据图D上的映射对（0;”0）导出的，如果（0;“0））1 （1;'1））2 ）n （n;n）。 给定一个图文法PG和一个数据图D，（PG; D）定义了从（S;;）导出的映射对的集合，其中;表示空映射.应用于数据图D的映射对允许我们识别D的具有由语法定义的属性的子图。提取的子图的每个节点可以关联到查询图的多个节点，如果这些节点具有不同的“角色”标签。 不同的标签用于区分节点和弧的不同类别（例如，在树中，内部节点和叶节点可以具有不同的标签）。1 （'）。7GT-VMT 2001 {S.弗莱斯卡湾Furfaro和S.Greco例3.5考虑例2的解析语法、例2中所示的推导和下面的图的左侧所示的数据图。图片：分别在推导的第三步和最后一步产生的查询图可以映射到D上，如图3.5的注意，定义图的公理（开始符号）的产生式包含一个弧，其开始节点用常数标签n1标记。这意味着所有派生查询图都是根节点标记为n1的树。因此，由这种语法生成的每棵树只能映射到根节点具有标签n1的树。在上述映射中，当查询组中的所有其他节点都具有相同的值时，一个变量。虽然图中没有表示，但查询图中的弧被映射到数据图中的弧;例如弧e =（1; 2; a）和a rc'（e）具有相同的标签a（即， '（e）=（'（1）;'（2）;a））。2语法分析我们现在介绍一种新型的图语法，称为解析语法，专门用于从数据图中提取信息。分析文法具有以下特点：1）产生式规则集是线性有序的（以驱动推导过程并减少不确定性）; 2）只有在满足提取数据的特定条件时才能应用规则。定义3.6解析（图）语法是一个元组PG =（; ; P;S），其中：是一个终端符号的字母表，是一个节点非终端符号的字母表（\=;），S2是公理。P是X！（C），其中(i) X 2是一个非终结符，(ii) 是G（[）中的（general）graph，(iii) C是一组连接规则，即一组元组（; ; v; d）其中d 2fin; outg，2、2V是一个节点，(iv) 对于每个符号X 2，都有一个产品X！在P中，(v) 对于每对产品，i：X！（C）与非空且j：X！是ij2<解析语法生成查询图，而不允许边重新标记。产生式的序定义了映射对导子的序8PG1 1 121PG 2 2 2GT-VMT 2001 {S.弗莱斯卡湾Furfaro和S.Greco给定一个数据图D，一个语法分析程序PG，以及PG 的 两个产生式和，我们可以说，从一个对（;'）导出一个对（1;'1）的d1在从（;'）导出一个对（2;'2）的d2之前（写作d1d2），如果1）d=（;'））（;'））（;'），d=（;'））（;'））（;'），或1ii1 1 2jj2 22) 有三个导数d、d3和d4，使得d1= dd3，d2= dd4，d3 =d4。我们现在可以使用关系来定义导出映射对集合（PG; D）上的偏序。 给定两个映射对M1; M2 2（PG; D），我们称M< M为M，如果对于每个导子d =（S; ;））M，存在导子d =（S; ;））M使得d d .在PG的产生式上引入序使得（PG; D）是偏序的.映射对M2若不存在映射对M0 ，则称（PG;D）是极小的 2（PG;D），则M0

下载后可阅读完整内容，剩余1页未读，立即下载