利用索引来搜索结构化文档的系统和方法

具体实施方式

下文中，将参考附图解释本发明的实施例。

附图1是示例了根据本发明一实施例的包括结构化文档搜索系统50的客户服务器系统的硬件配置的模块图。所述客户服务器系统主要由一数据库服务器10和多个客户(客户终端)组成。所述多个客户包括客户20。在客户20上，一应用(应用程序)使用数据库服务器10进行操作。包括客户20的所述多个客户通过例如局域网(LAN)的网络30连接到所述数据库服务器10。在附图1中，除了客户20以外的客户被省略。

所述数据库服务器10是一具有例如一主存储器的存储器11的计算机(数据库服务器计算机)。所述数据库服务器10连接到例如一硬盘驱动器的外部存储设备40。所述外部存储设备40存储数据库管理程序41和数据库42。在所述实施例中，结构化文档搜索系统50通过数据库服务器10和外部存储设备40(数据库42)来实现。

所述数据库管理程序41用于由所述数据库服务器10管理所述数据库42以及用于基于来自客户的查询的搜索处理，所述查询利用XPath，XQuery等等。所述数据库42是一XML文档数据库(结构化文档数据库)，其存储例如XML文档(XML电子文档)这样的结构化文档。

附图2示例了存储在数据库42中的XML文档集合的例子。在附图2的例子中，所述数据库42存储一包括XML文档101到XML文档103的XML文档的集合。包含在存储于数据库42中的XML文档中的每个节点具有如传统技术中一样的指示所述节点位置的节点ID。在附图2中，每个所述节点附近的数字指示所述节点的节点ID。

附图3是主要示例了附图1的结构化文档搜索系统50的功能配置的模块图。所述结构化文档搜索系统50包括一数据库管理系统51和数据库42。所述数据库42不仅存储XML文档集合还存储索引表格421、值索引表格422和结构索引表格423。

所述索引表格421用于管理关于节点的信息(索引信息)，所述节点包括在存储于数据库42中的XML文档中并且将被分配(设置)值索引。所述值索引表格422保存被分配给(被对应附加给)由所述索引表格421管理的所述节点(被认为是一值搜索的可能目标的节点)的值索引(索引信息项)。每个所述值索引包括节点(元素)的值(关键词)，所述节点的节点ID以及相关节点(此处，指一父节点)的节点ID。所述结构索引表格423保存表示所述节点的结构的结构索引，所述节点包括在存储于数据库42中的XML文档中。

所述数据库管理系统51包括一请求处理单元52，一搜索单元53，一索引管理单元54，一文档存储处理单元55，一数据库操作单元56，一索引表格57，一值索引表格58以及一结构索引表格59。

从客户20接收一请求(命令)，所述请求处理单元52确定所述请求的类型，并且基于所述确定的结果把所述请求发送给所述搜索单元53、索引管理单元54或者文档存储处理单元55。如果来自客户20的所述请求是一搜索请求，则所述请求处理单元52把所述搜索请求发送到所述搜索单元53。如果来自客户20的所述请求是一索引请求，则所述请求处理单元52把所述索引请求发送到所述索引管理单元54。如果来自客户20的所述请求是一文档存储请求，则所述请求处理单元52把所述文档存储请求发送到所述文档存储处理单元55。

通过所述请求处理单元52接收来自客户20的搜索请求，所述搜索单元53基于包括在所述搜索请求中的一查询来执行一搜索处理。在所述搜索处理中，所述索引管理单元54(由所述索引管理单元54管理的所述值索引表格58和结构索引表格59)被使用。所述搜索单元53包括一值索引搜索模块531，一结构索引搜索模块532以及一搜索结果获取模块533。

所述值索引搜索模块531在值索引表格58中搜索其值符合在所述搜索请求(查询)中指定的搜索条件的值索引。所述结构索引搜索模块532在所述结构索引表格59中搜索其结构符合在所述搜索请求中指定的搜索条件的结构索引。所述搜索结果获取模块533基于在所述值索引搜索模块531和结构索引搜索模块532中搜索所述索引的结果来获取所述搜索请求的搜索结果。

所述索引管理单元54通过所述请求处理单元52从所述客户20接收索引请求，并且基于所述索引请求来执行一索引处理。在所述索引处理中，关于在一XML文档中的元素(节点)的信息被添加到所述索引表格57，其中在所述索引请求中指定的值索引将被分配(设置)到所述XML文档中的元素。利用所述索引表格57，所述索引管理单元54也管理关于已被分配(设置)值索引的节点的信息。基于所述值索引表格58，所述索引管理单元54进一步为符合值搜索条件的节点产生一索引信息项(值索引)的列表。当所述值搜索条件包含一结构条件时，所述索引管理单元54基于所述结构索引表格59进一步为符合所述结构条件的节点产生一索引信息项(结构索引)的列表。当所述搜索单元53执行一值搜索处理时，所述索引管理单元54根据来自所述搜索单元53的所述请求产生一列表。产生的列表被发送到所述搜索单元53。

所述文档存储处理单元55通过所述请求处理单元52从客户20接收所述文档存储请求，并且执行把在所述文档存储请求中指定的一XML文档存储到数据库42中的文档存储处理。在所述文档存储处理中，所述文档存储处理单元55产生如下的值索引并把所述值索引添加到所述值索引表格58，即在包括在存储于所述数据库42中的XML文档中的节点之中，所述值索引将被分配给那些被指定在索引表格57进行索引的节点。所述数据库操作单元56起接口的作用，该接口使搜索单元53、索引管理单元54以及文档存储处理单元55能够访问数据库42并且在数据库42上执行处理。

