利用相关数据库实现非循环定向图形结构的方法

摘要

一种利用计算机关系数据库系统来实施非循环定向图形结构的方法。表示非循环绘图块的一种有利的关系数据库结构可以通过创建三种表格结构来获得,这三种表格结构用于存储绘图块中各节点之间的相互关系及其它特性。节点表格存储绘图块中每个节点之间的相互关系和分配给各节点的特性。边表格存储定向链接的各节点及所链接的方向的指示。路径表格存储定向或非定向链接的各节点及其各路径的方向的指示。还公开了用于以一致方式维护数据库结构的方法。

说明书

                                 发明领域

本发明涉及利用相关数据库实现非循环定向图形结构(acyclic directedgraph structure)的方法。非循环绘图块(diagraph)结构频繁地用于模型化现实世界分层系统(model real world hierarchy system)。这种可使用非循环绘图块结构的分层系统举例来说有家庭树结构、面向对象的关系模型、网络路由结构等。

                                 发明背景

尽管非循环绘图块结构在真实世界中很流行，但极少有计算机应用程序实际采用这种模型。应用程序的开发者则是喜欢使用另一种类似模型即定向树结构(directed tree structure)来仿真非循环绘图块系统，或者另外产生非循环绘图块的“景象(views)”并用定向树结构来表示这种景象。

应用程序的编程者门之所以趋向于避免使非循环绘图块结构模型化的主要原因是由于这种结构的复杂性，以及实施和维护这种结构的复杂性。

一个图形是由节点(nodes)(或者点(points)或者顶点(vertices))及边(edges)(或者连线(links)或者弧线(arcs))组成的数学系统。下面是从由Jean-PaulTremblay和Paul G Sorenson所著的一本书中摘录的对于图形的数学定义(ISBN0-07-065157-4)：

“一个图形G由下列部分组成：称为该图形的节点(点、顶点)集合的一个非空集合V、作为该图形的边集合的一个集合E、以及从边的集合E到单元对集合V的一个映射。

我们可以假定一个图形的两个集合V和E都是有限集合。也可以方便地将一个图形写作G=(V、E)。请注意一个图形的定义隐含着这样的意思：对于图形G的每一条边，我们可以将该图形的一对节点与其关联。如果一条边x∈E是这样与一对节点(u,v)相关联的，其中u,v∈V，则我们可以说这条边x连接或者接合节点u和v。由一个图形中的一条边连接的任何两个节点都称为相邻节点。

在一个图形G=(V,E)中，从一个节点指向另一个节点的一条边称为一条定向边，而没有特定方向的一条边称为一条非定向边。其中每条边都被定向的图形称为定向图形或者绘图块”。

除了上述定义以外，这本书还给出了下面的附加定义：

“一个绘图块的各条边的任何顺序都定义了该图形的一条路径，其中这种顺序使得该顺序中的任何边的终节点都是该顺序中下一个要出现的边(如果有的话)的始节点。一条路径是指从所述顺序中第一条边的始节点开始，到所述顺序中最后一条边的终节点结束，从而穿过出现在该顺序中的各个节点。”

“以同一个节点开始和结束的一条路径称为一个循环(回路)。”

“没有任何循环的一个简单的绘图块称为非循环式的。”

从上面的定义中，一个非循环绘图块的特性可总结如下：

1．其结构仅由节点和边组成；

2．各条边是非定向的；

3．任何两个节点之间的定向关系由一条边的最大值来表示；

4．任何两个节点之间的非定向关系或路径可通过多个边与其它节点相存在；

5．每个节点可以有一个或多个子节点；

6．每个节点可以有一个或多个父节点；

7．任何给定的节点都可以存在祖先节点，该祖先节点由所有的后续父节点或者特定节点组成；

8．任何给定的节点都可以存在后代节点，该后代节点由所有的后续后代节点或者特定节点组成；

9．一个节点的祖先不能是该相同节点的后代；

10．任何给定的非循环绘图块结构都存在一个逆结构。任何给定的非循环绘图块结构与其逆结构是相同结构，只是所有边的方向相反。

在计算机中存储并操纵非循环绘图块结构的传统方法是采用第三代编程语言来完成的。这基本上涉及将定义的存储器存储区域用作节点，并将指针用作边。采用C代码的例子如下：

struct Node (

char    nodename[10]

struct Node *nextnode[4])

