CN105095237B

CN105095237B - 用于生成非关系数据库的模式的方法和设备

Info

Publication number: CN105095237B
Application number: CN201410181384.1A
Authority: CN
Inventors: 王岚君; 张硕; 焦丽梅; 王晨
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 2014-04-30
Filing date: 2014-04-30
Publication date: 2018-07-17
Anticipated expiration: 2034-04-30
Also published as: US20180260420A1; US10055429B2; CN105095237A; US10936556B2; US20150317335A1

Abstract

本发明的实施例公开了用于生成非关系数据库的模式的方法和设备。在本发明的实施例中，可以确定非关系数据库的至少一个条目中的记录模式，所述记录模式是该条目中以键为节点的各键层级之间的树状关系，其中键对应于属性名称；对于至少一个记录模式，基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新该记录模式；基于更新后的记录模式生成所述非关系数据库的模式。

Description

用于生成非关系数据库的模式的方法和设备

技术领域

本发明的实施例涉及数据库领域，更具体地，涉及一种用于生成非关系数据库的模式的方法和设备。

背景技术

如本领域所已知，数据库在现代信息技术中发挥着重要作用。例如，作为数据库的重要类型之一，关系数据库系统被广泛地应用于存储和检索各类信息。然而，在当今不断发展的信息技术中，存在着对数据库高并发读写的需求、对海量数据的高效率存储和访问的需求以及对数据库的高可扩展性和高可用性的需求，对此，关系数据库已经显得力不从心并存在很多难以克服的问题。例如，在应付Web2.0网站，特别是超大规模和高并发的SNS类型的Web2.0纯动态网站方面，关系数据库越来越不适于应用。

针对这一问题，业界提出了非关系数据库(NoSQL)。非关系数据库具有自组织、自管理、低成本、高可扩展性、高并发性、查询关系简单等特点。具体而言，关系数据库中的表通常存储格式化的数据结构，每个条目字段的组成相同，即使不是每个条目都需要所有的字段，关系数据库也会为每个条目分配所有的字段，这样的结构是关系型数据库性能瓶颈的一个因素。不同的是，非关系数据库以键值对存储，它的结构不固定，每一个条目可以有不一样的字段，每个条目可以根据需要增加一些自己的键值对，这样就不会局限于固定的结构，可以减少一些时间和空间的开销。

目前，由于非关系数据库没有类似于关系数据库那样的模式(Schema)，所以无法根据Schema来对关系数据库和非关系数据库进行数据匹配、数据整合、数据交换等方面的处理，从而难以实现对关系数据库和非关系数据库二者的整合，因此，生成非关系数据库的模式是非常必要的。特别的是，由于NoSQL无需事先为要存储的数据建立字段，随时可以存储自定义的数据格式，在网站架构变化、程序员变化、程序员修正等情形下，新插入的数据的属性名称可以随时更改，使得生成非关系型数据库的模式具有一定的难度。

发明内容

鉴于现有技术中存在的上述问题，本领域中需要一种能够获取非关系数据库中的模式的解决方案。为此，本发明的实施例提供了一种用于生成非关系数据库的模式的方法和设备。

根据本发明的一个方面，提供了一种用于生成非关系数据库的模式的方法。该方法可以包括：确定非关系数据库的至少一个条目中的记录模式，所述记录模式是该条目中以键为节点的各键层级之间的树状关系，其中键对应于属性名称；基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式；基于更新后的记录模式生成所述非关系数据库的模式。

根据本发明的另一个方面，提供了一种用于生成非关系数据库的模式的设备。该设备可以包括：确定器，配置用于确定非关系数据库的至少一个条目中的记录模式，所述记录模式是该条目中以键为节点的各键层级之间的树状关系，其中键对应于属性名称；属性名称变化确定器，配置用于基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式；生成器，配置用于基于更新后的记录模式生成所述非关系数据库的模式。

通过下文描述将会理解，利用本发明的实施例，可以便捷地生成NoSQL的Schema。

附图说明

通过结合附图对本公开示例性实施方式进行更详细的描述，本公开的上述以及其它目的、特征和优势将变得更加明显，其中，在本公开示例性实施方式中，相同的参考标号通常代表相同部件。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12的框图；

图2示出了根据本发明一个示例性实施例的用于生成非关系数据库的模式的方法200的示意性流程图；

图3示出了根据本发明一个示例性实施例的确定非关系数据库的至少一个条目中的记录模式的方法300的示意性流程图；