所述索引表格57、值索引表格58和结构索引表格59分别相应于存储于数据库42中的索引表格421、值索引表格422和结构索引表格423。在实施例中，在所述结构化文档搜索系统50启动时，所述索引表格421、值索引表格422和结构化索引表格423作为索引表格57、值索引表格58和结构化索引表格59从数据库42中被复制到附图1中的存储器11中。当所述结构化文档搜索系统50在操作时，所述索引表格57、值索引表格58和结构索引表格59被查阅或者更新。索引表格57、值索引表格58和结构索引表格59的被更新的内容周期性地或者根据需要(如，当系统50的负载低时)反映在索引表格421、值索引表格422和结构索引表格423中。

附图4示例了附图3中所示的所述索引表格57的数据结构的例子。在该实施例中，所述索引表格57用作为每个路径(路径字符串)保存索引信息的索引信息存储单元。索引信息包括相应于所述索引信息的路径和相关节点类型信息。

所述路径是一绝对路径，其将在该路径中指定的一节点的结构表示为从根节点到所述节点的路径。相关节点类型信息指示与在所述路径中指定的所述节点(指定节点)具有特定关系的一节点(相关节点)的类型，所述路径被使得相应于包括所述指定节点的XML文档的层次结构(树状结构)的信息。当所述结构化文档搜索系统50发起搜索多个节点并且为所述多个节点所共有的一相关节点被获取作为搜索的结果时，用户指定所述类型。相关节点是在包括所述指定节点的XML文档的层次结构(树状结构)上与所述指定节点具有一特定关系的节点。例如，一相关节点是父节点或兄弟节点。一相关节点可以在包括所述指定节点的XML文档的树状结构上从所述指定节点进行追溯。在该实施例中，为简化说明，假设相关节点的类型限定为父节点。

附图5示例了附图3中所示的值索引表格58的数据结构的例子。在该实施例中，所述值索引表格58用作保存(存储)分配给节点的值索引(索引信息项)的一值索引存储单元，所述节点利用所述索引表格57进行管理。每个值索引包括一节点的值、所述节点的节点ID以及与所述节点相关的一相关节点的节点ID(相关节点ID)。所述值索引与传统技术的不同点在于其添加了相关节点ID。附图5的所述值索引表格58包括分配给附图2的XML文档101到XML文档103中的最后节点和第一节点的值索引。

附图6示例了附图3中所示的结构索引表格59的数据结构的例子。所述结构索引表格59用作结构索引存储单元，用于保存(存储)表示节点结构的结构索引，所述节点包括在存储于数据库42中的XML文档中。如在传统技术中，应用于该实施例中的每个结构索引包括表示结构的路径(路径字符串)和具有由所述路径指示的结构的节点的节点ID。

附图6的所述结构索引表格59包括分配给(被对应附加给)附图2的XML文档101到XML文档103中的个体节点的结构的结构索引。当多个节点IDs相应于一单个的路径(路径字符串)时，多个节点IDs以这样的方式被输入所述结构索引表格59中，即，使得所述多个节点IDs相应于所述单个路径。这种情况的一个例子是与附图2的XML文档101到XML文档103具有相同的结构的多个XML文档被存储于数据库42的情况。

在该实施例中，假设附图1的数据库服务器10把外部存储设备40中存储的数据库管理程序41读入到服务器10的存储器11中并且执行所述程序41，因而实现所述单元52到56。所述程序41被存储于一计算机可读存储媒介，如压缩盘或ROM，并且因此是可分发的。此外，所述程序41可以通过网络30下载到数据库服务器10中。此外，所述单元52到56可以由硬件组成。

接着，将解释附图3的结构化文档搜索系统50的操作。

<索引处理>

将参考附图7的流程图解释结构化文档搜索系统50中的索引处理。假设，例如，具有如附图2所示的树状结构的XML文档101到XML文档103被显示于客户20的显示器上。在附图2的示例中，所述XML文档101到103存储于称为“bib”的一个集合中并受其管理，该集合相应于文件系统中的文件夹或者目录。XML文档101到XML文档103中的最上层节点是书(book)节点。这些书节点的父节点是一bib节点。在附图2的示例中，所述bib节点是包含XML文档101到XML文档103的一树状结构中的一根节点，

在示例了具有如附图2所示的树状结构的XML文档101到XML文档103的状态中，假设用户通过操作，例如，鼠标指定了一任意节点作为将产生其索引的节点。指定了节点后，假设用户操作所述客户20以指定索引。在这个例子中，如果必须指定相关节点，则用户指定所期望的相关节点的类型。

然后，根据来自所述用户的指令，所述客户20通过网络30向所述结构化文档搜索系统50发送一索引请求以为所述指定节点设置(分配)一索引(步骤S1)。所述索引请求包括一路径(绝对路径)和一相关节点的类型，所述路径表示将被设置索引的节点的结构。

从所述客户20接收所述索引请求，所述结构化文档搜索系统50的所述请求处理单元52把所述索引请求转交给所述索引管理单元54，由此请求所述索引管理单元54执行索引(步骤S2)。通过所述请求处理单元52从所述客户20接收所述索引请求，所述索引管理单元54把关于在所述请求中指定的节点(即，将被设置所述索引的节点)的索引信息添加到所述索引表格57中(步骤S3)。此处，作为关于所述指定节点的索引信息，指示表示所述指定节点的结构的一路径和与所述指定节点相关的一节点(相关节点)的类型的信息(相关节点类型信息)被添加到所述索引表格57中。