其中nodename表示实际节点，而nextnode表示到另一个节点的边。这种结构的运行可采用函数或程序来编程。这种函数的例子有“InsertNode(插入节点)”、“Delete Node(删除节点)”、“Attach Node(附加节点)”等。

尽管这种方法可有效地实施一个非循环绘图块，但还有几点关于这种实施的复杂性和可靠性的考虑：

1．与一个节点相关的各条边的最大数目必须事先知道；

2．很难找出各节点之间路径的存在，因为所有可能的路径都必须在得出结论之前穿过；

3．没有考虑到这种结构关于数据库协调性和整体性方面的可靠性；

4．没有可行的节点锁存机制，因而将这种结构的使用限制为一个用户或者在一个时间内操作；

5．当使用第三代语言时可能会遇到关于存储器分配或丢失指针方面的问题，这些问题可以导致整个程序崩溃。

尽管一个训练的编程者可能能够避开所有这些限制，但忙于避开每一个这些限制只会进一步增加所做编程的复杂性。此外，由于每件事情都是通过编程来完成的，更有可能在系统中隐藏缺陷(bugs)，因而系统维护会显得非常困难和耗时。

                                 本发明的概述

本发明提供了一种通过使用关系数据库来存储和操纵非循环定向图形结构的替代方法。

按照本发明，提供了一种利用计算机运行的关系数据库来产生非循环定向图形结构或者非循环绘图块的方法，该非循环绘图块包括相互定向连接的多个节点，这些节点的连接使得每一个节点在前向连接方向上具有至少一个子节点和/或在反向连接方向上具有至少一个父节点，所述方法包括：

产生一个节点表格结构，该节点表格结构表示非循环绘图块中每个节点之间的相互关系和至少一种节点特性；

产生一个边表格结构，该边表格结构表示非循环绘图块中每个定向连接的节点对之间的相互关系；和

产生一个路径表格结构，该路径表格结构表示非循环绘图块中任何两个节点之间路径的存在性。

本发明还提供了一种在关系数据库系统中的计算机存储数据结构，用于表示一非循环绘图块，该非循环绘图块包括相互定向连接的多个节点，这些节点的连接使得每一个节点在前向连接方向上具有至少一个子节点和/或在反向连接方向上具有至少一个父节点，所述数据结构包括：

一个节点表格结构，指示所述非循环绘图块中每个节点之间的相互关系和至少一种节点特性，所述节点表结构包括用于所述非循环绘图块中的每个节点的记录，每个节点表格结构记录包括一节点标识字段和至少一个节点特性字段；

一个边表格结构，指示所述非循环绘图块中每一对连接的父和子节点之间的相互关系，所述边表格结构包括用于每一对父和子连接节点的记录，每个边表格结构记录包括用以识别所述父节点和所述子节点的相应字段；和

一个路径表格结构，指示所述非循环绘图块中任何两个节点之间路径的存在性，所述路径表格结构包括用于每一对父和子连接节点和每一对其中两个节点通过中介连接的祖先和后代连接节点的记录，每个路径表格结构记录包括用以识别每一个节点对的相应字段。

一种维护如上所述的由本发明提供的数据结构的方法，包括：

一节点创建程序，用于通过使用所述节点识别字段中的一个唯一值将一条新记录插入到所述节点表格结构中而在所述非循环绘图块中创建一新节点；

一节点链接程序，用于将所述非循环绘图块中的一子节点链接到一父节点，包括下列步骤：

将一条新记录插入到所述边表格结构中，该记录用以识别所述子节点和所述父节点以及从所述父节点到所述子节点的连接方向；

将一条新记录插入到所述路径表格结构中，该记录用以识别所述子节点和所述父节点以及从所述父节点到所述子节点的连接方向；

从所述路径表格结构中选择连接到所述父节点的每一个祖先节点，并将一条新记录插入到所述路径表格结构中，该记录用以识别所述子节点和每一个祖先节点以及从所述祖先节点到所述子节点的连接方向；和

从所述路径表格结构中选择所述子节点所连接的每一个后代节点，并将一条新记录插入到所述路径表格结构中，该记录用以识别所述子节点和每一个后代节点以及从所述子节点到所述后代节点的连接方向；

一节点解链接程序，用于将所述非循环绘图块中的一子节点与一父节点解链接，包括下列步骤：

从所述边表格结构中去除用以识别所述子节点和所述父节点的记录；

从所述路径表格结构中去除用以识别所述子节点的每一个记录；

从所述路径表格结构中选择并去除用以识别所述父节点的一祖先节点和所述子节点的一后代节点的记录；和