图4A-图4I示出了根据本发明一个示例性实施例的用于生成非关系数据库的模式的方法400的示意性流程图；

图5A-图5I示出了根据本发明一个示例性实施例的用于生成非关系数据库的模式的设备500的示意性框图；

图6示出了根据本发明的实施例的非关系数据库600中部分内容的示意图；

图7示出了表示根据本发明的实施例的树状关系700的示意图；

图8示出了根据本发明的实施例的用于生成非关系数据库的模式的设备800的示意图。

具体实施方式

下面将参照附图更详细地描述本公开的优选实施方式。虽然附图中显示了本公开的优选实施方式，然而应该理解，可以以各种形式实现本公开而不应被这里阐述的实施方式所限制。相反，提供这些实施方式是为了使本公开更加透彻和完整，并且能够将本公开的范围完整地传达给本领域的技术人员。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12的框图。图1显示的计算机系统/服务器12仅仅是一个示例，不应对本发明实施例的功能和使用范围带来任何限制。

如图1所示，计算机系统/服务器12以通用计算设备的形式表现。计算机系统/服务器12的组件可以包括但不限于：一个或者多个处理器或者处理单元16，系统存储器28，连接不同系统组件(包括系统存储器28和处理单元16)的总线18。

总线18表示几类总线结构中的一种或多种，包括存储器总线或者存储器控制器，外围总线，图形加速端口，处理器或者使用多种总线结构中的任意总线结构的局域总线。举例来说，这些体系结构包括但不限于工业标准体系结构(ISA)总线，微通道体系结构(MAC)总线，增强型ISA总线、视频电子标准协会(VESA)局域总线以及外围组件互连(PCI)总线。

计算机系统/服务器12典型地包括多种计算机系统可读介质。这些介质可以是任何能够被计算机系统/服务器12访问的可用介质，包括易失性和非易失性介质，可移动的和不可移动的介质。

系统存储器28可以包括易失性存储器形式的计算机系统可读介质，例如随机存取存储器(RAM)30和/或高速缓存存储器32。计算机系统/服务器12可以进一步包括其它可移动/不可移动的、易失性/非易失性计算机系统存储介质。仅作为举例，存储系统34可以用于读写不可移动的、非易失性磁介质(图1未显示，通常称为“硬盘驱动器”)。尽管图1中未示出，可以提供用于对可移动非易失性磁盘(例如“软盘”)读写的磁盘驱动器，以及对可移动非易失性光盘(例如CD-ROM,DVD-ROM或者其它光介质)读写的光盘驱动器。在这些情况下，每个驱动器可以通过一个或者多个数据介质接口与总线18相连。存储器28可以包括至少一个程序产品，该程序产品具有一组(例如至少一个)程序模块，这些程序模块被配置以执行本发明各实施例的功能。

具有一组(至少一个)程序模块42的程序/实用工具40，可以存储在例如存储器28中，这样的程序模块42包括——但不限于——操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。程序模块42通常执行本发明所描述的实施例中的功能和/或方法。

计算机系统/服务器12也可以与一个或多个外部设备14(例如键盘、指向设备、显示器24等)通信，还可与一个或者多个使得用户能与该计算机系统/服务器12交互的设备通信，和/或与使得该计算机系统/服务器12能与一个或多个其它计算设备进行通信的任何设备(例如网卡，调制解调器等等)通信。这种通信可以通过输入/输出(I/O)接口22进行。并且，计算机系统/服务器12还可以通过网络适配器20与一个或者多个网络(例如局域网(LAN)，广域网(WAN)和/或公共网络，例如因特网)通信。如图所示，网络适配器20通过总线18与计算机系统/服务器12的其它模块通信。应当明白，尽管图中未示出，可以结合计算机系统/服务器12使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RAID系统、磁带驱动器以及数据备份存储系统等。

在本发明的实施例中，“条目”可以是非关系数据库中的一个记录，也可以认为是非关系数据库中一个数据对象实例。一个条目可以拥有唯一的标识符(ID)，并可以包含零个或多个键/值(Key/Value)对。根据本发明的实施例，各个键/值对之间可以通过预先定义的区分符来进行区分，例如，可以通过逗号等来将不同的键/值对进行区分；同时，每个键/值对内的“键”和“值”可以通过预先定义的分隔符进行分隔，例如通过冒号来进行分隔，因此可以根据分隔符来从一个键/值对中确定其中的键。同时，可以通过预先定义的扩展符来扩展键/值对中的“值”，例如可以利用中括号来表示一个键/值对中的“值”包含两个以上的属性。所述两个以上的属性中的每个属性既可以是一个真正的“值”，也可以是一个键/值对，并且该键/值对中的“值”还可以继续包含一个或多个属性。