相应地，例如，如果所述指定节点是如附图2中节点ID为6的一节点并且所述指定相关节点的类型是一父节点，则指示“/bib/book/author/last”作为路径(路径字符串)并且还指示“一个父节点”作为所述相关节点的类型的索引信息被添加到表格57(参见附图4)。相似地，如果所述指定节点是如附图2中的节点ID为8的一节点并且所述指定相关节点的类型是一父节点，则指示“/bib/book/author/first”作为路径并指示“一个父节点”作为所述相关节点的类型的索引信息被添加到表格57(参见附图4)。

<文档存储处理>

接着，将参考附图8中的流程图解释在索引之后的一文档存储处理。假设用户已指定一XML文档存储于数据库42中并且操作客户20指定所述XML文档的存储。然后，所述客户20通过网络30向所述结构化文档搜索系统50发送一文档存储请求以将指定的XML文档存储到数据库42中(步骤S11)。

从客户20接收所述文档存储请求，所述请求处理单元52把所述文档存储请求转交给所述文档存储处理单元55，由此请求所述文档存储处理单元55存储所述XML文档(步骤S12)。通过所述请求处理单元52从所述客户20接收所述文档存储请求，所述文档存储处理单元55开始解析所述请求中指定的所述XML文档(步骤S13)。每次从所述XML文档中抽取一节点作为解析所述XML文档的结果时，所述文档存储处理单元55在所述节点上执行下面的处理(步骤S14)。从所述XML文档中抽取的节点的顺序与出现在所述XML文档中的节点的顺序相一致。

首先，所述文档存储处理单元55询问所述索引管理单元54所述被抽取节点上的信息(在此，表示所述被抽取节点的结构的路径)是否已被输入到所述索引表格57(步骤S15)。然后，所述索引管理单元54查阅所述索引表格57以检查表示被询问节点的结构的路径(路径字符串)是否已被存储于所述索引表格57，并且向所述文档存储处理单元55通知结果。如果该节点已被存储，则所述索引管理单元54进一步向所述文档存储处理单元55通知相关节点的类型，所述相关节点类型在存储于所述索引表格57中的相关节点类型信息中以这样的方式被指示，即，使得所述类型相应于表示所述被询问节点的结构的路径。

从所述索引管理单元54接收所述通知，所述文档存储处理单元55确定(表示所述被抽取节点的结构的一路径)所述被抽取的节点是否已经存储在所述索引表格57中(步骤S16)。如果已经被存储，基于来自所述索引管理单元54的所述通知，所述文档存储处理单元55检查存储在所述索引表格57中的相关节点的类型以相应于表示所述被抽取节点的结构的路径。

接着，所述文档存储处理单元55向所述索引管理单元54询问所述被抽取节点的值是否已经被存储于所述值索引表格58中(步骤S17)。于是，所述索引管理单元54查阅所述值索引表格58以检查被询问的值是否已经存储于所述值索引表格58中，并且向所述文档存储处理单元55通知其结果。从所述索引管理单元54接收所述通知，所述文档存储处理单元55确定所述被抽取节点的值是否已经存储在所述值索引表格58中(步骤S18)。

如果所述值没有被存储(步骤S18)，所述文档存储处理单元55促使所述索引管理单元54把所述被抽取节点的值、所述节点的节点ID以及确定类型的相关节点(这个例子中是父节点)的节点ID添加到所述值索引表格58中(步骤S19)。在此，如果相关节点是如所述实施例中的父节点，则所述相关节点已经被抽取。这对于所述相关节点是，例如，长兄(elderbrother)节点或一父节点的父节点(即，祖父节点)的情况也成立。如果所述相关节点是，例如，一弟(younger brother)节点时，则所述文档存储处理单元55追溯所述树状结构并且抽取所述弟节点。相反，如果所述被抽取节点的值已经被存储(步骤S18)，则所述文档存储处理单元55使得所述被抽取节点的节点ID和确定类型的相关节点(在这个例子中是父节点)的节点ID相应于所述被存储的值，并且促使所述索引管理单元54把所述结果添加到所述值索引表格58(步骤20)。

在执行步骤S19或步骤S20后，所述文档存储处理单元55向所述索引管理单元54询问表示所述被抽取节点的结构的路径(路径字符串)是否已经被存储于所述结构索引表格59中(步骤S21)。如果已经确定(表示所述被抽取节点的结构的路径)所述被抽取节点没有被存储在所述索引表格57中(步骤S16)，则所述文档存储处理单元55立即执行步骤S21。

从所述文档存储处理单元55接收到查询，所述索引管理单元54查阅所述结构索引表格59。然后，所述索引管理单元54检查表示被询问节点的结构的路径(路径字符串)是否已经存储在所述结构索引表格59中，并且向所述文档存储处理单元55通知其结果。从所述索引管理单元54接收所述通知后，所述文档存储处理单元55确定表示所述被抽取节点的结构的路径是否已经被存储在所述结构索引表格59中(步骤S22)。

如果其没有被存储(步骤S22)，则所述文档存储处理单元55促使所述索引管理单元54把表示所述被抽取节点的结构的路径(路径字符串)和所述节点的节点ID添加到所述结构索引表格59中(步骤S23)。相反，如果表示所述被抽取节点的结构的路径已经被存储(步骤S22)，则所述文档存储处理单元55使得所述节点的节点ID相应于所述存储的路径，并且使得所述索引管理单元54把结果的集合添加到所述结构化索引表格59中(步骤S24)。

在执行步骤S23或S24之后，所述文档存储处理单元55执行一文档存储操作以把所述被抽取的节点(即，所述XML文档的一部分)存储到所述数据库42中(步骤S25)。

在执行所述文档存储操作之后，所述文档存储处理单元55确定所述由客户20请求的对XML文档的分析是否已经完成(步骤S26)。即，所述文档存储处理单元55确定包含在所述被请求的XML文档中的所有节点是否都已经被处理。如果还存在没有被处理的节点，则所述文档存储处理单元55返回到步骤S14并且继续处理下一个节点。

