用於索引和搜索資料庫的方法和裝置的製作方法
2023-04-27 11:59:41 5
專利名稱：用於索引和搜索資料庫的方法和裝置的製作方法
技術領域：
所描述的技術通常涉及資料庫搜索，尤其涉及web資料庫搜索。
背景全球網(「web」)提供了大量可通過網頁訪問的數據。網頁可包含靜態內容或動態內容。靜態內容通常指通過網頁的許多次訪問能保持一樣的信息。動態內容通常指存儲在web資料庫中並響應於搜索請求添加到網頁上的信息。動態內容表示所謂的深web或隱藏的web。
許多搜尋引擎服務允許用戶查找web的靜態內容。在用戶提交了包括搜索項的搜索請求或查詢之後，搜尋引擎服務識別與那些搜索項相關的網頁。這些網頁是搜索結果。為了快速識別相關的網頁，搜尋引擎服務保持關鍵字到網頁的映射。通過「爬」網產生該映射來識別每個網頁的關鍵字。為了「爬」網，搜尋引擎服務可使用根網頁表來識別可通過那些根網頁訪問的所有網頁。任何特定網頁的關鍵字都可使用各種公知的信息檢索技術來識別，比如識別標題的字、網頁的元數據中提供的字、高亮的字等等。
然而，通常這些搜尋引擎服務不能用來搜索動態內容，也認為動態內容是不可「爬」內容。搜索動態內容的一個問題在於有幾個原因使得不能有效地檢索和索引web資料庫內容。一個原因是多個web資料庫的內容太大了，以至於不能檢索和索引。另一個原因是web資料庫的計劃隱藏在搜索界面後面，即只向用戶陳列搜索網頁(和結果網頁)的屬性。搜索動態內容的另一個問題在於，生成的索引需要支持結構性查詢和非結構性查詢。非結構性查詢是在搜索文獻時通常使用的搜索項列表。例如，一個非結構性查詢可以是「Harry PotterRowling」。一個結構性查詢是在搜索資料庫時通常使用的屬性和屬性值列表。例如，一個結構性查詢可以是「title＝Harry Potter and author＝Rowling」已經進行了相當多的研究來開發提供跨越多個web資料庫搜索的「元搜索器」。當元搜索器收到一個查詢時，它選擇最有可能包含相關內容的web資料庫，這被稱為「源選擇」。元搜索器接著將查詢翻譯成合適的格式，用於每個識別的web資料庫，這被稱為「查詢翻譯」。例如，元搜索器需要懂得如何將元搜索器查詢的屬性映射到每個選擇的web資料庫的站點屬性。例如，元搜索器可使用名為「格式」的屬性來查閱介質(例如，平裝書或精裝書)，而web資料庫可使用名為「類型」的屬性來查閱同一數據。查詢翻譯需要將元搜索器的格式屬性映射到web資料庫的類型屬性。元搜索器將翻譯的查詢發送到選擇的web資料庫，這被稱為「調度」。當元搜索器接收搜索結果時，它將它們整合為總的結果，這被稱為「結果整合」。
期望有一種用來有效地生成web資料庫索引的技術，該技術允許使用非結構性和結構性查詢來有效地搜索。
發明概述提供了一種用來在一個域中索引和搜索web資料庫的方法和系統。在一個實施例中，搜索系統通過生成性地抽樣資料庫來為web資料庫生成一個索引，並使用那個索引來識別和設計用來搜索資料庫的查詢。生成的索引被稱為域級屬性索引，並包含域級索引和用於每個資料庫的站點級索引。用於資料庫的站點級索引將站點屬性映射到資料庫中確定的屬性值。用於域的域級索引將屬性值映射到包含這些屬性值的資料庫和站點屬性對。為某個域中的資料庫生成站點級索引，所述搜索系統對那個域以最初的一組抽樣數據開始。該搜索系統使用域-站點映射來選擇與域屬性相應的資料庫站點屬性。該搜索系統從抽樣數據中為所述域屬性選擇一個屬性值。該搜索系統接著生成並提交抽樣查詢至資料庫以搜索在已選擇站點屬性方面匹配選擇的屬性值的條目。一旦收到作為查詢結果的條目，搜索系統為所述資料庫生成站點級索引，它將站點級屬性映射到包含在那些站點屬性之中確定的屬性值。該搜索系統可以從各種站點級索引中生成域級索引。
在一個實施例中，在搜索多個資料庫時，搜索系統允許用戶規定非結構性查詢或結構性查詢。該搜索系統通過基於域級索引首先識別非結構性查詢的項是否代表屬性或屬性值而將非結構性查詢映射到一系列結構性查詢。在識別了一組屬性項和屬性值項(term)之後，搜索系統為屬性項和屬性值項的每個組合生成一個查詢。該搜索系統能夠直接使用結構化查詢的屬性和屬性值對，而不必執行與用於非結構化查詢相似的映射。該搜索系統使用域級索引來識別查詢應提交到哪個資料庫。
附圖簡述
圖1是說明一個實施例中的搜索系統組件的框圖。
圖2說明了一個實施例中的對應表。
圖3說明了在一個實施例中用於域屬性索引的站點級索引。
圖4說明了在一個實施例中用於域屬性索引的域級索引。
圖5是說明在一個實施例中生成查詢組件處理過程的流程圖。
圖6是說明在一個實施例中設計非結構化查詢組件處理過程的流程圖。
圖7是說明在一個實施例中識別一個查詢的屬性項和屬性值項的組件處理過程的流程圖。
圖8是說明在一個實施例中組件選擇資料庫來提交查詢的處理過程的流程圖。
圖9是說明在一個實施例中生成域屬性索引的組件處理過程的流程圖。
圖10是說明在一個實施例中更新站點級索引組件的處理過程的流程圖。
詳細描述提供一種用來索引和搜索web資料庫的方法和裝置。在一個實施例中，搜索系統通過生成性地抽樣資料庫來為web資料庫生成一個索引，並使用該索引來識別和設計用來搜索資料庫的查詢。該生成的索引被稱為域-屬性索引，並包含一個域級索引和用於每個資料庫的站點級索引。域是針對特定主題(例如，書或汽車)的資料庫集合。每個域具有一個域規劃(也被稱為「全球規劃」)，它定義了一組通常能在域資料庫的規劃中找到的域屬性。例如，當域涉及到書時，域規劃包括作者屬性和書名屬性，因為大多數書資料庫具有那些屬性。用於資料庫的站點級索引將站點屬性映射到資料庫之中的確定的屬性值。例如，如果資料庫包含一個帶有作者屬性的項，作者屬性具有屬性值Tolkien，然後站點級索引將作者屬性映射到Tolkien。搜索系統通過如下所述抽樣資料庫來生成站點級索引。域級索引將屬性值映射到包含那些屬性值的資料庫和站點屬性對。例如，域級索引將包括屬性值Tolkien的項，該屬性值項Tolkien被映射到包含Tolkien書籍項的資料庫，並且還映射到那個資料庫的作者屬性。搜索系統可從站點級索引中生成域級索引。該域級索引是站點級索引的合併和轉置形式。為了處理一個查詢，搜索系統使用域-屬性索引來選擇應當搜索哪個資料庫，並使用域-站點屬性映射來將該查詢翻譯成適於每個選擇的資料庫的查詢。隨後搜索系統把翻譯的查詢提交到選擇的資料庫。搜索系統接著使用域-站點屬性映射整合查詢的結果以把結果從站點屬性映射到域屬性。
為特定域中的資料庫生成站點級索引，所述搜索系統開始於對那個域最初的一組抽樣數據。該抽樣數據為域中的資料庫提供抽樣項。所述項為域規劃的域屬性提供屬性值。例如，書籍域中的抽樣數據可包含一個項和另一個項，所述第一項的書名屬性設置成「Harry Potter and the Order of the Phoenix」且作者屬性設置成「Rowling」，此外另一個項的書名屬性設置成「The Fellowship of theRing」且作者屬性設置成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的站點出版者屬性來設計抽樣查詢，這將檢索由Houghton Mifflin出版的書籍的所有項。該搜索系統接著將更新站點級索引，以便它「覆蓋」資料庫的所有Houghton Mifflin書籍，從而增加了資料庫的覆蓋。該搜索系統可使用那個抽樣結果來進一步生成抽樣查詢。因此該搜索系統基於抽樣搜索的以前的抽樣結果，再生性地擴展了資料庫的覆蓋。
在一個實施例中，搜索系統從各種站點級索引中生成域級索引。該搜索系統為站點級索引中的每個確定的屬性值添加一個域級索引項。例如，如果5個資料庫具有Tolkien的書的項，那麼域級索引將具有用於Tolkien的項，它帶有至少5個子項，每個子項識別5個資料庫之一和那個資料庫的作者站點屬性。當所述資料庫之一包含書籍「J.R.R.TolkienArchitect of Middle EarthABiography」的項時，用於Tolkien的域級索引項也包含用於那個資料庫的子項，所述資料庫識別書名站點屬性。域級索引在每個子項中還包含頻率信息，所述頻率信息指示那個屬性值在每個資料庫中的頻率。該搜索系統在選擇資料庫來提交查詢時，可使用所述頻率信息。在一個實施例中，該搜索系統可基於域屬性劃分或分段域級索引。例如，域級索引具有用於書名域屬性的子索引，以及用於作者域屬性的另一個子索引。每個子索引包括一個對於在資料庫中的那個屬性的每個確定屬性值的項。子索引的使用通過允許搜索系統首先為結構式查詢的屬性選擇適當的子索引而後選擇包含屬性值的項(包含了完全對應於該屬性的子項)而便於翻譯結構式查詢，而不是首先選擇屬性值，而後還必須搜索相應於該屬性的子項。
在一個實施例中，在搜索多個資料庫時，搜索系統允許用戶規定非結構性查詢或結構性查詢。該搜索系統通過基於域級索引首先識別非結構性查詢的項是否代表屬性或屬性值而將非結構性查詢映射到一系列結構性查詢。例如，當用戶想搜索作者Tolkien寫的書時，非結構性查詢可以是「書名作者Tolkien」。該搜索系統識別出書名項和作者項都是域屬性，因為它們是域規劃之中的屬性名稱。該搜索系統還識別出書名項、作者項和Tolkien項是屬性值，因為它們是資料庫之中的屬性值。書名項和作者項可以是屬性值，因為資料庫之一具有書「1997 Harvard 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來為抽樣結果的已選擇項選擇下一個屬性。
本領域的普通技術人員將會理解，雖然為了舉例說明的目的，在此已經描述了搜索系統的具體實施例，但是可以做出各種修改而不脫離本發明的精神和範圍。因此，除了所附的權利要求之外，本發明不受限制。
權利要求
1.一種計算機可讀媒體，包括一個支持資料庫搜索的數據結構，該數據結構包含多個屬性值，每個屬性值被包含在一個資料庫的一個項的至少一個屬性中，從屬性值到資料庫和所述資料庫的屬性的映射，所述資料庫在其項屬性中包含了所述屬性值。
2.權利要求1所述的計算機可讀媒體，其中所述數據結構包括將域規劃的域屬性映射到資料庫的對應屬性的對應性信息。
3.權利要求1所述的計算機可讀媒體，其中對於每個資料庫和為該資料庫中的每個屬性，所述數據結構包括到確定的屬性值的映射，所述確定的屬性值包含在所述資料庫的一個項的屬性中。
4.權利要求3所述的計算機可讀媒體，其中每個到確定的屬性值的映射包括在所述資料庫的項屬性之中的屬性值的頻率指示。
5.權利要求1所述的計算機可讀媒體，其中資料庫是Web資料庫。
6.權利要求1所述的計算機可讀媒體，其中所述映射包括在所述資料庫的項屬性之中的屬性值出現頻率的指示。
7.權利要求1所述的計算機可讀媒體，其中所述映射基於屬性被隔開。
8.權利要求1所述的計算機可讀媒體，其中所述映射表示域屬性索引的屬等級。
9.權利要求8所述的計算機可讀媒體，其中所述數據結構對於每個資料庫包括一個站點級索引。
10.一種在計算機系統中用來搜索Web資料庫的方法，該方法包括接收一個具有項的非結構化查詢；識別屬性項為相應於web資料庫屬性的項；識別屬性值項為相應於web資料庫屬性值的項；對於屬性項和屬性值項對，用相應於設置到屬性值項的屬性項的屬性，設計一個查詢；以及向web資料庫提交設計的查詢。
11.權利要求10所述的方法，包括在提交設計的查詢之前，識別web資料庫的子集來提交設計的查詢。
12.權利要求10所述的方法，其中屬性項和屬性值項的識別使用域屬性索引。
13.權利要求12所述的方法，其中所述域屬性索引為多個屬性值提供了從屬性值到資料庫的映射和所述資料庫的屬性的映射，每個屬性值被包含在一個資料庫的一個項的至少一個屬性中，所述資料庫在其項屬性中包含了所述屬性值。
14.權利要求12所述的方法，其中所述域屬性索引為每個資料庫和該資料庫中的每個屬性，提供到確定的屬性值的映射，所述確定的屬性值包含在所述資料庫的一個項屬性中。
15.權利要求12所述的方法，其中所述域屬性索引包括域級索引和站點級索引。
16.在計算機系統中用來搜索web資料庫的方法，該方法包括接收屬性和屬性值對；為每個接收對設計一個查詢；識別web資料庫來使用域屬性索引提交設計的查詢；將設計的查詢提交到識別的web資料庫。
17.權利要求16所述的方法，其中域屬性索引為多個屬性值提供了從屬性值到資料庫的映射和所述資料庫的屬性的映射，每個屬性值被包含在一個資料庫的一個項的至少一個屬性中，所述資料庫在其項屬性中包含了所述屬性值。
18.權利要求16所述的方法，其中域屬性索引為每個資料庫和該資料庫中的每個屬性，提供到確定的屬性值的映射，所述確定的屬性值包含在所述資料庫的一個項屬性中。
19.權利要求16所述的方法，其中域屬性索引包括域級索引和站點級索引。
20.在計算機系統中用來抽樣在域中的資料庫的方法，該方法包括為域屬性提供多組屬性值；選擇一個資料庫來抽樣；為已選擇屬性選擇一個屬性和屬性值；向已選擇資料庫提交一個查詢，已選擇資料庫查詢具有已選擇屬性值的已選擇屬性，其中提交的查詢生成一個結果；和基於所述結果在已選擇資料庫的屬性和屬性值之間生成一個映射。
21.權利要求20所述的方法，包括基於所述結果，為域的屬性更新屬性值組，以便在接下來提交查詢時能夠使用來自於已更新組的屬性值。
22.權利要求20所述的方法，其中生成的映射為域屬性索引。
23.權利要求22所述的方法，其中生成的映射為站點級索引。
24.權利要求22所述的方法，其中生成的映射為域級索引。
25.權利要求20所述的方法，其中隨機選擇屬性和屬性值。
26.權利要求20所述的方法，其中選擇具有最小數目的確定屬性值的屬性。
27.權利要求20所述的方法，其中選擇在未被選擇的屬性值中具有最大出現次數的屬性值。
全文摘要
搜索系統通過生成性地抽樣資料庫來為web資料庫生成一個索引，並使用該索引來識別和設計搜索資料庫的查詢。該生成的索引被稱為域－屬性索引，並包含一個域級索引和多個站點級索引。用於資料庫的站點級索引將站點屬性映射到資料庫中的確定屬性值。用於域的域級索引將屬性值映射到包含那些屬性值的資料庫和站點屬性對。為某個域中的資料庫生成站點級索引，所述搜索系統開始於那個域最初的一組抽樣數據。該搜索系統基於抽樣數據生成抽樣查詢並將該抽樣查詢提交給資料庫。該搜索系統基於抽樣結果更新站點級索引，並使用該結果來生成更多的抽樣查詢。
文檔編號G06F17/30GK1741017SQ20051009224
公開日2006年3月1日 申請日期2005年5月16日 優先權日2004年5月14日
發明者J-R·文, 馬維英 申請人:微軟公司