图6示出了根据本发明的实施例的非关系数据库600中部分内容的示意图。如图6所示，所示例的非关系数据库600可以包含多条记录，每一条记录表示一个条目。非关系数据库600本身可以具有一个标识符，以对自己进行表征并将自己与其他非关系数据库区分。例如，非关系数据库600的标识符可以是“Blog”。根据本发明的实施例，可以将非关系数据库的标识符也认为是一个键。所以，在构建各个键的层级信息时，可以将其作为层级信息的中的一个键进行考虑。现在回到图6，在与第一条记录对应的条目中，“author:‘don’”是一个键/值对，其中键是“author”，值为“don”。另外，该条目中的“comments:[{author:‘mary’,comment:‘I disagree’},{author:‘alice’,comment:‘good post’}]”也是一个键/值对，其中键是“comments”，值为“[{author:‘mary’,comment:‘I disagree’},{author:‘alice’,comment:‘good post’}]”，可见该值中还可以嵌套一个或多个键/值对。根据区分符、分隔符、扩展符等可以确定各个键之间的层级信息，从而确定各个键之间的关联关系，进而，可以确定出每个条目中键之间的树状关系。

图2示出了根据本发明一个示例性实施例的用于生成非关系数据库的模式的方法200的示意性流程图。

在步骤S201，确定非关系数据库的至少一个条目中的记录模式，所述记录模式是该条目中以键为节点的各键层级之间的树状关系，其中键对应于属性名称。

如何从记录条目中解析出键之间的树状关系是现有技术。具体的，在根据本发明的一个实施例中，可以提取非关系数据库中一个条目中所包含的键，确定所提取的键在每个条目中的层级信息，以及根据该层级信息确定键之间的关联关系，进而确定出键之间的树状关系。

接下来，以图3为例对如何确定条目中键之间的树状关系进行详细的说明。图3示出了根据本发明一个示例性实施例的用于生成非关系数据库中数据条目的树状关系的方法300的示意性流程图。

在步骤S301，提取非关系数据库中每个条目中包含的键。

根据本发明的实施例，可以先确定出每个条目中包含哪些键/值对，然后从所确定的键/值对中来提取其中的键，从而完成对这个条目集合中的中的每个条目中的键的提取过程。

在图6所示的示例性非关系数据库中，通过逗号对不同的键/值对进行了区分，并通过冒号对每个键/值对内的“键”和“值”进行了分隔。由此，可以从该非关系数据库的第1个条目中提取其所包含的以下键：author,created,Title,Text,tags,comments,comment。类似地，可以分别提取该非关系数据库中的第2,3,……,N个条目中包含的键。

在步骤S302，确定提取的键在每个条目中的层级信息。

根据本发明的实施例，可以根据预先定义的各种符号(区分符、分隔符、扩展符等等)确定各个键之间的层级关系。在图6所示的示例性非关系数据库中，将逗号示例性地用作了区分符；将冒号示例性地用作了分隔符；将中括号示例性地用作了扩展符。因此，可以根据这些符号的出现来确定一个条目中的各个键的层级信息。

在步骤S303，根据层级信息确定键之间的树状关系。

在图7所示的层级信息的示意图中，以树形结构示出了从步骤S301提取的键，例如author,created,Title,Text,tags,comments,comment等键，之间的层级信息。假设Blog为根节点，author,created,Title,Text,tags,comments这些键分别是根节点的一级子节点；其中，一级子节点comments还具有两个子节点，也即author和comment这两个键，它们同时分别是根节点的二级子节点。

根据本发明的实施例，一级子节点是直接与根节点具有关联关系的子节点，二级子节点是直接与一级子节点具有关联关系的子节点，据此类推，N级子节点是直接与N-1级子节点具有关联关系的子节点。例如，在第一个条目中，author,created,Title,Text,tags,comments这些键都直接与非关系数据库具有关联关系，因此分别都是一级子节点；由于与comments这个键对应的值包含{author:‘mary’,comment:‘I disagree’}和{author:‘alice’,comment:‘good post’}，所以这个值中包含的author和comment这两个键分别与comments这个键直接具有关联关系，而与根节点没有直接的关联关系，因此author和comment这两个键是二级子节点。

由上可见，可以根据步骤S302得到的层级信息来确定各个子节点之间的关联关系，从而可以相应地确定各个键之间的树状关系。

