[發明專利]關系型數據庫和網狀數據結構相結合的關系路徑搜索方法

無效

• 申請號: 200910200123.9
• 申請日: 2009-12-08
• 公開（公告）號: CN101727479A
• 公開（公告）日: 2010-06-09
• 發明（設計）人: 張玉峰
• 申請（專利權）人: 張玉峰
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種搜索人際關系路徑的方法，特別涉及到對現有的關系型數據庫中SQL語句不擅長搜索人際關系路徑方法的改進。

背景技術

隨著現在各種社交網站、社交軟件及社交工具的興起，這些大型網站通常都有數千萬甚至數億的會員量，假設每個會員和其他100個會員有關聯關系(朋友、親戚、同事或其它關系)，這樣海量的數據構建的人際關系網是相當復雜的。挖掘其中會員間的關系路徑和關系圖(關系圖是關系路徑的集合)，可以增進人與人之間的信任，具有廣泛的意義。并且，依據“六度分割理論”會發現我們距離任何一個人的關系都不遠，可以增進社會和諧。

當A和B、C有關聯關系，C和D有關聯關系，如果我們想求解A和D之間的關系路徑，對于像這樣簡單的數據，很容易就得到路徑是A<->C<->D。然而，假設在一個數據庫中，任意一個節點和其它任意100個節點有關聯關系，當遍歷一個節點的第一層關系時，將遍歷100個節點，當遍歷一個節點的第二層關系時，將遍歷100X100＝10000個節點，依次類推，當遍歷第6層關系時，將遍歷10¹²個節點。依本技術領域人員的公職常識所知，當前絕大部分網站的數據都是保存在關系型數據庫中，而關系型數據庫是以表為基本數據結構的，其SQL語句并不擅長于此類關系路徑的搜索。本發明正是為求解海量數據(百萬級以上)庫中兩個節點的關聯關系路徑，以及山多條關系路徑組成關系圖。

發明內容

本發明的目的是實現一種關系型數據庫和網狀數據結構相結合的關系路徑搜索方法。突破了由于關系型數據庫的結構限制在關系路徑搜索上造成的效率低下問題。

為達到上述目的，實現一種關系型數據庫和網狀數據結構相結合的關系路徑搜索方法，分為4個步驟：

1)收集數據保存到關系型數據庫中。包括一個或者一個以上的保存用戶所有資料的關系型數據庫[101]，數據庫中的用戶ID字段是用戶會員(這里所指的會員，可以是個人、單位以及其它實體，被稱為一個節點)的唯一標示(不重復，能唯一標示一個用戶)，使用整型類型的數據，用戶的其它資料數據根據相應需求設置。為了突出主題，會員注冊資料、登錄、加好友等一般性步驟不在此贅述。

2)從關系型數據庫中抽取節點關系數據保存成網狀數據結構，并實時更新[104]。在內存或硬盤中創建一個用戶基本列表[201]，用戶基本列表[201]的索引號和用戶ID有一個簡單的對應關系，互相可以通過加上或減去一個常數計算所得，用戶基本列表[201]中保存的成員是用戶相應的關系列表句柄。讀取關系型數據庫中所有的用戶ID以及需要參加判斷的用戶其它數據，分別創建每個用戶的關系列表，并將關系列表的句柄存入用戶基本列表[201]的相應位置。用戶的關系列表中保存的是和此用戶有關聯關系的用戶ID。(如圖2所示)

3)在網狀數據結構的節點關系數據區中，搜索節點關系路徑[105]。需要請求路徑關系的應用程序(這里的應用程序可以是運行于前端應用服務器上的應用程序，也可以是運行于終端客戶端上的應用程序)把搜索條件發送至服務端，服務端接收到搜索條件[301]，先將源ID和目標ID組合成一個唯一的ID，然后根據這個組合ID和其它的輸入條件在關系路徑緩存區中搜索[302]。如果沒有找到，就依據輸入條件，在網狀數據結構的節點關系數據區中搜索關系路徑[305]，直到完成所有搜索，然后將搜索的結果和相關聯的條件保存至關系路徑緩存區[306]，以加速下一次的同類搜索。然后將搜索結果發送至請求客戶端[307]。(如圖3所示)

4)在關系型數據庫中使用SQL語句搜索關系路徑節點上的用戶的其它資料[106]，并組成呈現方式[107]。在接收到第(3)步搜索的結果之后，發送請求的應用程序可以根據搜索結果的關系路徑去關系型數據庫服務器上搜索路徑中成員的其它數據(比如：姓名、性別等)，然后根據這些信息以及關系路徑條數組成相應的呈現方式。比如：如果是一條關系路徑，可以呈現成條狀的由用戶姓名構建的路徑；如果是多條關系路徑，可以呈現成樹狀的、網狀的或者立體網狀的由用戶名稱構成的關系圖。呈現方式可以由美術人員依據需求進行設計，不局限于上述呈現方式。