从识别所述父节点的一祖先节点的记录开始，系统化地查看所述边表格结构，以确定从所述父节点的一祖先节点到所述子节点的一后代节点的任何路径，查看所述路径表格结构，以了解是否由一条路径表格结构记录识别出任何这种路径，并且，如果所述路径表格结构中不存在这种路径，则将一条识别所述路径的新记录插入到所述路径表格结构中；和

一去除节点程序，用于从所述非循环绘图块中去除已被解链接的一节点，包括从所述节点表格结构中去除识别所述被解链接的节点的记录。

                           附图的简要说明

下面将通过举例方式参照附图对本发明进行更详细的说明，附图中：

图1是非循环定向图形结构的典型图示；和

图2是另一种非循环绘图块结构的例子。

                                 优选实施例的详细描述

下面描述的是利用商用相关数据库实现非循环绘图块结构的方法。从如何存储、恢复、更新和维护结构中的各项目这些方面来描述各种操作。

使用商用数据库的优点如下：

1．能以负担得起的价格从市面上当时得到；

2．能加快应用程序开发时间；

3．利用了关系数据库的强度。这包括可靠性、入网工作能力、索引能力等；

4．关系数据库建立在集合原理和拓扑计算法这些数学概念的基础上。将这些概念应用于非循环绘图块结构的操作。

本发明的优选形式采用三种数据库表格。这些表格为：

1．节点表格

这种表格存储每个节点的特性。必须使用一个关键字段来唯一地识别每个节点。任何数目的附加字段也可以用于表示节点的附加特性。因此，这种表格中的每一条记录将表示非循环定向树结构中的一个节点。

2．边表格

这种表格存储任何两个节点之间的相互关系。它必须包括至少两个字段，一个是父字段(或始节点字段)，一个是子字段(或终节点字段)。因此，这种表格中的每一条记录将表示非循环定向图形结构中的一条边。

3．路径表格

这种表格列出任何两个节点之间的路径。这种表格必须包括至少两个字段，一个是祖先字段(路径的始节点)，一个是后代字段(路径的终节点)。因此，这种表格中的每一条记录将表示非循环定向图形结构中的一条路径。请注意，这种表格没有列出任何两个节点之间的路由，而是仅仅列出任何两个节点之间路径的存在性，所述路由必须通过详细研究(traverse)边表格来得出。这样就足够了，因为它会表示出两个节点之间的相互关系。

保持所有三个表格之间的整体性很重要。下面的规则可用于保证维护整体性：

1．父字段、子字段、祖先字段和后代字段中的每个值必须能够映射到所述节点表格中的一个关键字段记录；

2．在路径表格中表示的所有路径都必须能够通过利用所述边表格详细研究各节点而再现出来；

3．通过详细研究所述边表格中的各节点而可以追踪的所述结构中所有可能的路径都表示在所述路径表格中。

如果保持这三个规则，那么所述的三种表格就会表示一非循环定向图形结构。请注意，这种方法也允许多于一个的非循环绘图块结构在任何一个时间内存在于数据库中，还允许不同的结构合并在一起，或者分裂为两种不同的结构。还请注意，这种技术也允许人们不仅可以表示一非循环定向图形结构，还可以表示其逆结构。关系数据库中这种结构的例子由下面的表1、2和3来表示，并且在图1中以图表形式示出。

                              表1：节点表格

    节点    特性(色彩)    1    蓝色    2    绿色    3    蓝色    4    红色    5    褐色    6    绿色    7    红色    8    蓝色    9    紫色    10    褐色    11    绿色    12    蓝色    13    紫色    14    蓝色    15    红色

                              表2：边表格

    父    子    1    6    1    4    2    9    2    7    2    5    3    5    3    8    4    9    5    13    6    9    6    10    7    11    7    12    7    13    8    14    9    15    11    15

                                  表3：路径表格

    祖先    后代    1    4    1    6    1    9    1    10    1    15    2    5    2    7    2    9    2    11    2    12    2    13    2    15    3    5    3    8    3    13    3    14    4    9    4    15    5    13    6    9    6    10    7    11    7    12    7    13    8    14    9    15    11    15

为了有效地操纵非循环定向图形结构，需要定义几种操作。下面就是对各种操作以及如何实施这些操作的作为样品的Microsoft SQL服务器代码的描述。

创建节点