接下来，返回图2中的步骤S202，在步骤S202中，基于子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式。

在一个实施例中，是基于编码后的树形结构记录模式确定存在名称变化的节点。具体的，该实施例包括以下各步骤：对所述每个条目的记录模式进行CinP编码，所述CinP编码是对记录模式中每个节点进行编码时既包括该节点自身编码也包括其子节点的编码；所述基于子节点的相似度确定存在属性名称变化的节点是基于编码后的记录模式中子节点的相似度确定存在属性名称变化的节点。

在一个实施例中，可采用素数编码对每个条目进行CinP编码。在另一个实施例中，还可采用自然数-字符串编码对每个条目进行CinP编码。申请人将在图4、图5所示的实施例中对这两个实施例进行更为详细的介绍。

图4示出了根据本发明一个示例性实施例的基于素数编码的记录模式生成非关系数据库的模式的过程示意图。

步骤401，对所述每个条目的记录模式进行CinP编码，所述CinP编码是对记录模式中每个节点进行编码时既包括该节点自身编码也包括其子节点的编码。通过该步骤，可对每条记录(record)的记录模式(schema of record)建立层次化的CinP编码。

在一个实施例中，是从树型结构的最底层节点开始向根节点进行编码。每层维护一张编码表(code map)，用于表示属性名与编码的对应关系，图4C、图4D分别示出了基于素数编码的编码表，其中，图4C是对应于最底层的编码表，而图4D是对应于倒数第二层的编码表。每个节点的编码包括两部分：表示节点自身编码的自编码部分(P-code)，以及表示该节点子节点编码的子节点编码部分(C-code)，该两部分均是素数。在一个实施例中，C-code为节点所有子节点P-code的乘积，图4A、图4B分别示出了记录模式1、以及记录模式2进行素数编码后的结果，例如其中记录模式1中的B节点的编码为7，35，其中7为节点B的自编码，35为节点B的子编码，是节点B子节点E和F的自编码的乘积。

在步骤402中，将编码后的树形结构记录模式解析成路径集合，所述路径包括叶子节点到根节点所经过的所有节点的编码。图4E，图4F分别示出了上述两个记录模式的路径集合。例如，在记录模式2中的一条路径为D,A,O，用CinP编码表示为3,0,3,115,0,15。在该编码中，奇数位为P-Code，偶数位为C-Code，最后两个编码代表根节点的P-Code和C-Code。由于叶子节点无子节点，所以叶子节点的C-Code为0；同时，由于根节点为虚拟节点，P-Code为0。

步骤403，统计所有条目的路径集合中各条路径的频率。图4G示出的是路径频率统计的结果，其中记录模式1出现过1次，记录模式2出现过2次，在图4G中，()内的数字表示该路径频率。

接下来，从底层节点开始执行步骤404-406，迭代执行到根节点：

步骤404：将路径按该层P-Code分桶，相同的P-Code被分到相同的桶中。在上述路径集合中，以最底层为例，所有路径按照P-Code分别为3，5，7，以及无最底层节点被分到4个桶中，即：

Bucket1：3,0,3,115,0,15(2)

Bucket2：5,0,3,115,0,15(2)

5,0,7,35,0,35(1)

Bucket3：7,0,3,115,0,15(2)

7,0,7,35,0,35(1)

Bucket4：5,0,0,15(2)

5,0,0,35(1)

步骤405：在各桶中，判断是否出现属性名称变化的步骤包括：

1)检查在一个桶内是否有多余一条路径；

2)如果是，检查他们的父节点的P-Code是否不同；

3)如果不同，利用他们父节点的C-Code并且根据公式(1)计算父节点的相似度：

其中，N1，N2代表两个父节点，CN1表示N1的子节点集合，N2表示N2的子节点集合，|.|表示集合中元素个数。该相似度定义为两个父节点所包含的共同子节点的个数与总子节点个数的比例。即，当两个父节点包含子节点全部相同的时，该相似度为1；当两个父节点的所有子节点都不同的时候，该相似度为0，在上述例子中，对于节点A和B，他们含有2个共同子节点(E,F)，总子节点个数为3(D,E,F),相似度为2/3。

在上述利用素数编码时，两个父节点的共同子节点的个数为两个父节点C-code的最大公约数所包含的素数个数；两个父节点的总子节点个数为两个父节点C-code的最小公倍数所包含的素数的个数，由此可见，通过素数编码可以明显提高相似度确定时的效率。在本例中，父节点P-Code为3所对应的C-Code为115,父节点P-Code为7所对应的C-Code为35.115和35的最大公约数为35,可分解为2个素数；115和35的最小公倍数为115，可分解为3个素数。

