用于索引和搜索数据库的方法和装置转让专利
申请号 : CN200510092243.3
文献号 : CN1741017B
文献日 : 2010-05-26
发明人 : J-R·文 , 马维英
申请人 : 微软公司
摘要 :
搜索系统通过生成性地抽样数据库来为web数据库生成一个索引，并使用该索引来识别和设计搜索数据库的查询。该生成的索引被称为域-属性索引，并包含一个域级索引和多个站点级索引。用于数据库的站点级索引将站点属性映射到数据库中的确定属性值。用于域的域级索引将属性值映射到包含那些属性值的数据库和站点属性对。为某个域中的数据库生成站点级索引，所述搜索系统开始于那个域最初的一组抽样数据。该搜索系统基于抽样数据生成抽样查询并将该抽样查询提交给数据库。该搜索系统基于抽样结果更新站点级索引，并使用该结果来生成更多的抽样查询。
权利要求 :
1.一种在计算机系统中用来搜索Web数据库的方法，该方法包括：向包含属性和属性值的对的web数据库提供所述属性和属性值的对的映射，所述映射通过抽样该web数据库而生成；
接收具有项的非结构化查询；
从所述非结构化查询中识别为对应于web数据库属性的属性项的项；
从所述非结构化查询中识别为对应于web数据库属性值的属性值项的项；
对于每对所识别的属性项和所识别的属性值项，
用对应于设置到所识别的属性值项的属性项的属性来设计查询；以及当所述映射指示web数据库具有对应于用于设计该查询的所识别的属性项和所识别的属性值项的对的属性和属性值的对时，向所述web数据库提交设计的查询。
2.如权利要求1所述的方法，其中所述映射是域属性索引。
3.如权利要求2所述的方法，其中所述域属性索引为多个属性值提供从所述属性值到web数据库和到该web数据库的属性的映射，其中每个属性值被包含在一个web数据库的一个条目的至少一个属性中，所述web数据库在其条目属性中包含所述属性值。
4.如权利要求2所述的方法，其中所述域属性索引为每个web数据库和该web数据库中的每个属性，提供到确定的属性值的映射，所述确定的属性值包含在所述web数据库的条目属性中。
5.如权利要求2所述的方法，其中所述域属性索引包括域级索引和站点级索引，其中所述域级索引将属性值映射到包含这些属性值的数据库和站点属性对，所述站点级索引将站点属性映射到数据库中确定的属性值。
6.一种在计算机系统中用来搜索web数据库的方法，该方法包括：接收属性和属性值的对；
为每个接收的对设计查询；
识别web数据库以使用域属性索引提交设计的查询，所述域属性索引为多个属性值提供从所述属性值到web数据库和到该web数据库的属性的映射，每个属性值被包含在一个web数据库的一个条目的至少一个属性中，所述web数据库在其条目属性中包含所述属性值，所述映射通过抽样所述web数据库、向所述web数据库提交具有属性和属性值的对的各种组合的查询而生成；
向所识别的web数据库提交设计的查询。
7.如权利要求6所述的方法，其中所述域属性索引包括域级索引和站点级索引，其中所述域级索引将属性值映射到包含这些属性值的数据库和站点属性对，所述站点级索引将站点属性映射到数据库中确定的属性值。
8.一种在计算机系统中用来抽样域中的数据库的方法，该方法包括：为所述域的属性提供多组属性值；以及
为多个数据库的每一个抽样；
为从提供的多组属性值中选择的多个属性和属性值的对的每一个向数据库提交查询，该查询用该对中的属性值来查询该对中的属性，其中所提交的查询生成结果；和当该结果指示该数据库包含所提交的查询的属性和属性值的对时，在该数据库的属性和属性值之间生成映射。
9.如权利要求8所述的方法，包括基于所述结果，为所述域的属性更新所述多组属性值，以便在接下来提交查询时能够使用来自于已更新的组的属性值。
10.如权利要求8所述的方法，其中生成的映射为域属性索引。
11.如权利要求10所述的方法，其中所述域属性索引包括站点级索引，其中所述站点级索引将站点属性映射到数据库中确定的属性值。
12.如权利要求10所述的方法，其中所述域属性索引包括域级索引，其中所述域级索引将属性值映射到包含这些属性值的数据库和站点属性对。
13.如权利要求8所述的方法，其中选择具有最小数目的确定属性值的属性。
14.如权利要求8所述的方法，其中选择在未被选择的属性值中具有最大出现次数的属性值。
15.如权利要求8所述的方法，包括提供将域属性映射到数据库的数据库特定属性的对应表。
16.如权利要求15所述的方法，其中提交查询包括使用所述对应表来为域属性确定数据库的数据库特定属性，其中向该数据库提交该查询。
17.如权利要求15所述的方法，包括为将数据库的数据库特定属性映射到包含在该数据库中的属性值的每个数据库生成映射。
说明书 :
技术领域
所描述的技术通常涉及数据库搜索，尤其涉及web数据库搜索。
背景技术
全球网(“web”)提供了大量可通过网页访问的数据。网页可包含静态内容或动态内容。静态内容通常指通过网页的许多次访问能保持一样的信息。动态内容通常指存储在web数据库中并响应于搜索请求添加到网页上的信息。动态内容表示所谓的深web或隐藏的web。
许多搜索引擎服务允许用户查找web的静态内容。在用户提交了包括搜索项的搜索请求或查询之后，搜索引擎服务识别与那些搜索项相关的网页。这些网页是搜索结果。为了快速识别相关的网页，搜索引擎服务保持关键字到网页的映射。通过“爬”网产生该映射来识别每个网页的关键字。为了“爬”网，搜索引擎服务可使用根网页表来识别可通过那些根网页访问的所有网页。任何特定网页的关键字都可使用各种公知的信息检索技术来识别，比如识别标题的字、网页的元数据中提供的字、高亮的字等等。
然而，通常这些搜索引擎服务不能用来搜索动态内容，也认为动态内容是不可“爬”内容。搜索动态内容的一个问题在于有几个原因使得不能有效地检索和索引web数据库内容。一个原因是多个web数据库的内容太大了，以至于不能检索和索引。另一个原因是web数据库的计划隐藏在搜索界面后面，即只向用户陈列搜索网页(和结果网页)的属性。搜索动态内容的另一个问题在于，生成的索引需要支持结构性查询和非结构性查询。非结构性查询是在搜索文献时通常使用的搜索项列表。例如，一个非结构性查询可以是“Harry Potter Rowling”。一个结构性查询是在搜索数据库时通常使用的属性和属性值列表。例如，一个结构性查询可以是“title＝Harry Potter andauthor＝Rowling”
已经进行了相当多的研究来开发提供跨越多个web数据库搜索的“元搜索器”。当元搜索器收到一个查询时，它选择最有可能包含相关内容的web数据库，这被称为“源选择”。元搜索器接着将查询翻译成合适的格式，用于每个识别的web数据库，这被称为“查询翻译”。例如，元搜索器需要懂得如何将元搜索器查询的属性映射到每个选择的web数据库的站点属性。例如，元搜索器可使用名为“格式”的属性来查阅介质(例如，平装书或精装书)，而web数据库可使用名为“类型”的属性来查阅同一数据。查询翻译需要将元搜索器的格式属性映射到web数据库的类型属性。元搜索器将翻译的查询发送到选择的web数据库，这被称为“调度”。当元搜索器接收搜索结果时，它将它们整合为总的结果，这被称为“结果整合”。
期望有一种用来有效地生成web数据库索引的技术，该技术允许使用非结构性和结构性查询来有效地搜索。
许多搜索引擎服务允许用户查找web的静态内容。在用户提交了包括搜索项的搜索请求或查询之后，搜索引擎服务识别与那些搜索项相关的网页。这些网页是搜索结果。为了快速识别相关的网页，搜索引擎服务保持关键字到网页的映射。通过“爬”网产生该映射来识别每个网页的关键字。为了“爬”网，搜索引擎服务可使用根网页表来识别可通过那些根网页访问的所有网页。任何特定网页的关键字都可使用各种公知的信息检索技术来识别，比如识别标题的字、网页的元数据中提供的字、高亮的字等等。
然而，通常这些搜索引擎服务不能用来搜索动态内容，也认为动态内容是不可“爬”内容。搜索动态内容的一个问题在于有几个原因使得不能有效地检索和索引web数据库内容。一个原因是多个web数据库的内容太大了，以至于不能检索和索引。另一个原因是web数据库的计划隐藏在搜索界面后面，即只向用户陈列搜索网页(和结果网页)的属性。搜索动态内容的另一个问题在于，生成的索引需要支持结构性查询和非结构性查询。非结构性查询是在搜索文献时通常使用的搜索项列表。例如，一个非结构性查询可以是“Harry Potter Rowling”。一个结构性查询是在搜索数据库时通常使用的属性和属性值列表。例如，一个结构性查询可以是“title＝Harry Potter andauthor＝Rowling”
已经进行了相当多的研究来开发提供跨越多个web数据库搜索的“元搜索器”。当元搜索器收到一个查询时，它选择最有可能包含相关内容的web数据库，这被称为“源选择”。元搜索器接着将查询翻译成合适的格式，用于每个识别的web数据库，这被称为“查询翻译”。例如，元搜索器需要懂得如何将元搜索器查询的属性映射到每个选择的web数据库的站点属性。例如，元搜索器可使用名为“格式”的属性来查阅介质(例如，平装书或精装书)，而web数据库可使用名为“类型”的属性来查阅同一数据。查询翻译需要将元搜索器的格式属性映射到web数据库的类型属性。元搜索器将翻译的查询发送到选择的web数据库，这被称为“调度”。当元搜索器接收搜索结果时，它将它们整合为总的结果，这被称为“结果整合”。
期望有一种用来有效地生成web数据库索引的技术，该技术允许使用非结构性和结构性查询来有效地搜索。
发明内容
提供了一种用来在一个域中索引和搜索web数据库的方法和系统。在一个实施例中，搜索系统通过生成性地抽样数据库来为web数据库生成一个索引，并使用那个索引来识别和设计用来搜索数据库的查询。生成的索引被称为域级属性索引，并包含域级索引和用于每个数据库的站点级索引。用于数据库的站点级索引将站点属性映射到数据库中确定的属性值。用于域的域级索引将属性值映射到包含这些属性值的数据库和站点属性对。为某个域中的数据库生成站点级索引，所述搜索系统对那个域以最初的一组抽样数据开始。该搜索系统使用域-站点映射来选择与域属性相应的数据库站点属性。该搜索系统从抽样数据中为所述域属性选择一个属性值。该搜索系统接着生成并提交抽样查询至数据库以搜索在已选择站点属性方面匹配选择的属性值的条目。一旦收到作为查询结果的条目，搜索系统为所述数据库生成站点级索引，它将站点级属性映射到包含在那些站点属性之中确定的属性值。该搜索系统可以从各种站点级索引中生成域级索引。
在一个实施例中，在搜索多个数据库时，搜索系统允许用户规定非结构性查询或结构性查询。该搜索系统通过基于域级索引首先识别非结构性查询的项是否代表属性或属性值而将非结构性查询映射到一系列结构性查询。在识别了一组属性项和属性值项(term)之后，搜索系统为属性项和属性值项的每个组合生成一个查询。该搜索系统能够直接使用结构化查询的属性和属性值对，而不必执行与用于非结构化查询相似的映射。该搜索系统使用域级索引来识别查询应提交到哪个数据库。
在一个实施例中，在搜索多个数据库时，搜索系统允许用户规定非结构性查询或结构性查询。该搜索系统通过基于域级索引首先识别非结构性查询的项是否代表属性或属性值而将非结构性查询映射到一系列结构性查询。在识别了一组属性项和属性值项(term)之后，搜索系统为属性项和属性值项的每个组合生成一个查询。该搜索系统能够直接使用结构化查询的属性和属性值对，而不必执行与用于非结构化查询相似的映射。该搜索系统使用域级索引来识别查询应提交到哪个数据库。
附图说明
图1是说明一个实施例中的搜索系统组件的框图。
图2说明了一个实施例中的对应表。
图3说明了在一个实施例中用于域属性索引的站点级索引。
图4说明了在一个实施例中用于域属性索引的域级索引。
图5是说明在一个实施例中生成查询组件处理过程的流程图。
图6是说明在一个实施例中设计非结构化查询组件处理过程的流程图。
图7是说明在一个实施例中识别一个查询的属性项和属性值项的组件处理过程的流程图。
图8是说明在一个实施例中组件选择数据库来提交查询的处理过程的流程图。
图9是说明在一个实施例中生成域属性索引的组件处理过程的流程图。
图10是说明在一个实施例中更新站点级索引组件的处理过程的流程图。
图2说明了一个实施例中的对应表。
图3说明了在一个实施例中用于域属性索引的站点级索引。
图4说明了在一个实施例中用于域属性索引的域级索引。
图5是说明在一个实施例中生成查询组件处理过程的流程图。
图6是说明在一个实施例中设计非结构化查询组件处理过程的流程图。
图7是说明在一个实施例中识别一个查询的属性项和属性值项的组件处理过程的流程图。
图8是说明在一个实施例中组件选择数据库来提交查询的处理过程的流程图。
图9是说明在一个实施例中生成域属性索引的组件处理过程的流程图。
图10是说明在一个实施例中更新站点级索引组件的处理过程的流程图。
具体实施方式
提供一种用来索引和搜索web数据库的方法和装置。在一个实施例中，搜索系统通过生成性地抽样数据库来为web数据库生成一个索引，并使用该索引来识别和设计用来搜索数据库的查询。该生成的索引被称为域-属性索引，并包含一个域级索引和用于每个数据库的站点级索引。域是针对特定主题(例如，书或汽车)的数据库集合。每个域具有一个域规划(也被称为“全球规划”)，它定义了一组通常能在域数据库的规划中找到的域属性。例如，当域涉及到书时，域规划包括作者属性和书名属性，因为大多数书数据库具有那些属性。用于数据库的站点级索引将站点属性映射到数据库之中的确定的属性值。例如，如果数据库包含一个带有作者属性的项，作者属性具有属性值Tolkien，然后站点级索引将作者属性映射到Tolkien。搜索系统通过如下所述抽样数据库来生成站点级索引。域级索引将属性值映射到包含那些属性值的数据库和站点属性对。例如，域级索引将包括属性值Tolkien的项，该属性值项Tolkien被映射到包含Tolkien书籍项的数据库，并且还映射到那个数据库的作者属性。搜索系统可从站点级索引中生成域级索引。该域级索引是站点级索引的合并和转置形式。为了处理一个查询，搜索系统使用域-属性索引来选择应当搜索哪个数据库，并使用域-站点属性映射来将该查询翻译成适于每个选择的数据库的查询。随后搜索系统把翻译的查询提交到选择的数据库。搜索系统接着使用域-站点属性映射整合查询的结果以把结果从站点属性映射到域属性。
为特定域中的数据库生成站点级索引，所述搜索系统开始于对那个域最初的一组抽样数据。该抽样数据为域中的数据库提供抽样项。所述项为域规划的域属性提供属性值。例如，书籍域中的抽样数据可包含一个项和另一个项，所述第一项的书名属性设置成“Harry Potter and the Order ofthe Phoenix”且作者属性设置成“Rowling”，此外另一个项的书名属性设置成“The Fellowship ofthe Ring”且作者属性设置成Tolkien。为了抽样数据库，搜索系统使用域-站点映射来选择与域属性相应的数据库站点属性。搜索系统从抽样数据中为那个域属性选择一个属性值。搜索系统接着生成并提交抽样查询至数据库以搜索在选择的站点属性方面匹配于选择的属性值的项。例如，如果选择的站点属性是作者，且选择的属性值是Tolkien，则查询将搜索由Tolkien写的书的项。一旦收到作为查询结果的项，搜索系统为那个数据库生成站点级索引，它将站点级属性映射到包含在那些站点属性之中的确定的属性值。例如，结果可包括由Del Ray出版的Tolkien的书“Silmarillion”的项，由Houghton Mifflin出版的Tolkien的书“Roverandom”的项和由Houghton Mifflin出版的Tolkien的书“The Hobbit”的项。如果这样，那么站点级索引将把书名站点属性映射到词Silmarillion、Roverandom和Hobbit，并且各出版人的站点属性映射到词Del Ray、Houghton和Mifflin。搜索系统也跟踪每个属性值在抽样结果中出现的次数。例如，出现计数为2将与Houghton的属性值相关，因为它出现在这个抽样结果的两个项中。为了增加数据库的覆盖，即增加被表示在站点级索引中的项数，搜索系统使用抽样结果的数据来为那个数据库设计新的抽样查询。例如，该搜索系统用设置成Houghton的站点出版者属性来设计抽样查询，这将检索由HoughtonMifflin出版的书籍的所有项。该搜索系统接着将更新站点级索引，以便它“覆盖”数据库的所有Houghton Mifflin书籍，从而增加了数据库的覆盖。该搜索系统可使用那个抽样结果来进一步生成抽样查询。因此该搜索系统基于抽样搜索的以前的抽样结果，再生性地扩展了数据库的覆盖。
在一个实施例中，搜索系统从各种站点级索引中生成域级索引。该搜索系统为站点级索引中的每个确定的属性值添加一个域级索引项。例如，如果5个数据库具有Tolkien的书的项，那么域级索引将具有用于Tolkien的项，它带有至少5个子项，每个子项识别5个数据库之一和那个数据库的作者站点属性。当所述数据库之一包含书籍“J.R.R.Tolkien：Architect ofMiddle Earth：ABiography”的项时，用于Tolkien的域级索引项也包含用于那个数据库的子项，所述数据库识别书名站点属性。域级索引在每个子项中还包含频率信息，所述频率信息指示那个属性值在每个数据库中的频率。该搜索系统在选择数据库来提交查询时，可使用所述频率信息。在一个实施例中，该搜索系统可基于域属性划分或分段域级索引。例如，域级索引具有用于书名域属性的子索引，以及用于作者域属性的另一个子索引。每个子索引包括一个对于在数据库中的那个属性的每个确定属性值的项。子索引的使用通过允许搜索系统首先为结构式查询的属性选择适当的子索引而后选择包含属性值的项(包含了完全对应于该属性的子项)而便于翻译结构式查询，而不是首先选择属性值，而后还必须搜索相应于该属性的子项。
在一个实施例中，在搜索多个数据库时，搜索系统允许用户规定非结构性查询或结构性查询。该搜索系统通过基于域级索引首先识别非结构性查询的项是否代表属性或属性值而将非结构性查询映射到一系列结构性查询。例如，当用户想搜索作者Tolkien写的书时，非结构性查询可以是“书名作者Tolkien”。该搜索系统识别出书名项和作者项都是域属性，因为它们是域规划之中的属性名称。该搜索系统还识别出书名项、作者项和Tolkien项是属性值，因为它们是数据库之中的属性值。书名项和作者项可以是属性值，因为数据库之一具有书“1997Harvard Business School Core Collection：作者、书名和主题指南”的项。在识别了一组属性项和属性值项(term)之后，搜索系统为属性项和属性值项的每个组合生成一个查询。例如，该搜索系统将为具有书名、作者和Tolkien属性值的书名属性生成查询，并且为具有书名、作者和Tolkien属性值的作者属性生成查询。该搜索系统能够直接使用结构化查询的属性和属性值对，而不必执行与用于非结构化查询相似的映射。用非结构化查询或结构化查询，该搜索系统将域属性翻译成所选择数据库的站点属性。该搜索系统接着将那些查询提交给基于域属性索引选择的数据库，例如，已知它们具有与查询的属性和属性值相对应的条目。该搜索系统也基于域属性索引信息识别查询提交的顺序。例如，该搜索系统基于域属性是否指示它们可能会返回大量项(比如，频率数指示将返回的大量项)来决定对数据库排序。
因为数据库抽样将在数据库上加上较重的负担，搜索系统可使用各种技术，以确保以更少的抽样来实现数据库的更大覆盖。该搜索系统可使用各种抽样准则，包括随机抽样、属性自适应抽样和值自适应抽样。在使用随机抽样时，搜索系统随机地选择站点属性，并且为选择的属性随机选择还没有被选择的属性值。在使用属性自适应抽样时，搜索系统选择在数据库的所有属性中具有最小数目确定属性值的站点属性。该搜索系统接着为那个站点属性随机选择一个未使用过的属性值。在使用值自适应抽样时，该搜索系统选择具有最小数目确定属性值的站点属性(像属性自适应抽样一样)，但是为那个属性选择还没有被选择并且在所有还没有被选择的属性值中具有最大出现次数的属性值。在域属性索引中带有最小确定值数的属性在已抽样数据库中也可以具有小数目的确定值。即，在从该属性中平均一个值时，比从其它属性中的值更可能匹配大部分已抽样数据库项。同样，在域属性索引中更多出现的值在抽样数据库中也出现得更频繁。即，以更多出现的值来抽样数据库可检索更大部分数据库项。
在一个实施例中，搜索系统运用抽样停止准则来终止已抽样数据库的抽样。虽然可能彻底抽样数据库，但是这为数据库加上很重的负担，且数据库的web站点将把过度频繁访问数据库的用户关在外面。搜索系统可使用绝对抽样停止准则，该绝对抽样停止准则是基于最大数目查询或者最大时间。可替换地，搜索系统可使用相对抽样停止准则，该相对抽样停止准则是基于最后几个抽样查询的边界值，如同基于查询结果被添加到站点级索引的新内容的数量所指示的一样。该搜索系统可使用绝对和相对抽样停止准则的组合。例如，不管哪一个首先出现，该搜索系统可在1000个查询之后停止抽样，或者边界值在阈值以下时停止抽样。
图1是说明一个实施例中的搜索系统组件的框图。Web数据库101经由通信链路102连接到搜索系统110。该搜索系统包括一个生成查询组件111，设计结构化查询组件112，设计非结构化查询组件113，生成域属性索引组件114，查询选择组件115，更新站点级索引116和更新域级索引组件117。该搜索系统还包括域属性索引120，它包括域级索引121和对于每个数据库的站点级索引122。该搜索系统还包括对应表123。域级索引是一个值-属性索引，它将属性值映射到数据库和数据库之中的站点属性。站点级索引是属性-值索引，它将数据库的站点属性映射到它们的对应确定值。对应表将域属性映射到每个数据库的站点属性。本领域普通技术人员可以理解，由于站点属性被映射到域属性，反之亦然，无论何时某物映射到站点属性，它都可以直接或间接地通过域属性被映射，并且对于域属性相反。生成查询组件接收用户查询，判定该查询是结构化的还是非结构化的，并适当地调用设计结构化查询组件或者设计非结构化查询组件。设计结构化查询组件基于结构化查询的属性和属性值生成查询。设计非结构化查询组件识别查询的属性项和属性值项，并基于属性项和属性值项的组合生成查询。生成查询组件选择数据库并将查询提交到那些数据库。生成域属性索引组件控制域属性索引的生成，域属性索引包括域级索引和站点级索引。生成域属性索引组件调用查询选择组件来生成抽样数据库的查询。生成域属性索引组件调用更新站点级索引组件来为抽样的数据库更新站点级索引。生成域属性索引组件基于站点级索引的信息调用更新域级索引组件来更新域级索引。
在其上实现搜索系统的计算设备可包括中央处理单元，内存，输入设备(比如，键盘和指向设备)，输出设备(比如，显示设备)和存储设备(比如，磁盘驱动器)。内存和存储设备是包含实现搜索系统指令的计算机可读媒体。此外，可以经由诸如通信链路上的信号之类的数据传输介质存储或发射数据结构和消息结构。可使用各种通信链路，比如因特网、局域网、广域网或者点对点拨号连接。本领域普通技术人员可以理解还可以和除了web数据库之外数据库一起使用搜索系统。例如，所述数据库是不同组织(例如，公司或者政府实体)的数据库，这些数据库能够通过元搜索器搜索。
该搜索系统可以在各种操作环境中实现，各种操作环境包括个人计算机、服务器计算机、手持或便携式设备、多处理器系统、基于微处理器的系统、可编程消费电器、网络PC、微型计算机、大型计算机、包括任何上述系统或设备的分布式计算环境，等等。
该搜索系统应当在计算机可执行指令的通用环境中描述，比如由一个或多个计算机或其它设备执行的程序模块。程序模块通常包括例行程序、程序、对象、组件、数据结构等等，执行特定任务或实施特定抽象的数据类型。通常程序模块的功能性可如在各个实施例中所需要的那样组合或分配。本领域普通技术人员能够理解举例说明的数据结构仅仅是能够用来组织数据的数据结构抽样类型。
图2说明了一个实施例中的对应表。对应表200为(也被称为域-站点属性映射)将每个域属性201映射到每个数据库相应的站点属性。例如，对应表的行202指示作者域属性对应到第一数据库的作者站点属性和第二数据库的“au”站点属性。行203指示格式域属性对应到第一数据库的类型站点属性和第二数据库的格式站点属性。对应表的产生在美国专利申请号为--------，名为“用于Web数据库规划匹配的方法和装置”，于2004年5月14日提交的申请中描述，该申请通过参考合并于此。
图3说明了在一个实施例中用于域属性索引的站点级索引。站点级索引300包含一个Web站点数据库的每个站点属性的项。在本实例中，站点属性的项由表中的行表示。每个项包括对于那个站点属性在数据库内的每一确定值的子项。子项还指示在抽样数据库时被发现的属性值出现的频率或者数目。例如，作者站点属性的项具有Rowling属性值的子项和Tolkien属性值的另一个子项。书名站点属性的项包括魔术师属性值的子项和铃声属性值的子项。
图4说明了在一个实施例中用于域属性索引的域级索引。域级索引400包括一个对于在站点级索引中的每个确定属性值的项和将属性值映射到数据库和包含所述值的站点属性的子项。在本例中，项401对应于属性值Tolkien，并具有指示在第一数据库的书名站点属性、第一数据库的作者站点属性和第二数据库的书名站点属性中发现Tolkien属性值的子项。条目402对应于属性值Houghton，并具有指示是在第一数据库的出版者站点属性、第二数据库的出版者站点属性、第二数据库的作者站点属性和第二数据库的书名站点属性中发现Houghton属性值的子项。
图5是说明在一个实施例中生成查询组件的处理过程的流程图。该组件传递一个查询，该查询是结构化或者是非结构化的，并生成将提交到各种数据库的查询。在判决块501，如果传递的查询是结构化的，组件在块502继续，否则组件在块503继续。在块502，组件调用设计结构化查询组件来生成数据库的查询。在块503，组件调用设计非结构化查询组件而从非结构化查询设计查询。在块504，组件调用选择数据库组件来选择向其提交查询的数据库。该组件还将查询从域属性翻译成已选择数据库的站点属性。在块505，组件对数据库排序，以便以能够更快地生成最需要的结果的次序提交所述查询。例如，可根据哪个数据库具有与某个属性值相关的最多项来对数据库排序。该组件也可以通过逻辑“OR”组合属性和属性值来为数据库组合查询。组件随后结束。
图6是说明在一个实施例中设计非结构化查询组件的处理过程流程图。在块601，该组件调用一个组件，以从查询中识别属性项和属性值项。在块602-606，组件循环选择属性和属性值项对，并为该对设计一个查询。在块602，组件选择下一个属性项。在判决块603，如果已经选择了所有属性项，那么组件返回，否则组件继续到块604。在块604，组件选择下一个属性值项。在判决块605，如果已经选择了所有属性值项，那么组件循环到块602来选择下一个属性项，否则组件在块606继续。在块606，组件通过把与选择的属性项对应的域属性设置成已选择属性值项来设计一个查询。随后组件循环到块604选择下一个属性值项。
图7是说明在一个实施例中识别查询的属性项和属性值项的处理过程的流程图。在块701，组件将属性项列表和属性值项列表初始化为空。在块702-707，组件循环选择查询的每个项，并判定它是一个属性项还是一个属性值项，或者两者都是。在块702，组件选择查询的下一项。在判决块703，如果已经选择了查询的所有项，那么部件返回，否则组件在块704继续。在判决块704，如果选择的项是属性值项，那么组件在块705继续，否则该组件在块706继续。当该项在域级索引的项中时，该项是一个属性值项。在块705中，组件将选择的项添加到属性值项列表，然后在块706继续。在判决块706，如果选择项是属性，那么组件在块707继续，否则组件循环到块702来选择查询的下一项。当项在域级索引的项的任一个之内的子项中时，它是一个属性项。在块707，组件将选择的项添加到属性项列表，然后循环到块702以选择查询的下一项。
图8是说明在一个实施例中组件选择数据库来提交查询的处理过程的流程图。组件根据那个数据库是否在项的子项中来选择数据库，所述项是对于域级索引中的查询属性值的项。在块801，组件选择下一个设计的查询。在判决块802，如果已经选择了所有的查询，那么组件返回，否则组件在块803继续。在块803，组件在用于已选择查询的属性的项中选择一个子项。在判决块804，如果已经选择了所有这样的子项，那么组件循环到块801来选择下一个查询，否则组件在块805继续。在块805，组件为查询生成数据库、属性和属性值三元组，然后循环到块803来选择下一个子项。三元组指示将提交到数据库的查询。组件还将域属性翻译成数据库相应的站点属性。
图9是说明在一个实施例中生成域属性索引组件(component)的处理过程的流程图。在该实施例中，所述组件竭力为所有属性和属性值组合生成查询，并随机选择属性和属性值。块901-904可由实现不同抽样准则(例如，属性自适应抽样)和抽样停止准则的组件代替。在块901中，组件选择下一个域属性。在判决块902中，如果已经选择了所有的域属性，那么组件在块980继续，否则组件在903继续。在块903，组件选择下一个属性值。在判决块904，如果已经选择了所有属性值，那么组件在块901继续，否则组件在块905继续。在块905，组件根据选择的域属性(映射到相应的站点属性)和选择的属性值来提交抽样查询。在块906，组件提取抽样结果的项。例如，组件只提取前10个项或者其它数量的项。在块907，组件调用更新站点级索引组件来来为已抽样数据库更新站点级索引。该组件接着循环到块903来为已选择的域属性选择下一个属性值。在块908，组件基于已更新的站点级索引，调用更新域级索引来更新域级索引。
图10是说明在一个实施例中更新站点级索引组件的处理过程的流程图。该组件被传递抽样结果，选择抽样结果之中的每个属性和属性值对，此外还判定该对是否在站点级索引中。如果不在站点级索引中，该组件将所述对添加到索引中。否则，组件更新现有对的频率。在块1001，该组件选择抽样结果的下一项。在判决块1002，如果已经选择了所有条目，那么组件返回，否则组件在块1003继续。在块1003，组件选择已选择项的下一个属性。在判决块1004，如果已经选择了已选择项的所有属性，该组件循环到块1001来选择下一项，否则组件在块1005继续。在判决块1005，如果已选择属性及其属性值已经是在站点级索引中的一对，那么，组件在块1006继续，否则组件在块1007继续。在块1007，该组件将属性和属性值对添加到站点级索引，然后在块1006继续。在块1006，组件在站点级索引中更新属性和属性值对的频率，之后循环到块1003来为抽样结果的已选择项选择下一个属性。
本领域的普通技术人员将会理解，虽然为了举例说明的目的，在此已经描述了搜索系统的具体实施例，但是可以做出各种修改而不脱离本发明的精神和范围。因此，除了所附的权利要求之外，本发明不受限制。
为特定域中的数据库生成站点级索引，所述搜索系统开始于对那个域最初的一组抽样数据。该抽样数据为域中的数据库提供抽样项。所述项为域规划的域属性提供属性值。例如，书籍域中的抽样数据可包含一个项和另一个项，所述第一项的书名属性设置成“Harry Potter and the Order ofthe Phoenix”且作者属性设置成“Rowling”，此外另一个项的书名属性设置成“The Fellowship ofthe Ring”且作者属性设置成Tolkien。为了抽样数据库，搜索系统使用域-站点映射来选择与域属性相应的数据库站点属性。搜索系统从抽样数据中为那个域属性选择一个属性值。搜索系统接着生成并提交抽样查询至数据库以搜索在选择的站点属性方面匹配于选择的属性值的项。例如，如果选择的站点属性是作者，且选择的属性值是Tolkien，则查询将搜索由Tolkien写的书的项。一旦收到作为查询结果的项，搜索系统为那个数据库生成站点级索引，它将站点级属性映射到包含在那些站点属性之中的确定的属性值。例如，结果可包括由Del Ray出版的Tolkien的书“Silmarillion”的项，由Houghton Mifflin出版的Tolkien的书“Roverandom”的项和由Houghton Mifflin出版的Tolkien的书“The Hobbit”的项。如果这样，那么站点级索引将把书名站点属性映射到词Silmarillion、Roverandom和Hobbit，并且各出版人的站点属性映射到词Del Ray、Houghton和Mifflin。搜索系统也跟踪每个属性值在抽样结果中出现的次数。例如，出现计数为2将与Houghton的属性值相关，因为它出现在这个抽样结果的两个项中。为了增加数据库的覆盖，即增加被表示在站点级索引中的项数，搜索系统使用抽样结果的数据来为那个数据库设计新的抽样查询。例如，该搜索系统用设置成Houghton的站点出版者属性来设计抽样查询，这将检索由HoughtonMifflin出版的书籍的所有项。该搜索系统接着将更新站点级索引，以便它“覆盖”数据库的所有Houghton Mifflin书籍，从而增加了数据库的覆盖。该搜索系统可使用那个抽样结果来进一步生成抽样查询。因此该搜索系统基于抽样搜索的以前的抽样结果，再生性地扩展了数据库的覆盖。
在一个实施例中，搜索系统从各种站点级索引中生成域级索引。该搜索系统为站点级索引中的每个确定的属性值添加一个域级索引项。例如，如果5个数据库具有Tolkien的书的项，那么域级索引将具有用于Tolkien的项，它带有至少5个子项，每个子项识别5个数据库之一和那个数据库的作者站点属性。当所述数据库之一包含书籍“J.R.R.Tolkien：Architect ofMiddle Earth：ABiography”的项时，用于Tolkien的域级索引项也包含用于那个数据库的子项，所述数据库识别书名站点属性。域级索引在每个子项中还包含频率信息，所述频率信息指示那个属性值在每个数据库中的频率。该搜索系统在选择数据库来提交查询时，可使用所述频率信息。在一个实施例中，该搜索系统可基于域属性划分或分段域级索引。例如，域级索引具有用于书名域属性的子索引，以及用于作者域属性的另一个子索引。每个子索引包括一个对于在数据库中的那个属性的每个确定属性值的项。子索引的使用通过允许搜索系统首先为结构式查询的属性选择适当的子索引而后选择包含属性值的项(包含了完全对应于该属性的子项)而便于翻译结构式查询，而不是首先选择属性值，而后还必须搜索相应于该属性的子项。
在一个实施例中，在搜索多个数据库时，搜索系统允许用户规定非结构性查询或结构性查询。该搜索系统通过基于域级索引首先识别非结构性查询的项是否代表属性或属性值而将非结构性查询映射到一系列结构性查询。例如，当用户想搜索作者Tolkien写的书时，非结构性查询可以是“书名作者Tolkien”。该搜索系统识别出书名项和作者项都是域属性，因为它们是域规划之中的属性名称。该搜索系统还识别出书名项、作者项和Tolkien项是属性值，因为它们是数据库之中的属性值。书名项和作者项可以是属性值，因为数据库之一具有书“1997Harvard Business School Core Collection：作者、书名和主题指南”的项。在识别了一组属性项和属性值项(term)之后，搜索系统为属性项和属性值项的每个组合生成一个查询。例如，该搜索系统将为具有书名、作者和Tolkien属性值的书名属性生成查询，并且为具有书名、作者和Tolkien属性值的作者属性生成查询。该搜索系统能够直接使用结构化查询的属性和属性值对，而不必执行与用于非结构化查询相似的映射。用非结构化查询或结构化查询，该搜索系统将域属性翻译成所选择数据库的站点属性。该搜索系统接着将那些查询提交给基于域属性索引选择的数据库，例如，已知它们具有与查询的属性和属性值相对应的条目。该搜索系统也基于域属性索引信息识别查询提交的顺序。例如，该搜索系统基于域属性是否指示它们可能会返回大量项(比如，频率数指示将返回的大量项)来决定对数据库排序。
因为数据库抽样将在数据库上加上较重的负担，搜索系统可使用各种技术，以确保以更少的抽样来实现数据库的更大覆盖。该搜索系统可使用各种抽样准则，包括随机抽样、属性自适应抽样和值自适应抽样。在使用随机抽样时，搜索系统随机地选择站点属性，并且为选择的属性随机选择还没有被选择的属性值。在使用属性自适应抽样时，搜索系统选择在数据库的所有属性中具有最小数目确定属性值的站点属性。该搜索系统接着为那个站点属性随机选择一个未使用过的属性值。在使用值自适应抽样时，该搜索系统选择具有最小数目确定属性值的站点属性(像属性自适应抽样一样)，但是为那个属性选择还没有被选择并且在所有还没有被选择的属性值中具有最大出现次数的属性值。在域属性索引中带有最小确定值数的属性在已抽样数据库中也可以具有小数目的确定值。即，在从该属性中平均一个值时，比从其它属性中的值更可能匹配大部分已抽样数据库项。同样，在域属性索引中更多出现的值在抽样数据库中也出现得更频繁。即，以更多出现的值来抽样数据库可检索更大部分数据库项。
在一个实施例中，搜索系统运用抽样停止准则来终止已抽样数据库的抽样。虽然可能彻底抽样数据库，但是这为数据库加上很重的负担，且数据库的web站点将把过度频繁访问数据库的用户关在外面。搜索系统可使用绝对抽样停止准则，该绝对抽样停止准则是基于最大数目查询或者最大时间。可替换地，搜索系统可使用相对抽样停止准则，该相对抽样停止准则是基于最后几个抽样查询的边界值，如同基于查询结果被添加到站点级索引的新内容的数量所指示的一样。该搜索系统可使用绝对和相对抽样停止准则的组合。例如，不管哪一个首先出现，该搜索系统可在1000个查询之后停止抽样，或者边界值在阈值以下时停止抽样。
图1是说明一个实施例中的搜索系统组件的框图。Web数据库101经由通信链路102连接到搜索系统110。该搜索系统包括一个生成查询组件111，设计结构化查询组件112，设计非结构化查询组件113，生成域属性索引组件114，查询选择组件115，更新站点级索引116和更新域级索引组件117。该搜索系统还包括域属性索引120，它包括域级索引121和对于每个数据库的站点级索引122。该搜索系统还包括对应表123。域级索引是一个值-属性索引，它将属性值映射到数据库和数据库之中的站点属性。站点级索引是属性-值索引，它将数据库的站点属性映射到它们的对应确定值。对应表将域属性映射到每个数据库的站点属性。本领域普通技术人员可以理解，由于站点属性被映射到域属性，反之亦然，无论何时某物映射到站点属性，它都可以直接或间接地通过域属性被映射，并且对于域属性相反。生成查询组件接收用户查询，判定该查询是结构化的还是非结构化的，并适当地调用设计结构化查询组件或者设计非结构化查询组件。设计结构化查询组件基于结构化查询的属性和属性值生成查询。设计非结构化查询组件识别查询的属性项和属性值项，并基于属性项和属性值项的组合生成查询。生成查询组件选择数据库并将查询提交到那些数据库。生成域属性索引组件控制域属性索引的生成，域属性索引包括域级索引和站点级索引。生成域属性索引组件调用查询选择组件来生成抽样数据库的查询。生成域属性索引组件调用更新站点级索引组件来为抽样的数据库更新站点级索引。生成域属性索引组件基于站点级索引的信息调用更新域级索引组件来更新域级索引。
在其上实现搜索系统的计算设备可包括中央处理单元，内存，输入设备(比如，键盘和指向设备)，输出设备(比如，显示设备)和存储设备(比如，磁盘驱动器)。内存和存储设备是包含实现搜索系统指令的计算机可读媒体。此外，可以经由诸如通信链路上的信号之类的数据传输介质存储或发射数据结构和消息结构。可使用各种通信链路，比如因特网、局域网、广域网或者点对点拨号连接。本领域普通技术人员可以理解还可以和除了web数据库之外数据库一起使用搜索系统。例如，所述数据库是不同组织(例如，公司或者政府实体)的数据库，这些数据库能够通过元搜索器搜索。
该搜索系统可以在各种操作环境中实现，各种操作环境包括个人计算机、服务器计算机、手持或便携式设备、多处理器系统、基于微处理器的系统、可编程消费电器、网络PC、微型计算机、大型计算机、包括任何上述系统或设备的分布式计算环境，等等。
该搜索系统应当在计算机可执行指令的通用环境中描述，比如由一个或多个计算机或其它设备执行的程序模块。程序模块通常包括例行程序、程序、对象、组件、数据结构等等，执行特定任务或实施特定抽象的数据类型。通常程序模块的功能性可如在各个实施例中所需要的那样组合或分配。本领域普通技术人员能够理解举例说明的数据结构仅仅是能够用来组织数据的数据结构抽样类型。
图2说明了一个实施例中的对应表。对应表200为(也被称为域-站点属性映射)将每个域属性201映射到每个数据库相应的站点属性。例如，对应表的行202指示作者域属性对应到第一数据库的作者站点属性和第二数据库的“au”站点属性。行203指示格式域属性对应到第一数据库的类型站点属性和第二数据库的格式站点属性。对应表的产生在美国专利申请号为--------，名为“用于Web数据库规划匹配的方法和装置”，于2004年5月14日提交的申请中描述，该申请通过参考合并于此。
图3说明了在一个实施例中用于域属性索引的站点级索引。站点级索引300包含一个Web站点数据库的每个站点属性的项。在本实例中，站点属性的项由表中的行表示。每个项包括对于那个站点属性在数据库内的每一确定值的子项。子项还指示在抽样数据库时被发现的属性值出现的频率或者数目。例如，作者站点属性的项具有Rowling属性值的子项和Tolkien属性值的另一个子项。书名站点属性的项包括魔术师属性值的子项和铃声属性值的子项。
图4说明了在一个实施例中用于域属性索引的域级索引。域级索引400包括一个对于在站点级索引中的每个确定属性值的项和将属性值映射到数据库和包含所述值的站点属性的子项。在本例中，项401对应于属性值Tolkien，并具有指示在第一数据库的书名站点属性、第一数据库的作者站点属性和第二数据库的书名站点属性中发现Tolkien属性值的子项。条目402对应于属性值Houghton，并具有指示是在第一数据库的出版者站点属性、第二数据库的出版者站点属性、第二数据库的作者站点属性和第二数据库的书名站点属性中发现Houghton属性值的子项。
图5是说明在一个实施例中生成查询组件的处理过程的流程图。该组件传递一个查询，该查询是结构化或者是非结构化的，并生成将提交到各种数据库的查询。在判决块501，如果传递的查询是结构化的，组件在块502继续，否则组件在块503继续。在块502，组件调用设计结构化查询组件来生成数据库的查询。在块503，组件调用设计非结构化查询组件而从非结构化查询设计查询。在块504，组件调用选择数据库组件来选择向其提交查询的数据库。该组件还将查询从域属性翻译成已选择数据库的站点属性。在块505，组件对数据库排序，以便以能够更快地生成最需要的结果的次序提交所述查询。例如，可根据哪个数据库具有与某个属性值相关的最多项来对数据库排序。该组件也可以通过逻辑“OR”组合属性和属性值来为数据库组合查询。组件随后结束。
图6是说明在一个实施例中设计非结构化查询组件的处理过程流程图。在块601，该组件调用一个组件，以从查询中识别属性项和属性值项。在块602-606，组件循环选择属性和属性值项对，并为该对设计一个查询。在块602，组件选择下一个属性项。在判决块603，如果已经选择了所有属性项，那么组件返回，否则组件继续到块604。在块604，组件选择下一个属性值项。在判决块605，如果已经选择了所有属性值项，那么组件循环到块602来选择下一个属性项，否则组件在块606继续。在块606，组件通过把与选择的属性项对应的域属性设置成已选择属性值项来设计一个查询。随后组件循环到块604选择下一个属性值项。
图7是说明在一个实施例中识别查询的属性项和属性值项的处理过程的流程图。在块701，组件将属性项列表和属性值项列表初始化为空。在块702-707，组件循环选择查询的每个项，并判定它是一个属性项还是一个属性值项，或者两者都是。在块702，组件选择查询的下一项。在判决块703，如果已经选择了查询的所有项，那么部件返回，否则组件在块704继续。在判决块704，如果选择的项是属性值项，那么组件在块705继续，否则该组件在块706继续。当该项在域级索引的项中时，该项是一个属性值项。在块705中，组件将选择的项添加到属性值项列表，然后在块706继续。在判决块706，如果选择项是属性，那么组件在块707继续，否则组件循环到块702来选择查询的下一项。当项在域级索引的项的任一个之内的子项中时，它是一个属性项。在块707，组件将选择的项添加到属性项列表，然后循环到块702以选择查询的下一项。
图8是说明在一个实施例中组件选择数据库来提交查询的处理过程的流程图。组件根据那个数据库是否在项的子项中来选择数据库，所述项是对于域级索引中的查询属性值的项。在块801，组件选择下一个设计的查询。在判决块802，如果已经选择了所有的查询，那么组件返回，否则组件在块803继续。在块803，组件在用于已选择查询的属性的项中选择一个子项。在判决块804，如果已经选择了所有这样的子项，那么组件循环到块801来选择下一个查询，否则组件在块805继续。在块805，组件为查询生成数据库、属性和属性值三元组，然后循环到块803来选择下一个子项。三元组指示将提交到数据库的查询。组件还将域属性翻译成数据库相应的站点属性。
图9是说明在一个实施例中生成域属性索引组件(component)的处理过程的流程图。在该实施例中，所述组件竭力为所有属性和属性值组合生成查询，并随机选择属性和属性值。块901-904可由实现不同抽样准则(例如，属性自适应抽样)和抽样停止准则的组件代替。在块901中，组件选择下一个域属性。在判决块902中，如果已经选择了所有的域属性，那么组件在块980继续，否则组件在903继续。在块903，组件选择下一个属性值。在判决块904，如果已经选择了所有属性值，那么组件在块901继续，否则组件在块905继续。在块905，组件根据选择的域属性(映射到相应的站点属性)和选择的属性值来提交抽样查询。在块906，组件提取抽样结果的项。例如，组件只提取前10个项或者其它数量的项。在块907，组件调用更新站点级索引组件来来为已抽样数据库更新站点级索引。该组件接着循环到块903来为已选择的域属性选择下一个属性值。在块908，组件基于已更新的站点级索引，调用更新域级索引来更新域级索引。
图10是说明在一个实施例中更新站点级索引组件的处理过程的流程图。该组件被传递抽样结果，选择抽样结果之中的每个属性和属性值对，此外还判定该对是否在站点级索引中。如果不在站点级索引中，该组件将所述对添加到索引中。否则，组件更新现有对的频率。在块1001，该组件选择抽样结果的下一项。在判决块1002，如果已经选择了所有条目，那么组件返回，否则组件在块1003继续。在块1003，组件选择已选择项的下一个属性。在判决块1004，如果已经选择了已选择项的所有属性，该组件循环到块1001来选择下一项，否则组件在块1005继续。在判决块1005，如果已选择属性及其属性值已经是在站点级索引中的一对，那么，组件在块1006继续，否则组件在块1007继续。在块1007，该组件将属性和属性值对添加到站点级索引，然后在块1006继续。在块1006，组件在站点级索引中更新属性和属性值对的频率，之后循环到块1003来为抽样结果的已选择项选择下一个属性。
本领域的普通技术人员将会理解，虽然为了举例说明的目的，在此已经描述了搜索系统的具体实施例，但是可以做出各种修改而不脱离本发明的精神和范围。因此，除了所附的权利要求之外，本发明不受限制。