这种操作在结构中创建一个新的节点。结构中的一个新节点由节点表格中的一条新记录来表示。还必须产生新的关键值以唯一识别该新节点。也可以为新节点规定一个或多个附加特性。新节点一旦建立，则会与结构的其它部分独立存在。它必须链接到已经存在于结构中的一节点并成为该结构的一部分。

例子：

INSERT INTO node_table(node,property)

VALUES(16,Blue)；

去除节点

这种操作从结构中完全去除一个节点。请注意该节点在其被去除之前必须首先与所有其它节点解链接。

链接节点

这种操作将结构中的一节点(子节点)链接到另一节点(父节点)。通过链接这两个节点，还可在结构中形成新的路径。这种算法的一部分是要保证结构的整体性。这种算法为：

1．确定是否将由链接操作形成一循环路径。(这可以通过保证要链接的子节点不能已经是要链接的父节点的祖先节点而容易地做到)。如果将会形成循环路径，则程序终止，因为所得的结构将不会是非循环的。

2．将子节点链接到父节点。

3．确定是否有至少一条新路径已经存在于所述结构中。(如果至少一条新路径已经存在，则所有可能的新路径应当已经存在于所述结构中)。

4．如果路径已经存在则结束操作，否则便继续到下一步。

5．产生所有新路径的一列表，并将相应记录增加到所述路径表格中。这可以通过下列操作来完成：

ⅰ)将所述父节点的所有祖先作为所述子节点的后代的祖先而增加到所述路径表格中。

ⅱ)将所述父节点的所有祖先作为所述子节点的祖先而增加到所述路径表格中。

ⅲ)将所述子节点的所有后代作为所述父节点的后代而增加到所述路径表格中。

ⅳ)将所述父节点和子节点分别作为祖先和后代增加到所述路径表格中。

链接操作的例子：

CREAT PROCEDURE Link@parent_node,@child_nodeASDECLARE@ancestor intDECLARE@testcount intDECLAREnodeancestorINSENSITIVE CURSORFORSELECT DISTINCT ancestor FROM path_table WHERE descendant=@parent_node								BEGINSELECT @testcount=COUNT(ancestor)FROM path_tableWHEREdescendant=@parent_nodeANDancestor=@child_nodeIF @testcount＞0BEGIN RAISERROR(‘Illegal Link,Cyclic path not allowed’,16,-l) RETURNENDINSERT INTO edge_table(parent,child)VALUES@parent_node,@child_nodeSELECT@testcount=COUNT(ancestor)FROMpath_tableWHERE ancestor=@parent_nodeAND descendant=@child_nodeIF @testcount＞0BEGINRETURN/*Path already exist in structure*/ENDOPENnodeancestorFETCH nodeancestor INTO@ancestorWHILE @@fetch_status=0BEGIN								 INSET INTOpath_table(ancestor,descendant) SELECT@ancestor,descendant FROMpath_table WHERE ancestor=@child_node AND descendant NOT IN (SELECT descendantFROMpath_tableWHEREancestor=@ancestor) INSERT INTO path_table(ancestor,descendant) SELECT DISTINCT parent,@child_node FROMedge_table WHEREparent=@ancestor AND child_node NOT IN (SELECT descendantFROM path_tableWHEREancestor=@ancestor) FETCH nodeancestor INTO @ancestorEND INSERT INTO path_table(ancestor,descendant) SELECT@parent_node,descendant FROMpath_table WHEREancestor=@child_node ANDdescendant NOT IN(SELECT descendant FROM path_table WHEREancestor=@parent_node ) INSERT INTO path_table(ancestor,descendant) SELECT DISTINCT parent,@child_node								 FROMedge_table WHEREparent=@parent_node AND @child_node NOT IN (SELECT descendantFROM path_tableWHEREancestor=@parent_node )END

对节点解链接

这种操作将结构中的一节点(子节点)与另一节点(父节点)解链接。通过对任意两个节点解链接，路径表格需要被更新以反映某些路径不再有效。用于解链接操作的算法可表达为：

1．从边表格中去除所述父节点和子节点之间的链接。将该子节点链接到父节点。

2．从路径表格中去除所述父节点的各祖先和所述子节点的各后代之间的所有链接。

3．从路径表格中去除所述父节点和子节点之间的链接。

4．在路径表格之后增加可通过可替代路径存在于所述父节点的各祖先和所述子节点的各后代之间的所有链接。

5．在路径表格之后增加经由可替代路由的所述父节点和所述子节点之间的链接(如果这种路径的确存在的话)。

解链接操作的例子：