4)如果相似度大于某一门限值G1，则认为两个父节点发生了属性名称的变化。

5)按照一定规则生成编码映射对：源P-Code–>目标P-Code，按照相应层的编码表，该编码映射对可以解析为映射对：源属性名称->目标属性名称。在后续的处理中，要将源属性名称替换为目标属性名称。比如，当规则为保留出现频率高的属性名称时，源属性名称为出现频率较低的属性名称，目标属性名称为出现频率较高的属性名称。在这个例子中由于记录模式2在数据中出现了2次，比记录模式1多，所以编码映射对为:7->3,源属性名称为B，目标属性名称为A。这里的规则还可以设置为保留最新出现的属性名称，或者保留具有语义的属性名称等。

步骤406：按照编码映射对，将父节点层源P-Code更新为目标P-Code，更新该节点相应父节点的C-Code编码。在本例中,除了将父节点层所有P-Code为7改为3,还需要将该节点的父节点的C-Code由35(7*5)改为15(3*5)。图4H示出的是更新后的路径集合。

步骤407：在路径编码中，提取只包含P-Code的子序列，并统计该子序列出现的频率(即合并相同的P-Code子序列)，比如，频率为2的路径5,0,3,115,0,15的P-Code子序列为5，3，0；频率为1的路径5,0,3,35,0,15的P-Code子序列为5，3，0，两者相同，合并后，P-Code子序列5，3，0，的频率为3。

步骤408：保留频率超过门限G2的P-Code子序列，并将其按照各层的编码表进行解码生成表的模式(schema)。在本例中，设G2＝100％，则得到图4I所示的模式。

图5示出了根据本发明一个示例性实施例的基于自然数-字符串编码的记录模式生成非关系数据库的模式的过程示意图。

步骤501，对所述每个条目的记录模式进行CinP编码，所述CinP编码是对记录模式中每个节点进行编码时既包括该节点自身编码也包括其子节点的编码。通过该步骤，可对每条记录(record)的记录模式(schema of record)建立层次化的CinP编码。

在一个实施例中，是从树型结构的最底层节点开始向根节点进行编码。每层维护一张编码表(code map)，用于表示属性名与编码的对应关系，图5C、图5D分别示出了基于自然数编码的编码表，其中，图5C是对应于最底层的编码表，而图5D是对应于倒数第二层的编码表。每个节点的编码包括两部分：表示节点自身编码的自编码部分(P-code)，以及表示该节点子节点编码的子节点编码部分(C-code)。在该利用自然数-字符串进行编码的实施例中，例如，记录模式1中的B节点的编码为3，2|3，其中3为节点B自编码，2|3为节点B子编码，是节点B子节点E和F的自编码的以及全局定义分隔符“|”的组合。。

在步骤502中，将编码后的树形结构记录模式解析成路径集合，所述路径包括叶子节点到根节点所经过的所有节点的编码。图5E，图5F分别示出了上述两个记录模式的路径集合。例如，在记录模式2中的一条路径为D,A,O，用CinP编码表示为1,0,1,1|2|3,0,1|2。在该编码中，奇数位为P-Code，偶数位为C-Code，最后两个编码代表根节点的P-Code和C-Code。由于叶子节点无子节点，所以叶子节点的C-Code为0；同时，由于根节点为虚拟节点，P-Code为0。

步骤503，统计所有条目的路径集合中各条路径的频率。图5G示出的是路径频率统计的结果，其中记录模式1出现过1次，记录模式2出现过2次，在图4G中，()内的数字表示该路径频率。

接下来，从底层节点开始执行步骤504-506，迭代执行到根节点：

步骤504：将路径按该层P-Code分桶，相同的P-Code被分到相同的桶中。在上述路径集合中，以最底层为例，所有路径按照P-Code分别为1，2，3，以及没有最底层节点被分到4个桶中，即：

Bucket1：1,0,1,1|2|3,0,1|2(2)

Bucket2：2,0,1,1|2|3,0,1|2(2)

2,0,3,2|3,0,2|3(1)

Bucket3：3,0,1,1|2|3,0,1|2(2)

3,0,3,2|3,0,2|3(1)

Bucket4：2,0,0,1|2(2)

2,0,0,2|3(1)