通过上述处理，分配到其结构存储于所述索引表格57中的所述节点的值索引被添加到所述值索引表格58中。所述值索引与传统值索引的不同在于其不仅仅包括一节点(元素)的值和该节点的节点ID，还包括相关节点(在这个例子中是父节点)的节点ID(相关节点ID)。附图5中所述值索引表格58包括当附图2中的所述XML文档101到XML文档103被添加到所述数据库42中时所添加的值索引。

<搜索处理>

接着，将参考附图9A和9B中的流程图来解释利用存储在所述值索引表格58中的值索引和存储在所述结构索引表格59中的结构索引的一搜索处理。假设，作为用户操作客户20的一个结果，所述客户20已经通过所述网络30向所述结构化文档搜索系统50发送一搜索请求(步骤S31)。假定所述搜索请求包括例如用XPath书写的一查询。这时，假设具有附图2中所述结构的XML文档101到103已经存储于数据库42中。此外，假设附图5中所述的值索引表格58包括当附图2中的所述XML文档101到103被存储到所述数据库42中时所添加的值索引。

从所述客户20接收所述搜索请求后，所述请求处理单元52把所述搜索请求转交给所述搜索单元53，由此请求所述搜索单元53执行搜索(步骤S32)。通过请求处理单元52从所述客户20接收所述搜索请求后，所述搜索单元53分析所述搜索请求(步骤S33)。在此，假设包含在所述搜索请求中的查询是在背景技术部分中所写的第二查询：(xPath)

/bib/book/author[last＝”Stevens”and first＝”W.”]。

即，假设客户20作出一搜索一作者(父节点)的搜索请求，所述作者满足条件last＝”Stevens”和first＝”W.”。在此，所述条件last＝”Stevens”，即，最后节点的值为”Stevens”的条件是所述值搜索中的一个条件。相似地，所述条件first＝”W.”，即，第一节点的值为”W.”的条件是所述值搜索中的一个条件。

基于步骤S23中分析的结果，所述搜索单元53确定所述被请求的搜索是否是覆盖多个节点的值的一值搜索以及所述被请求的搜索目标节点是否是父节点，其中对所述多个节点设置了索引(步骤S34)。在该实施例中，符合在步骤S34中的确定条件。在这个例子中，利用所述值索引表格58，所述搜索单元53的值索引搜索模块531执行如下的搜索。

所述值索引搜索模块531从多个值搜索条件中选择一个未处理的条件(步骤S35)。在此，假设选择了last＝”Stevens”。所述值索引搜索模块531从所述索引管理单元54中请求符合选出的值搜索条件的节点(值为”Stevens”的最后节点)的值索引列表(步骤S36)。在下面的解释中，符合选出的值搜索条件的节点被称为候选节点。

根据来自所述值索引搜索模块531的请求参考所述值索引表格58，所述索引管理单元54产生所述被请求的候选节点(值为”Stevens”的最后节点)的值索引的列表作为第一候选节点列表。所述第一候选节点列表包括候选节点的值和下述所有节点的节点IDs的集合，所述所有节点包括基于候选节点的节点的相关节点(父节点)的值和节点IDs(相关节点IDs)。每个节点ID和相关节点ID的集合可以被分配节点值(这个例子中是“Stevens”)。即，第一候选节点列表可以是值、节点ID和相关节点ID的集合的列表。

所述索引管理单元54向所述搜索单元53的值索引搜索模块531通知基于所述值索引表格58产生的第一候选节点列表。结果，所述值索引搜索模块531获取通知的第一候选节点列表(步骤S37)。即，所述值索引搜索模块531通过所述索引管理单元54在所述值索引表格58中搜索符合所述值搜索条件的值索引来获取所述第一候选节点列表。

在获取所述第一候选节点列表之后，所述值索引搜索模块531作为一排序单元并且例如以所述候选节点的节点IDs和相关节点IDs(父节点IDs)的升序排列所述第一候选节点列表(步骤S38)。在此，所述候选节点的节点IDs被给定优先权。所述被排序的第一候选节点列表被存储于包含在附图1的数据库服务器10中的存储器11的指定区域中。

在执行步骤S38之后，所述值索引搜索模块531确定所有值搜索条件是否都已被处理(步骤S39)。如果还有未处理的值搜索条件，则所述值索引搜索模块531返回到步骤S35并选择所述未处理条件之一。在此，假设选择了值搜索条件first＝“W.”。

所述值索引搜索模块531执行步骤S36中的处理并且推进到符合所述选择的值搜索条件的候选节点(值为“W.”的第一节点)。结果，所述值索引搜索模块531获取候选节点(值为“W.”的第一节点)的值索引(索引信息)列表作为第一候选节点列表并且排序所述列表。被排序的第一候选节点列表被存储在附图1的存储器11的指定区域中。

附图10A和10B分别示例了在附图5的所述值索引表格58的例子中获取的值为“Stevens”的最后节点的第一候选节点列表111和值为“W.”的第一节点的第一候选节点列表112的例子。附图11示例了包含在附图10A和10B中示例的候选列表111和112中的值为“Stevens”的最后节点和值为“W.”的第一节点在附图2的XML文档101到103中的位置。在附图11中，每个边框箭头指示值为“Stevens”的最后节点的一相关节点(父节点)或值为“W.”的第一节点的一相关节点(父节点)。