CREAT PROCEDURE unlink @parent_node@child_nodeASDECLARE @ancestor intDECLARE @testcount intDECLARE nodeancestor SCROLL CURSORFOR SELECT DISTINCT path_table1.ancestorFROMpath_table as path_tablelINNER JOIN path_table as path_table2ON path_table1.ancestor=path_table2.ancestor								 WHERE path_table1.descendant=@child_node AND (path_table2.descendant=@parent_node OR path_table1.ancestor=@parent_node)BEGINSELECT FROM edge_tableWHERE parent=@parent_nodeAND child=@child_nodeOPENnodeancestorFETCH FIRST nodeancestor INTO @ancestorWHILE@@fetch_status=0BEGIN DELETE FROMpath_table WHEREancestor=@ancestor AND(descendant IN(SELECTdescendant FROMpath_table WHEREancestor=@child_node) OR descendant=@class_node) FETCH NEXTnodeancestorINTO@ancestorENDFETCH FIRST nodeancestor INTO@ancestorWHILE@@fetch_status=0BEGIN INSERT INTO path_table(ancestor,descendant) SELECT@ancestor,child FROM edge_table INNER JOINpath_table ON parent=descendant WHERE ancestor=@ancestor								 ANDchild NOT IN (SELECT descendantFROM path_tableWHEREancestor=@ancestor) INSERT INTO path_table(ancestor,descendant) SELECT@ancestor,child FROMedge_table WHERE parent=@ancestor ANDchild NOT IN (SELECT descendantFROM path_tableWHEREancestor=@ancestor) FETCH NEXT FROM nodeancestor INTO@ancestorENDEND

这种技术如何应用的一个例子是分类系统(Classification System)。一个商业目录可能会有数百个产品和服务类别。这些类别可以组织到定向图形结构中。一种样品分类结构的一部分示例示于图2中。

利用所描述的表示这种分类系统的技术，可列出下列表格：

                              表4：节点表格

    节点    分类    1    流量控制设备    2    阀门    3    泵    4    废物处理设备    5    空气泵    6    酸剂泵    7    污水泵    8    污水过滤器

                           表5：边表格

    父    子    1    2    1    3    3    5    3    6    3    7    4    7    4    8

                                表6：路径表格

    祖先    后代    1    2    1    3    1    5    1    6    1    7    3    5    3    6    3    7    4    7    4    8

因此就有可能将公司(company)与任何给定的类别相联系，为此，确保所有的祖先类别也可以“固有(inherit)”这种相互关系。例如，假定想要通过将一条记录插入到一个被特殊建立以表示这种相互关系的一表格中，而将公司“Caterpillar Pumps Ltd(凯特比勒泵有限公司)”与“空气泵”联系起来。下面的表格就是结果：

                     公司分类表

    分类节点    公司    5    凯特比勒泵有限公司

然后，该路径表格可用于将同样的关系反映到祖先类别。用SQL语句实现的样例为：

INSERT INTO company_classification_tableSELECTancestor,“Caterpillar Pumps Ltd”FROMpath_tableWHERE descendant=5

于是，所得表格为：

    分类节点    公司    1    凯特比勒泵有限公司    3    凯特比勒泵有限公司    5    凯特比勒泵有限公司

如果还有公司想加入到该系统，比如说将“Calpeda Valves Ltd(凯尔比达阀门有限公司)”加到类别“阀门”，并且将“Green Treatment Ltd(格林处理有限公司)”加到类别“污水泵”，则所得表格为：

    分类节点    公司    1    凯特比勒泵有限公司    3    凯特比勒泵有限公司    5    凯特比勒泵有限公司    1    凯尔比达阀门有限公司    2    凯尔比达阀门有限公司    1    格林处理有限公司    3    格林处理有限公司    4    格林处理有限公司    7    格林处理有限公司同样的表格，但通过分类而存储之后，将成为    分类节点    公司    1    凯特比勒泵有限公司    1    凯尔比达阀门有限公司    1    格林处理有限公司    2    凯尔比达阀门有限公司    3    凯特比勒泵有限公司    3    格林处理有限公司    4    格林处理有限公司    5    凯特比勒泵有限公司    7    格林处理有限公司

因此，能够快速维护正确的“遗传(inheritance)”结构，而不需要找出根节点，也不需要详细研究任何路径。

上面对本发明优选实施例的详细描述已经通过举例形式表示出，但并不打算将由所附权利要求书限定的本发明限制为上述说明。