步骤505：在各桶中，判断持否出现属性名称变化的步骤包括：

1)检查在一个桶内是否有多余一条路径。在本实施例中，桶2有超过一条路径。

2)如果是，检查他们的父节点的P-Code是否不同。在本实施例中，桶2所对应的相同节点的父节点的P-Code不同，分别为1和3。3)如果不同，利用他们父节点的C-Code并且根据公式(1)计算父节点的相似度：

在上述利用自然数-字符串编码时，一个节点的所有子节点可由其的C-code结合分割符“|”解析而得。比如，本例中父节点P-code为1所对应的C-code为1|2|3，解析可得其包含P-Code分别为1，2，3的三个子节点；同理，P-code为3所对应的C-code为2|3，解析可得其包含P-Code为2，3的两个子节点。

5)按照一定规则生成编码映射对：源P-Code–>目标P-Code，按照相应层的编码表，该编码映射对可以解析为映射对：属性名称->目标属性名称。在后续的处理中，要将源属性名称替换为目标属性名称。比如，当规则为保留出现频率高的属性名称时，源属性名称为出现频率较低的属性名称，目标属性名称为出现频率较高的属性名称。在这个例子中由于记录模式2在数据中出现了2次，比记录模式1多，所以编码映射对为:7->3,源属性名称为B，目标属性名称为A。这里的规则还可以设置为保留最新出现的属性名称，或者保留具有语义的属性名称等。

步骤506：按照编码映射对，将父节点层源P-Code更新为目标P-Code，更新该节点相应父节点的C-Code编码。在本例中,除了将父节点层所有P-Code为3改为1,还需要将该节点的父节点的C-Code由2|3改为2|1。图5H示出的是更新后的路径集合。

步骤507：在路径编码中，提取只包含P-Code的子序列，并统计该子序列出现的频率(即合并相同的P-Code子序列)，比如，频率为2的路径2,0,0,1|2的P-Code子序列为2,0；频率为1的路径2,0,0,2|3的P-Code子序列为2，0，两者相同，合并后，P-Code子序列2，0，的频率为3。

步骤508：保留频率超过门限G2的P-Code子序列，并将其按照各层的编码表进行解码生成表的模式(schema)。在本例中，设G2＝100％，则得到图5I所示的模式。

接下来，继续说明图2中步骤S202的其它实施例。在一个的实施例中，基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式包括：将编码后的树形结构记录模式解析成路径集合，所述路径包括叶子节点到根节点所经过的所有节点的编码；(A)根据某一层的P-Code分桶；(B)在各桶中，根据子节点的相似度判断确定存在属性名称变化的父节点；(C)将部分所确定的存在属性名称变化的父节点层源P-Code更新为目标P-Code，更新该节点相应父节点的C-Code编码。

在一个更为具体的实施例中，还包括按照一定规则将部分所确定的存在属性名称变化的父节点源P-Code更新为目标P-Code，其中，源P-Code对应于源属性名称，目标P-Code对应于目标属性名称。该规则例如可以是保留出现频率高的属性名称，源属性名称为出现频率较低的属性名称，目标属性名称为出现频率较高的属性名称，在图4所示的实施例中还涉及了其它规则。

在另一个更为具体实施例中，并不仅仅是在某一层执行步骤A-C，而是从树状结构的底层节点开始执行步骤A-C，并迭代直至根节点。

接下来，继续说明图2中的步骤S203，在步骤S203中，基于更新后的记录模式生成所述非关系数据库的模式。

根据本发明的实施例，非关系数据库的模式可以根据多种方式生成。在根据本发明的一个实施例中，可以获取至少一个路径中的有效路径及其权重，然后可以基于有效路径及其权重来生成非关系数据库的模式。

在根据本发明的一个实施例中，可以通过多种实施方式来从至少一个路径中获取有效路径及其权重。例如，可以在至少一个路径中确定重复的路径；将重复的路径设定为一个有效路径，并将这样得到的有效路径的权重设定为该重复的路径的重复次数；同时，可以将不重复的路径分别设定为一个有效路径，并将如此设定有效路径的权重设定为一个预设权重。根据本发明的实施例，该预设权重例如可以为1。

在根据本发明的一个实施例中，还可以将路径的权重小于预定权重阈值的有效路径过滤掉，从而仅使用权重较大的有效路径来生成非关系数据库的模式。例如，可以将每个有效路径的权重与预定权重阈值进行比较，根据比较结果从有效路径中选择一个或多个目标路径，然后基于所选择的目标路径来生成非关系数据库的模式。通过这种实施方式，可以过滤掉一些出现频率较低的键，从而避免了为非关系数据库生成的模式的规模过于庞大。