假设所述搜索单元53的值索引搜索模块531已经处理了所述值搜索条件中所述多个节点中的所有节点(步骤S39)。那么，所述搜索单元53中的结构索引搜索模块532被启动。所述结构索引搜索模块532从所述多个值搜索条件中选择一个未处理的条件(步骤S40)，并抽取包含在所选择的条件中的结构条件(步骤S41)。在此，在值为“Stevens”的最后节点的值搜索条件中所指定的节点的结构条件(表示所述结构条件的路径)“/bib/book/author/last”被抽取。所述结构索引搜索模块532从所述索引管理单元54中请求符合所抽取的结构条件(/bib/book/author/last)的节点(候选节点)的结构索引列表(步骤S42)。

所述索引管理单元54根据来自所述结构索引搜索模块532的请求查阅所述结构索引表格59，由此，产生符合所述被请求(被选择)的结构条件(/bib/book/author/last)的候选节点的结构索引列表作为第二候选节点列表。所述第二候选节点列表包括符合所述结构条件的路径(路径字符串)和由该路径指定的所有节点(候选节点)的节点IDs。每个节点ID可以被分配一表示所述被选择的结构条件的路径(“/bib/book/author/last”)。即，所述第二候选节点列表可以是一路径和一节点ID的集合的列表。

所述索引管理单元54向所述搜索单元53的结构索引搜索模块532通知所产生的第二候选节点列表。结果，所述结构索引搜索模块532获取所通知的第二候选节点列表(步骤S43)。即，所述结构索引搜索模块532通过所述索引管理单元54，在所述结构索引表格59中搜索符合包含在所述值搜索条件中的所述结构条件的结构索引，由此获取所述第二候选节点列表。

在获取所述第二候选节点列表之后，所述结构索引搜索模块532作为一排序单元并且以例如，所述候选节点的节点IDs的升序来排列所述第二候选节点列表(步骤S44)。所述被排序的第二候选节点列表存储在包含在附图1的数据库服务器10中的存储器11的指定区域。

在执行步骤S44之后，所述结构索引搜索模块532确定是否所有值搜索条件都已经被处理(步骤S45)。如果还存在未处理的值搜索条件，所述结构索引搜索模块532返回到步骤S40，选择未处理的条件之一，并且抽取包含在所选择的条件中的结构条件(步骤S41)。在这个例子中，假设值为“W.”的第一节点的结构条件(表示所述结构条件的路径)“/bib/book/author/first”已经被抽取。

所述结构索引搜索模块532执行步骤S42中的处理并且推进到所抽取的结构条件“bib/book/author/first”。结果，所述结构索引搜索模块532获取符合所述结构条件“/bib/book/author/first”的候选节点的结构索引列表作为第二候选节点列表并且排序所述列表。所述被排序的第二候选节点列表被存储在附图1的存储器11中的指定区域。

附图12A和12B分别示例了从附图6的所述结构索引表格59的例子中获取的符合结构条件“/bib/book/author/last”的最后节点的第二候选节点列表113和符合结构条件“/bib/book/author/first”的第一节点的第二候选节点列表114的例子。

假设所述搜索单元53的所述结构索引搜索模块532已经处理了所述值搜索条件中的多个节点中的所有节点(步骤S45)。那么，所述搜索单元53的搜索结果获取模块533被启动。利用所述候选节点的节点IDs，所述搜索结果获取模块533在基于值搜索条件的条件下，将基于所述值索引表格58获取的第一候选节点列表和基于所述结构索引表格59获取的第二候选节点列表进行合并(步骤S46)。在此，所述搜索结果获取模块533利用所述候选节点的节点IDs作为关键词对所述第一和第二候选列表执行AND操作，由此合并所述第一和第二候选列表。这样的AND操作被称为AND合并操作。

结果，根据所述值搜索条件(last＝”Stevens”和first＝”W.”)产生附图13A和13B所示的第三候选节点列表115和116。所述第三候选节点列表115是对附图10A中的第一候选节点列表111和附图12A中的第二候选节点列表113执行AND合并操作的结果。对于包含在所述列表111和113两者中的所有节点IDs(候选节点IDs)来说，所述第三候选节点列表115不仅包括节点ID和相关节点ID的集合，而且还包括为具有所述节点IDs的节点(元素)所共有的值。所述第三候选节点列表116是对附图10B中的第一候选节点列表112和附图12B中的第二候选节点列表114执行AND合并操作的结果。所述第三候选节点列表116不仅包括包含在列表112和114两者中的节点IDs的所述节点ID和相关节点ID的集合，而且还包括为具有所述节点ID的节点(元素)所共有的值。

在执行步骤S46之后，所述搜索结果获取模块533在根据所述值搜索条件所产生的第三候选节点列表之中搜索相关节点IDs(在这个例子中是父节点IDs)相互一致的组合(步骤S47)。在此，利用包含在相应于所述值搜索条件的所述第三候选节点列表中的所述相关节点IDs作为关键词，所述搜索单元53a对所述第三候选节点列表执行一AND合并操作，由此搜索其相关节点IDs(父节点IDs)相互符合的组合。附图14示例了一组合的列表(搜索结果列表)117，所述组合的相关节点IDs(父IDs)在附图13A和附图13B所示的候选节点列表115和116之间相互一致。在此，仅仅是其值为15的相关节点在所述候选节点列表115和116之间相互一致。即，仅仅是其值为15的相关节点为所述候选节点列表115和116所共有(be common to)。如从附图11中看到的，其值为15的相关节点ID是符合在来自所述客户20的搜索请求中所请求的条件last＝”Stevens”和first＝”W.”的作者的节点ID。

