一種數據表關聯方法及裝置製造方法
2023-12-07 06:31:01 2
一種數據表關聯方法及裝置製造方法
【專利摘要】本發明實施例提供一種數據表關聯方法及裝置，涉及網絡信息處理領域，能夠有效提高數據關聯分析的執行效率，實現數據關聯分析的準實時性。該方法包括：讀取分布式計算系統文件，根據數值關係分析中的等值條件以所述系統文件中任意兩個數據源各自的屬性值建立滿足所述等值條件的鍵值對，其中所述數據源中每條數據記錄與所述數據源各自的屬性值之間具有固定函數關係；將建立所述鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷，在所述兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄。本發明實施實例應用於數據表關聯處理。
【專利說明】一種數據表關聯方法及裝置
【技術領域】
[0001]本發明涉及網絡信息處理領域，尤其涉及一種數據表關聯方法及裝置。
【背景技術】
[0002]當今我們處在大數據時代，據統計人類每天產生的數據量超過
2.5quintilli0n(l(Tl8)字節，在過去兩年產生的數據量佔人類收集數據總量的90 %，而且隨著移動寬帶網絡、sensor network (傳感器網絡)、RFID (radio frequencyidentification devices,無線射頻識別)等技術的快速發展,人類產生數據的速度還在急速增長中。從海量數據中挖掘出有價值的信息，將數據轉變為信息，進而發掘其中存在的商業價值成為技術熱點，以幫助企業獲得商業成功。進行數據挖掘的海量數據通常來自於多個數據源，某些有價值的信息只有通過關聯分析隱藏在多個數據源間的關係才能獲得。在電信網絡中以信令分析為例，「信令風暴」是3G移動寬帶網絡面臨的一個具有挑戰性的問題。智慧型手機的快速普及是信令風暴產生的一個重要原因，表現為終端或業務心跳機制，弓丨發連接請求次數和尋呼次數的大幅度增加，進而造成尋呼成功率和EV-DO掉話率劣化。3G網絡中的信令分析希望通過將數據業務、終端類型等與信令消耗進行關聯分析，了解不同數據業務、終端類型對信令消耗的不同影響，從而了解信令風暴產生的原因，從而給運營商提供解決或處理建議。
[0003]在現有的技術中以底層的分布式文件系統HDFS (Hadoop Distributed FileSystem)通過Map-reduce (映射-線性相關)構架實現數據關聯的分析。通過Map-reduce針對多數據源的關聯，Hadoop的DataJoin (數據連接)機制實現如下:以A，B數據源(表)用於關聯的xl，yl作為映射的鍵值輸出，針對具有相同鍵值的A，B表，進行笛卡爾積，從中選擇滿足條件的結果作為關聯分析結果；從所有笛卡爾積的關聯組合中，選擇符合最優條件的記錄。如果假設A表和B表相同鍵值的表項各自有n，m個，則關聯階段的算法複雜度為0(n*m)。如果A表和B表相同key值的表項過多，則計算複雜度相當高，因此極大地影響了關聯分析的效率。
【發明內容】
[0004]本發明的實施例提供一種數據表關聯方法及裝置，能夠有效提高數據關聯分析的執行效率，實現數據關聯分析的準實時性。
[0005]為達到上述目的，本發明的實施例採用如下技術方案:
[0006]—方面，提供一種數據表關聯方法，包括:
[0007]讀取分布式計算系統文件，根據數值關係分析中的等值條件以所述系統文件中任意兩個數據源各自的屬性值建立滿足所述等值條件的鍵值對，其中所述數據源中每條數據記錄與所述數據源各自的屬性值之間具有固定函數關係；
[0008]將建立所述鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷，在所述兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄。
[0009]一方面，提供一種數據表關聯的裝置，包括:
[0010]至少一個映射器，用於讀取分布式計算系統文件，根據數值關係分析中的等值條件以所述系統文件中任意兩個數據源各自的屬性值建立滿足所述等值條件的鍵值對，其中所述數據源中每條數據記錄與所述數據源各自的屬性值之間具有固定函數關係；
[0011]至少一個遍歷器，用於將建立所述鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷，在所述兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄。
[0012]本發明的實施例提供一種數據表關聯方法及裝置，通過採用按順序遍歷的方法實現數據的關聯，能夠有效提高數據關聯分析的執行效率，實現數據關聯分析的準實時性。
【專利附圖】
【附圖說明】
[0013]為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。
[0014]圖1為本發明實施例提供的一種數據表關聯的方法流程示意圖；
[0015]圖2為本發明實施例提供的一種滿足性條件搜索方法示意圖；
[0016]圖3為本發明另一實施例提供的一種數據表關聯的方法流程示意圖；
[0017]圖4為本發明實施例提供的一種數據表關聯裝置示意圖；
[0018]圖5為本發明另一實施例提供的一種數據表關聯裝置示意圖；
[0019]圖6為本發明又一實施例提供的一種數據表關聯裝置示意圖。
【具體實施方式】
[0020]下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
[0021]參照圖1所示，為本發明實施實例提供的數據表關聯方法，包括以下步驟:
[0022]S101、讀取分布式計算系統文件，根據數值關係分析中的等值條件以系統文件中任意兩個數據源各自的屬性值建立滿足等值條件的鍵值對，其中數據源中每條數據記錄與數據源各自的屬性值之間具有固定函數關係；
[0023]這裡在SlOl中，以A、B兩個數據源(數據表)為例，以數值關係分析中的等值條件(A.xl = B.yl)作為A、B兩個數據源滿足的等值條件，其中xl和yl分別為數據源A、B的屬性值，以屬性值xl和yl作為滿足上述的等值條件的鍵值對輸出。此外，A、B兩個數據源中的每條數據記錄分別與A、B之間存在固定的函數關係，這裡以分別以A、B各自的屬性值
為變量，則有數據源A中的數據記錄與A中的屬性值的函數關係表示為f (xl，x2，......)，
數據源B中的數據記錄與B中的屬性值的函數關係表示為g(yl，y2，......)，為了代表普
遍的實用性，一個數據源中可能包含多個屬性值，其中函數關係f(xl，x2，......)和g(yl，y2，......)中同時示出多個可用作A、B數據元之間建立鍵值對的屬性值。
[0024]S102、將建立鍵值對的任意兩個數據源的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷，在兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄。
[0025]進一步可選的，步驟S102中將建立鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷包括:首先，將建立鍵值對的任意兩個數據源中具有相同鍵值的數據記錄分別按照各自滿足的固定函數關係進行排序；其次，將排序後生成的不同序列分別進行遍歷。
[0026]以下只是以xl和yl作為滿足上述的等值條件的鍵值對為例進行說明，對A和B表分別按照各自的函數關係f(X 1，χ2，...)和g(yl，y2，...)排序後進行遍歷。接下來為每一個A表中的記錄，在B表中尋找一個尋找滿足最優條件(MIN/MAX(f(xl，x2,...)-g(yl，12，...))的記錄，當然這裡的最優條件只是以獲取函數關係f(xl，x2,...)和g(yl，y2，...)的差值的最大或最小值為例，當然該最優條件可以根據需求通過函數關係f (xl，x2，...)和g(yl，y2,...)進行調整。由於兩個序列已經排序，因此，只需要對排序的兩個序列執行一次順序遍歷，即可完成A和B表的關聯。這裡假設A數據源中的數據記錄按照函數關係f(xl，x2,...)的順序為all、al2、al3、al4，B數據源中的數據記錄按照函數關係 g(yl, y2,...)的順序為 bll、bl2、bl3,則因為如果 f (al.xl, al.x2, al.x3...)-g(bl.yl, bl.y2, bl.y3...)小於 | f (al.xl, al.x2, al.χ3...) -g(b2.yl, b2.y2, b2.y3...) | ,則b3及其往下的f (xl, x2,...)和g(yl, y2,...)函數之差只能越來越大。
[0027]此時，假設具有相同鍵值對的A和B數據源中的數據記錄長度為m，n，則對兩個序列進行排序的算法複雜度為0(lOg2m+lOg2n)，而對已排序的A和B表進行一次順序遍歷的算法複雜度為0(m+n),相比較現有技術Hadoop的DataJoin機制的算法複雜度0(m*n),在算法執行效率上有了很大的提高。
[0028]本發明實施例提供的數據表關聯方法，能夠有效提高數據關聯分析的執行效率，實現數據關聯分析的準實時性。
[0029]進一步的,參照圖1所示，該方法還包括:
[0030]S103，在兩個數據源中按照最優條件的順序搜索兩個數據源各自固定函數關係之間符合滿足性條件的數據記錄。
[0031]這裡參照圖2所示的滿足性條件搜索示意圖，根據以上實施例提供的數據表關聯方法，為數據源A中的記錄Al，找到滿足等值條件和最優條件的數據源B中的記錄Bi。檢測記錄Al和記錄Bi是否符合滿足性條件，如果條件滿足，則表述已經找到了同時滿足等值條件、最優條件和滿足性條件的記錄，停止繼續搜索。否則，則從B表中的當前位置向前、向後對各條記錄逐一搜索，並保證搜索記錄的順序是按照最優化ΜΙΝ/MAX {f (xl,x2...)-g(yl,y2...順序，直到找到第一個符合滿足性條件的記錄，則該記錄即為滿足等值條件、滿足性條件及最優條件的記錄。在最壞情況下，對於A中的所有記錄，需要遍歷B表中的每一條記錄，此時算法複雜度為0(m*n),這時與Hadoop的Datajoin的複雜度相同。若對於A中的記錄，B中需要平均遍歷的次數為C，則算法複雜度為0(C*m)。這裡滿足性條件也是f (xl，
x2,......)和g(yl，y2，......)之間滿足的自定義的特殊關係，因此滿足性條件可以為多個。[0032]在實際問題中，最優化條件與滿足性條件常常是相關的，很多情況下，符合最優化條件的記錄也傾向於符合滿足性條件，這樣搜索到忽略滿足性條件但符合最優化條件的記錄或附近記錄也較容易符合了滿足性條件，因此平均遍歷次數c << |b|，因此算法複雜度相比現有技術會較小。
[0033]可選的，參照圖3所示，本發明另一實施例提供的一種數據表關聯方法，包括以下步驟:
[0034]S301、讀取分布式計算系統文件，根據數值關係分析中的等值條件以系統文件中任意兩個數據源各自的屬性值建立滿足等值條件的鍵值對，其中數據源中每條數據記錄與數據源各自的屬性值之間具有固定函數關係；
[0035]該步驟的【具體實施方式】可參照上一實施例中SlOl這裡不再贅述。
[0036]S302、將建立鍵值對的任意兩個數據源中具有相同鍵值的數據記錄分別按照各自滿足的固定函數關係進行排序。
[0037]在實施例一中是分別針對A、B數據源中具有相同鍵值對的數據記錄進行排序。當然這裡可以統一的對A、B數據源中的數據記錄按照鍵值進行排序，具有相同鍵值對的數據記錄將會被輸出到同一個序列中。這裡的排序過程可以為同時按照鍵值和數據源固有的函數關係進行排序，即對相同鍵值的數據記錄按照數據源固有的函數關係進行排序，記為:A表按照, B 表按照進行排序。
[0038]S303、將建立鍵值對的任意兩個數據源的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷，在兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄。
[0039]同樣，這裡只需要對具有相同鍵值(A為xl，B為yl)並且已經按照f(xl，x2，...)和g(yl，y2,...)排好序的序列，進行一次順序遍歷，即可完成數據關聯分析。在實現排序過程並不會引起額外的計算複雜度。這樣，關聯分析的算法複雜度為O(m+n)。具體遍歷的過程可以參照上一實施例步驟S102，這裡不再贅述。
[0040]本發明實施例提供的數據表關聯方法，能夠有效提高數據關聯分析的執行效率，實現數據關聯分析的準實時性。
[0041]進一步，可選的參照圖3所示，該方法還包括:
[0042]S304、在兩個數據源中按照最優條件的順序搜索兩個數據源各自固定函數關係之間符合滿足性條件的數據記錄。
[0043]該步驟的【具體實施方式】可參照上一實施例中S103這裡不再贅述。
[0044]以上本發明的實施例中抽象成的一般性問題具有普遍性，以上實施例中的方法可以直接應用到3G網絡中信令日誌和數據流的關聯分析。其中，信令日誌信息是從RNC設備的日誌記錄中獲得的，而數據流則在GGSN處採集得到。其中，BS (Base station orNodeB,基站)、RNC(Radio Network Controller,無線網絡控制器)、SGSN(Serving GeneralPacket Radio Service Support Node,通用無線分組服務支持節點)及 GGSN(GatewayGPRS Support Node,網關通用無線分組服務支持節點)構成了 3G網絡的基本架構。
[0045]其中數據和信令的關聯策略如下表所示:
[0046]
【權利要求】
1.一種數據表關聯方法，其特徵在於，包括: 讀取分布式計算系統文件，根據數值關係分析中的等值條件以所述系統文件中任意兩個數據源各自的屬性值建立滿足所述等值條件的鍵值對，其中所述數據源中每條數據記錄與所述數據源各自的屬性值之間具有固定函數關係； 將建立所述鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷，在所述兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄。
2.根據權利要求1所述的方法，其特徵在於，所述將建立所述鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷包括: 將建立所述鍵值對的任意兩個數據源中具有相同鍵值的數據記錄分別按照各自滿足的固定函數關係進行排序； 將排序後生成的不同序列分別進行遍歷。
3.根據權利要求1所述的方法，其特徵在於，所述將建立所述鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷前，還包括: 將建立所述鍵值對的任意兩個數據源中具有相同鍵值的數據記錄分別按照各自滿足的固定函數關係進行排序。
4.根據權利要求1?3任一項所述的方法，其特徵在於，所述在所述兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄之後，還包括: 在所述兩個數據源中按照所述最優條件的順序搜索所述兩個數據源各自固定函數關係之間符合滿足性條件的數據記錄。
5.一種數據表關聯裝置，其特徵在於，包括: 至少一個映射器，用於讀取分布式計算系統文件，根據數值關係分析中的等值條件以所述系統文件中任意兩個數據源各自的屬性值建立滿足所述等值條件的鍵值對，其中所述數據源中每條數據記錄與所述數據源各自的屬性值之間具有固定函數關係； 至少一個遍歷器，用於將建立所述鍵值對的任意兩個數據源中的數據記錄分別按照各自滿足的固定函數關係提供的順序進行遍歷，在所述兩個數據源中找到各自固定函數關係之間滿足最優條件的數據記錄。
6.根據權利要求5所述的裝置，其特徵在於，所述遍歷器包括: 洗牌模塊，用於將建立所述鍵值對的任意兩個數據源中具有相同鍵值的數據記錄分別按照各自滿足的固定函數關係進行排序； 遍歷模塊，用於將排序後生成的不同序列分別進行遍歷。
7.根據權利要求5所述的裝置，其特徵在於，所述裝置還包括: 洗牌器，用於將建立所述鍵值對的任意兩個數據源中具有相同鍵值的數據記錄分別按照各自滿足的固定函數關係進行排序。
8.根據權利要求5?7任一項所述裝置，其特徵在於，所述遍歷器還用於在所述兩個數據源中按照所述最優條件的順序搜索所述兩個數據源各自固定函數關係之間符合滿足性條件的數據記錄。
【文檔編號】G06F17/30GK103488657SQ201210196712
【公開日】2014年1月1日 申請日期:2012年6月14日 優先權日:2012年6月14日
【發明者】溫嘉佳, 何秀強, 潘璐伽 申請人:華為技術有限公司