在根据本发明的一些实施例中，可以根据键的层级信息确定一条或多条路径，将具备关联关系的键划分到同一条路径中。例如，在图7中，每条路径可以包括若干级子节点，每条路径从根节点开始、到末端叶节点也即最后一级子节点结束，并且每条路径不能完全相同。在图7所示的示意图中，Blog和created构成一条路径Blog－>created；Blog、Comments和author构成一条路径Blog－>Comments－>author；Blog、Comments和comment构成一条路径Blog－>Comments－>comment；等等，其他不再赘述。

当采用本申请实施例中所进一步公开的CinP编码对具有树状关系的记录模式进行编码时，则各路径是根据所包括的节点的CinP编码来确定。

图8示出了根据本发明一个示例性实施例的用于生成非关系数据库的模式的设备800的示意性框图。

根据本发明的实施例，设备800可以包括：确定器810，配置用于确定非关系数据库的至少一个条目中的记录模式，所述记录模式是该条目中以键为节点的各键层级之间的树状关系，其中键对应于属性名称；更新器820，配置用于基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式；生成器830，配置用于基于更新后的记录模式生成所述非关系数据库的模式。

在一个实施例中，图8所述的设备，还包括：配置为对所述每个条目的记录模式进行CinP编码的模块，其中，每个节点的CinP编码包括该节点自身编码P-Code以及其子节点的编码C-Code；所述属性名称变化确定器是基于CinP编码后的记录模式中子节点的相似度确定存在属性名称变化的节点。

在一个实施例中，所述属性名称变化确定器820包括：配置为将编码后的树形结构记录模式解析成路径集合的模块，所述路径包括叶子节点到根节点所经过的所有节点的编码；配置为根据某一层的P-Code分桶的模块；配置为在各桶中，根据该层子节点的相似度判断确定存在属性名称变化的父节点的模块；配置为将父节点源P-Code更新为目标P-Code，更新该更新后的父节点相应父节点的C-Code编码的模块。

在一个实施例中，所述配置为在各桶中，根据该层子节点的相似度判断确定存在属性名称变化的父节点的模块包括：配置为对于存在多条路径的桶，确定出父节点的P-Code不同的节点的模块；配置为通过父节点的C-Code以及公式计算父节点的相似度的模块，其中，N1，N2代表两个父节点，CN1表示N1的子节点集合，CN2表示N2的子节点集合，|.|表示集合中元素个数；配置为如果相似度大于门限值G1，则认为两个父节点发生了属性名称的变化的模块。

在一个实施例中，所述配置为根据所述至少一个更新后的记录模式生成所述非关系数据库的模式的模块包括：配置为在路径编码中，提取只包含P-Code的子序列，并统计该子序列出现的频率，并合并相同的P-Code子序列的模块；配置为保留频率超过门限G2的P-Code子序列，并将其按照各层的编码表进行解码生成非关系数据库的模式的模块。

在一个实施例中，其中确定器810包括：配置为提取所述条目中包含的键的模块；配置为确定所述提取的键在所述条目中的层级信息的模块；以及配置为根据所述层级信息确定所述键之间的树状关系的模块。

在一个实施例中，其中生成器830包括：配置为获取所述至少一个路径中的有效路径及其权重的模块；以及配置为基于所述有效路径及其权重，生成所述非关系数据库的模式的模块。

本发明可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括计算机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算机可读程序指令。

计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以是但不限于

电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携式压缩盘只读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质中。

用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构(ISA)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言—诸如Smalltalk、C++等，以及常规的过程式编程语言—诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)，该电子电路可以执行计算机可读程序指令，从而实现本发明的各个方面。

这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。

Claims

1.一种用于生成非关系数据库的模式的方法，包括：

确定非关系数据库的至少一个条目中的记录模式，所述记录模式是该条目中以键为节点的各键层级之间的树状关系，其中键对应于属性名称；

基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式；

基于更新后的记录模式生成所述非关系数据库的模式，

所述方法还包括：

对每个条目的记录模式进行CinP编码，其中，每个节点的CinP编码包括该节点自身编码P-Code以及其子节点的编码C-Code；

所述基于树状关系中子节点的相似度确定存在属性名称变化的节点是基于CinP编码后的记录模式中子节点的相似度确定存在属性名称变化的节点，

所述基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式包括：