所述搜索结果获取模块533把包含在从步骤S47中获取的所述搜索结果列表中的所述相关节点IDs(即，在根据所述值搜索条件产生的所述第三候选节点列表之间相互一致的相关节点IDs)作为通过所述请求处理单元52来自客户20的所述搜索请求的搜索结果返回给客户20(步骤S48)。当附图14的所述搜索结果列表117已经被获取时，其值为15的相关节点ID，即，满足条件last＝”Stevens”和first＝”W.”的作者的节点ID(＝15)作为搜索结果被返回给客户20。

如上面描述的，在所述实施例中，所述相关节点(父节点)的节点IDs(相关节点IDs)包含在保存于所述值索引表格58中的所述值索引中。因此，在所述实施例中，用于覆盖多个节点的值的值搜索和用于搜索为所述多个节点所共有的相关节点(父节点)的一个搜索处理可以仅仅通过查阅所述值索引表格58的一索引操作来执行。即，在所述实施例中，所述搜索处理可以不必搜索数据库42中的所有XML文档而高速地被执行。

如果一搜索不符合值搜索覆盖多个节点的值且被请求搜索的节点是所述多个节点的相关节点(父节点)的条件(步骤S34)，则所述搜索单元53执行传统搜索处理(步骤S50)。

在所述实施例中，在所述索引表格57中被管理的节点(最后节点和第一节点)的相关节点的类型是一父节点的情况是一前提条件。然而，在所述索引表格57中被管理的节点(最后节点和第一节点)的相关节点的类型可以是不同于一父节点的节点。例如，满足条件last＝”Stevens”和first＝”W.”的作者所写的一本书的标题被作为想要的搜索结果时，所述用户在一索引请求中指定一父节点的兄长节点(即，伯父节点)作为一相关节点，使得适合用于由所述用户使用的搜索条件的相关节点上的信息能够被包含于保存在所述值索引表格58中的一个值索引中。这使得即使所述搜索条件(搜索目标节点)改变时也有可能高速地执行搜索。

[实施例变体]

接着，将参考附图解释所述实施例的一个变体(特别地，结构化文档搜索系统50的一个变体)。附图15是一模块图，主要示例了应用于所述变体的一结构化文档搜索系统50a的功能配置。在附图15中，与附图3中元素相等同的元素由相同的附图标记指示。

所述结构化文档搜索系统50a相应于所述实施例中的所述结构化文档搜索系统50。与所述结构化文档搜索系统50相似，假设所述所述结构化文档搜索系统50a由附图1中所示的数据库服务器10和外部存储设备40(数据库42)实现。

所述结构化文档搜索系统50a包括一数据库管理系统51a和数据库42。在该变体中，在所述数据库42中存储了一XML文档集合、一索引表格421、一值索引表格422a和一结构索引表格423a。

与传统值索引表格具有相同数据结构的所述值索引表格422a与应用于所述实施例中的值索引表格422不同，其不具有相关IDs。所述结构索引表格423a保存被对应附加给(被分配给)在所述索引表格421中被管理的节点(被认为是一值搜索的可能目标的节点)的结构索引。如后面将详细描述的，每个所述结构索引包括表示一节点(元素)的结构的路径(路径字符串)、由所述路径指定的节点的节点ID以及与所述节点相关的一相关节点(在这个例子中是父节点)的节点ID的集合。

所述数据库管理系统51a与附图3中的所述结构化文档搜索系统50的不同在于一搜索单元53a、一值索引表格58a和一结构索引表格59a代替了所述搜索单元53、值索引表格58和结构索引表格59。所述值索引表格58a和结构索引表格59a相应于存储在数据库42中的值索引表格422a和结构索引表格423a。在所述结构化文档搜索系统50a启动时，所述值索引表格422a和结构索引表格423a作为所述值索引表格58a和结构索引表格59a被复制到存储器11中。

所述搜索单元53a与所述实施例中的搜索单元53的不同在于，其不仅包括值索引搜索模块531、结构索引搜索模块532和搜索结果获取模块533，还包括一节点数目确定模块534和一文档搜索模块535。所述节点数目确定模块534确定包含在由所述值索引搜索模块531获取的所述第一候选节点列表中的候选节点的总数目是否大于或等于预先确定的指定数目。如果所述候选节点的总数目小于所述指定数目，则所述文档搜索模块535搜索数据库42中存储的XML文档。在所述搜索中，所述文档搜索模块535获取符合结构条件的候选节点的列表(第四候选节点列表)并且搜索其相关IDs在所述列表之间相一致的组合。

附图16示例了附图15中所示的值索引表格58a的数据结构的例子。与所述实施例中的值索引表格58相似，所述值索引表格58a保存了分配给利用所述索引表格57管理的所述节点的值索引。在此，保存在值索引表格53a中的值索引与保存在所述值索引表格58中的值索引的不同在于其没有相关节点ID。附图16中所述的值索引表格58a包括分配给附图2中的XML文档101到103中的最后节点和第一节点的值索引。

附图17示例了附图15中所示的结构索引表格59a的数据结构的例子。与所述实施例中的所述结构索引表格59相似，所述结构索引表格59a被用于保存表示存储在数据库42中的XML文档中的所述节点的结构的结构索引。每个所述结构索引包括表示所述结构的路径(路径字符串)、由所述路径指定的所述节点的节点ID以及与所述节点相关的一相关节点的节点ID(相关节点ID)。所述结构索引与保存在所述结构索引表格59中的结构索引的不同在于添加了相关节点ID。即，在所述变体中，所述相关节点ID被分配给结构索引而不是值索引。附图17中的所述结构索引表格59a包括相应于附图2中XML文档101到103中的每个节点的结构的结构索引。

接着，将解释附图11中的所述结构化文档搜索系统50a的操作，主要着重于解释与所述实施例中的所述结构化文档搜索系统50的不同之处。

<文档存储处理>

首先，将参考附图18中的流程图解释在所述变体中索引之后的一文档存储处理。在附图18中，与附图8的流程图中相同的处理步骤由相同的附图标记指示。

假设客户20向所述结构化文档搜索系统50a发送一文档存储请求以将一用户指定XML文档存储到数据库42中(步骤S11)。然后，所述结构化文档搜索系统50a的文档存储处理单元55开始解析指定的XML文档(步骤S13)。然后，每当从所述指定的XML文档中抽取一节点时，所述文档存储处理单元55如下处理所述节点(步骤S14)。

首先，所述文档存储处理单元55向所述索引管理单元54询问关于所抽取节点的信息(一路径)是否已被输入到所述索引表格57中(步骤S15)。如果已经被输入(步骤S16)，则所述文档存储处理单元55基于所述索引管理单元54响应于所述询问所给出的通知，检查由存储在所述索引表格57中的相关节点类型信息所指示的所述相关节点的类型，以相应于表示所述被抽取的节点的结构的路径。

如果关于被抽取节点的信息(所述路径)已经被存储在所述索引表格57中(步骤S16)，则所述文档存储处理单元55向所述索引管理单元54询问所述节点的值是否已经存储于所述值索引表格58a中(步骤S17)。如果所述值没有被存储(步骤S18)，则所述文档存储处理单元55促使所述索引管理单元54将被抽取节点的值和该节点的节点ID添加到所述值索引表格58a中(步骤S19a)。相反地，如果所述被抽取节点的值已经被存储(步骤S18)，则所述文档存储处理单元55使得所述节点的节点ID相应于所存储的值，并且使得所述索引管理单元54把所述结果添加到所述值索引表格58a中(步骤S20a)。

在执行步骤S19a或S20a之后，所述文档存储处理单元55向所述索引管理单元54询问表示所述被抽取节点的结构的路径(路径字符串)是否已经被存储于结构索引表格59a中(步骤S21)。如果已经确定在步骤S14中所抽取节点上的信息没有被存储在所述索引表格57中(步骤S16)，则所述文档存储处理单元55立即执行步骤S21和S22。

如果表示所述被抽取节点的结构的路径没有被存储(步骤S22)，则所述文档存储处理单元55促使所述索引管理单元54把所述路径(路径字符串)、所述节点的节点ID和确定类型的相关节点的节点ID添加到所述结构索引表格59中(步骤S23)。相反地，如果表示所述被抽取节点的结构的路径已经被存储(步骤S22)，则所述文档存储处理单元55使得所述节点的节点ID和确定类型的相关节点的节点ID相应于所述路径，并且使得所述索引管理单元54将所述生成的组合添加到所述结构索引表格59中(步骤S24a)。在用于没有存储于所述索引表格57中的节点的结构的结构索引(即，用于相关节点类型没有被确定的节点的结构的结构索引)中，没有包括所述相关节点的节点ID。

在执行步骤S23a或S24a之后，所述文档存储处理单元55执行一文档存储操作以将所述被抽取的节点(即，所述XML文档的一部分)存储于数据库42中(步骤S25)。所述文档存储处理单元55重复上述操作，直到完成对客户20请求的XML文档的分析。

<搜索处理>

接着，将参考附图19A和19B的流程图解释利用存储于所述值索引表格58a中的值索引和存储于所述结构索引表格59a中的结构索引的搜索处理。在附图19A和19B中，与附图9A和9B的流程图中相同的处理步骤由相同的附图标记指示。

假设客户20向所述结构化文档搜索系统50a发送一搜索请求，该搜索请求包括以例如XPath撰写的一个查询(步骤S31)。假定所述查询是第二查询(XPath)。如上面描述的，所述第二查询包括last＝”Stevens”的值搜索条件和first＝”W.”的值搜索条件。此外，这些值搜索条件包括节点要具有由“/bib/book/author/last”表示值为“Stevens”的最后节点结构的结构条件以及节点要具有由“/bib/book/author/first”表示值为“W.”的第一节点结构的结构条件。

在这个例子中，与所述实施例中的所述结构化文档搜索系统50相似，结构化文档搜索系统50a执行步骤S32到步骤S39。特别地，包括在所述结构化文档搜索系统50a中的所述搜索单元53a的值索引搜索模块531从所述索引管理单元54获取与多个值搜索条件中的每一个都符合的节点列表(第一候选节点列表)，并排序所述列表。然而，在变体中，第一候选节点列表利用所述值索引表格58a而产生，并且按照候选节点的ID节点的升序来进行排序。

附图20A和20B分别示例了附图16的所述值索引表格58a的例子中获取的值为“Stevens”的最后节点的第一候选节点列表111a和值为“W.”的第一节点的第一候选节点列表112a的例子。所述候选节点列表111a和112a不包括相关节点ID，与附图10A和10B所示例的候选节点列表111和112不同。

当为多个值搜索条件中的每一个获取了第一候选节点列表时(步骤S39)，所述搜索单元53a的节点数目确定模块534被启动。在排序之后，所述节点数目确定模块534计算包含在所有第一候选节点列表中的候选节点的节点IDs的总数目，即，候选节点的总数目(步骤S61)。然后，所述节点数目确定模块534确定所述候选节点的总数目是否大于或等于预先指定的数目(步骤S62)。

在此，假设所述候选节点的总数目大于或等于所述指定数目(步骤S62)。在这种情况中，如在所述实施例中一样，所述搜索模块53a的结构索引搜索模块532执行步骤S40到步骤S45。特别地，所述结构索引搜索模块532基于所述结构索引表格59a为包含在多个值搜索条件中的每个结构条件执行获取符合所述结构条件的节点列表(第二候选节点列表)的处理。结果，所述结构索引搜索模块532获取如附图21A和21B所示的第二候选节点列表113a和114a。