将编码后的树形结构记录模式解析成路径集合，所述路径包括叶子节点到根节点所经过的所有节点的编码；

根据某一层的P-Code分桶；

在各桶中，根据该层子节点的相似度判断确定存在属性名称变化的父节点；

将部分所确定的存在属性名称变化的父节点源P-Code更新为目标P-Code，更新该更新后的父节点的相应父节点的C-Code编码。

2.根据权利要求1所述的方法，所述各桶中，根据该层子节点的相似度判断确定存在属性名称变化的父节点包括：

对于存在多条路径的桶，确定出该层子节点的父节点的P-Code不同的节点；

通过所确定的父节点的C-Code以及公式计算父节点的相似度，其中，N₁，N₂代表两个父节点，C_N1表示N₁的子节点集合，C_N2表示N₂的子节点集合，|.|表示集合中元素个数；

如果相似度大于门限值G1，则认为两个父节点发生了属性名称的变化。

3.根据权利要求2所述的方法，根据至少一个更新后的记录模式生成所述非关系数据库的模式包括：

在路径编码中，提取只包含P-Code的子序列，并统计该子序列出现的频率，并合并相同的P-Code子序列；

保留频率超过门限G2的P-Code子序列，并将其按照各层的编码表进行解码生成所述非关系数据库的模式。

4.根据权利要求1所述的方法，其中确定非关系数据库的至少一个条目中的键之间的树状关系包括：

提取所述条目中包含的键；

确定所述提取的键在所述条目中的层级信息；以及

根据所述层级信息确定所述键之间的树状关系。

5.根据权利要求1所述的方法，其中根据基于更新后的记录模式生成所述非关系数据库的模式包括：

获取至少一个路径中的有效路径及其权重；以及

基于所述有效路径及其权重，生成所述非关系数据库的模式。

6.一种用于生成非关系数据库的模式的设备，包括：

确定器，配置用于确定非关系数据库的至少一个条目中的记录模式，所述记录模式是该条目中以键为节点的各键层级之间的树状关系，其中键对应于属性名称；

更新器，配置用于基于所述树状关系中子节点的相似度确定存在属性名称变化的节点，并根据确定的结果更新相应的记录模式；

生成器，配置用于基于更新后的记录模式生成所述非关系数据库的模式，

所述设备还包括：

配置为对每个条目的记录模式进行CinP编码的模块，其中，每个节点的CinP编码包括该节点自身编码P-Code以及其子节点的编码C-Code；

所述更新器是基于CinP编码后的记录模式中子节点的相似度确定存在属性名称变化的节点，

所述更新器包括：

配置为将编码后的树形结构记录模式解析成路径集合的模块，所述路径包括叶子节点到根节点所经过的所有节点的编码；

配置为根据某一层的P-Code分桶的模块；

配置为在各桶中，根据该层子节点的相似度判断确定存在属性名称变化的父节点的模块；

配置为将部分所确定的存在属性名称变化的父节点源P-Code更新为目标P-Code，更新该更新后的父节点的相应父节点的C-Code编码的模块。

7.根据权利要求6所述的设备，所述配置为在各桶中，根据该层子节点的相似度判断确定存在属性名称变化的父节点的模块包括：

配置为对于存在多条路径的桶，确定出父节点的P-Code不同的节点的模块；

配置为通过父节点的C-Code以及公式计算父节点的相似度的模块，其中，N₁，N₂代表两个父节点，C_N1表示N₁的子节点集合，C_N2表示N₂的子节点集合，|.|表示集合中元素个数；

配置为如果相似度大于门限值G1，则认为两个父节点发生了属性名称的变化的模块。

8.根据权利要求7所述的设备，配置为根据至少一个更新后的记录模式生成所述非关系数据库的模式的模块包括：

配置为在路径编码中，提取只包含P-Code的子序列，并统计该子序列出现的频率，并合并相同的P-Code子序列的模块；

配置为保留频率超过门限G2的P-Code子序列，并将其按照各层的编码表进行解码生成所述非关系数据库的模式的模块。

9.根据权利要求6所述的设备，其中确定器包括：

配置为提取所述条目中包含的键的模块；

配置为确定所述提取的键在所述条目中的层级信息的模块；以及

配置为根据所述层级信息确定所述键之间的树状关系的模块。

10.根据权利要求6所述的设备，其中生成器包括：

配置为获取至少一个路径中的有效路径及其权重的模块；以及

配置为基于所述有效路径及其权重，生成所述非关系数据库的模式的模块。