所述候选节点列表113a是符合结构条件“/bib/book/author/last”(表示所述结构条件的路径)的节点(候选节点)的结构索引的列表，用于由最后节点值为“Stevens”的值搜索条件所指定的节点。所述候选节点列表114a是符合结构条件“/bib/book/author/first”(表示所述结构条件的路径)的节点(候选节点)的结构索引的列表，用于由第一节点值为“W.”的值搜索条件所指定的节点。由于用于产生候选列表113a和114a的结构索引表格59a的特性，所述列表113a和114a包括相关节点IDs，与所述候选节点列表113和114不同。

当为包含在多个值搜索条件中的每个结构条件获取了第二候选节点列表时(步骤S45)，所述搜索单元53的搜索结果获取模块533被启动。利用候选节点的节点IDs，所述搜索结果获取模块533基于值搜索条件，对基于所述值索引表格58a获取的第一候选节点列表和基于所述结构索引表格59a获取的第二候选节点列表执行一AND合并操作(步骤S46)。

在此，在附图20A的第一候选节点列表111a和附图21A的第二候选节点列表113a上执行一AND合并操作，由此产生如所述实施例中的附图13A所示的第三候选节点列表115。相似地，在附图20B的第一候选节点列表112a和附图21B的第二候选节点列表114a上执行一AND合并操作，由此产生如所述实施例中的附图13B所示的第三候选节点列表116。

在执行步骤S46之后，所述搜索结果获取模块533在根据所述值搜索条件产生的第三候选节点列表中搜索其相关节点IDs彼此相一致的组合(步骤S47)。然后，所述搜索单元53将所述相互一致的相关节点IDs作为通过所述请求处理单元52来自客户20的所述搜索请求的搜索结果返回给客户20(步骤S48)。

如上描述的，在所述变体中，所述相关节点(父节点)的节点ID(相关节点IDs)被包含在保存于结构索引表格59a中的所述结构索引中。相应地，在所述变体中，用于覆盖符合所述结构条件的多个节点的值的值搜索以及用于搜索为多个节点所共有的一相关节点(父节点)的搜索处理可以仅仅通过查阅所述值索引表格58a和结构索引表格59a的索引操作来执行。即，在所述变体中，与所述实施例中一样，可以高速执行所述搜索处理而不搜索数据库42中所有XML文档。随着符合每个值搜索条件的节点数目的增加，该效果变得更加显著。

相反地，如果基于所述值索引表格58a找到的符合每个值搜索条件的节点的总数目很小，则利用与传统技术相似的搜索方法，即，实际搜索数据库42中存储的XML文档的方法，可以使得搜索以更高的速度执行。因此，在所述变体中，如果在步骤S62中确定候选节点的总数目(即，符合每个所述值搜索条件的节点的总数目)小于指定数目时，则所述搜索单元53a利用下面描述的与传统技术相似的搜索方法对所请求搜索的节点(相关节点)进行搜索。

首先，所述搜索单元53a的文档搜索模块535在存储于数据库42中的XML文档中搜索包含在为每个所述值搜索条件而获取的候选节点列表中的节点(步骤S63)。在步骤S63中，对于相应于所述值搜索条件的每个结构条件，所述文档搜索模块535从所述被搜索的XML文档中抽取符合所述结构条件的节点的节点IDs和该节点(符合所述结构条件的节点)的相关节点(父节点)的节点IDs(相关节点IDs)。在步骤S63，所述文档搜索模块535获取所述抽取节点的节点IDs和所述相关节点的节点IDs(相关节点IDs)的列表来作为第四候选节点列表。即，所述文档搜索模块535根据所述结构条件获取所述第四候选节点列表。

然后，所述搜索单元53a的搜索结果获取模块533在根据所述结构条件获取的所有第四候选节点列表之间搜索其相关节点IDs相互一致的组合(步骤S64)。然后，所述搜索结果获取模块533把为所述查得的组合所共有的相关节点ID作为通过所述请求处理单元52来自客户20的搜索请求的搜索结果返回给客户20(步骤S48)。如上所描述的，在所述变体中，由于根据候选节点的总数目自动应用了最佳搜索过程，因此能够实现最优处理性能。

如在所述实施例中一样，在所述变体中，在所述索引表格57中管理的节点(最后节点和第一节点)的相关节点的类型是父节点的情况是一前提条件。然而，在所述索引表格57中管理的所述节点(最后节点和第一节点)的相关节点的类型可以是与一父节点不同的节点。例如，当满足条件last＝”Stevens”和first＝”W.”的作者所写的一本书的标题被作为想要的搜索结果时，用户指定一伯父节点作为索引请求中的相关节点，使得适用于由所述用户使用的搜索条件的相关节点上的信息能够被包含于所述结构索引表格59a中。这使得即使所述搜索条件(搜索目标节点)改变时也有可能高速地执行搜索。

所述搜索单元53a本身可以查阅所述索引表格57、值索引表格58a和结构索引表格59a。相似地，在所述实施例中，所述搜索单元53本身可以查阅所述索引表格57、值索引表格58和结构索引表格59。进一步地，如在所述变体中一样，在所述实施例中，所述搜索单元53可以配备有所述节点数目确定模块534和文档搜索模块535。

对于本领域技术人员来说很容易发现其它优点和变体。因此，本发明的范围不限于此处所示例和描述的具体细节和代表性实施例。相应地，能够作出多种变体而不偏离由所附权利要求和其等同物所定义的总发明构思的精神和范围。