唐雪飛，樊治強

（電子科技大學(xué) 信息與軟件工程學(xué)院，四川 成都 610054）

0 引 言

科學(xué)計算、數(shù)據(jù)倉庫以及工作流管理等應(yīng)用領(lǐng)域，都需要記錄數(shù)據(jù)的來源信息。來源信息除了原始數(shù)據(jù)以外，還包括數(shù)據(jù)的變換過程。例如，分子生物學(xué)領(lǐng)域的公共數(shù)據(jù)庫多達1 000 個，其中只有較少的數(shù)據(jù)庫存儲的是原始的實驗記錄，大部分?jǐn)?shù)據(jù)庫都是由其他數(shù)據(jù)庫經(jīng)過數(shù)據(jù)清洗、格式轉(zhuǎn)換以及數(shù)學(xué)運算等操作派生而來。在面對這類龐大復(fù)雜的數(shù)據(jù)時，如果無法知曉數(shù)據(jù)的來源和轉(zhuǎn)換過程，甚至無法判斷某些數(shù)據(jù)是原始數(shù)據(jù)還是轉(zhuǎn)換后的數(shù)據(jù)，那么這些數(shù)據(jù)將失去價值，因此，數(shù)據(jù)的來源信息的重要性不亞于數(shù)據(jù)本身。

數(shù)據(jù)血緣分析，又稱數(shù)據(jù)溯源（Data Provenance）和數(shù)據(jù)世系（Data Lineage），借助于數(shù)據(jù)血緣分析技術(shù)，可以追蹤數(shù)據(jù)的來源，評價數(shù)據(jù)的質(zhì)量和可靠性，復(fù)現(xiàn)數(shù)據(jù)的產(chǎn)生與轉(zhuǎn)換過程，當(dāng)發(fā)現(xiàn)數(shù)據(jù)質(zhì)量問題時，能夠高效地定位至錯誤產(chǎn)生的位置從而分析出錯誤的原因等。數(shù)據(jù)血緣分析技術(shù)的研究，無論對于科研領(lǐng)域還是商業(yè)生產(chǎn)領(lǐng)域，都具有重要的意義。

結(jié)構(gòu)化數(shù)據(jù)也稱作行數(shù)據(jù)，是由二維表結(jié)構(gòu)來邏輯表達和實現(xiàn)的數(shù)據(jù)，嚴(yán)格地遵循數(shù)據(jù)格式與長度規(guī)范，一般通過關(guān)系型數(shù)據(jù)庫進行存儲和管理。目前對于關(guān)系型數(shù)據(jù)庫中的數(shù)據(jù)血緣分析的研究，其中大多數(shù)都依賴于特定數(shù)據(jù)庫和相關(guān)查詢語言。本文提出一種基于標(biāo)注的方法，通過構(gòu)造并存儲關(guān)系表和字段的元數(shù)據(jù)映射關(guān)系，記錄關(guān)系表及其字段的血緣關(guān)系，從而給出針對特定表和字段的血緣分析算法描述。

1 關(guān)鍵概念

1.1 元數(shù)據(jù)

元數(shù)據(jù)被定義為“描述、解釋、定位或以其他方式使信息資源更容易檢索、使用或管理的結(jié)構(gòu)化信息”。針對分散于不同物理位置和不同業(yè)務(wù)系統(tǒng)中的數(shù)據(jù)庫業(yè)務(wù)表，可以使用元數(shù)據(jù)表metadata_table 對這些表的元數(shù)據(jù)信息進行統(tǒng)一記錄、管理和維護；對于數(shù)據(jù)庫表的列（字段），則使用另一張元數(shù)據(jù)表metadata_field 進行管理。每一張業(yè)務(wù)表在metadata_table 中都有其唯一標(biāo)識tid，每一個業(yè)務(wù)表中的字段在metadata_field 中也有其唯一標(biāo)識fid。

數(shù)據(jù)血緣信息也可以被認為是一種元數(shù)據(jù)，用來記錄數(shù)據(jù)產(chǎn)品的原始數(shù)據(jù)及其演變和轉(zhuǎn)換過程。關(guān)系型數(shù)據(jù)庫中的血緣分析可分為基于標(biāo)注和基于非標(biāo)注兩種方法，基于標(biāo)注的方法需要更多的存儲空間來記錄數(shù)據(jù)血緣信息，但是其查詢比較簡單；基于非標(biāo)注的方法不需要存儲數(shù)據(jù)演變和轉(zhuǎn)換過程的全部標(biāo)注信息，只需要使用少量的元數(shù)據(jù)信息，但這種方法需要存在已驗證的逆查詢機制或逆過程推導(dǎo)函數(shù)時才有效。本文采用一種基于標(biāo)注的方法，即通過構(gòu)造、存儲并分析元數(shù)據(jù)的映射關(guān)系，實現(xiàn)數(shù)據(jù)血緣分析。

1.2 映射關(guān)系

定義映射關(guān)系：a?>b。其表示表b 的數(shù)據(jù)是基于表a 的數(shù)據(jù)生成的，稱a 是b 的來源表，b 是a 的目標(biāo)表。

對于映射關(guān)系*：ta?>tb。其中表ta 有4 個字段分別為af1，af2，af3，af4；表tb 有4 個字段分別為bf1，bf2，bf3，bf4。其中bf1 來源于af1，bf2 來源于af2 和af3，bf3 和bf4 來源于af4。圖1 為映射關(guān)系*的圖形表示。

圖1 映射關(guān)系M*的示例

因此，映射關(guān)系可以用有向圖的形式展現(xiàn)，其中數(shù)據(jù)庫表用深色矩形塊表示，表的字段用白色矩形塊表示，塊之間的有向連接線（?。┍硎緮?shù)據(jù)流向。以上示例也說明：目標(biāo)表的某個字段可能來源于來源表的多個字段，來源表的某個字段也可能傳播至目標(biāo)表的多個字段。

本文使用一個關(guān)系表來存儲，表示表與表之間的映射關(guān)系，表名為mapping_relation，該表的主要字段如表1所示。

表1 表mapping_relation 的主要字段

在 表 mapping_relation 中，字 段 source_tid 和target_tid 的含義分別為來源表和目標(biāo)表在元數(shù)據(jù)表metadata_table 中的唯一標(biāo)識。創(chuàng)建映射關(guān)系M 的記錄即在表mapping_relation 中創(chuàng)建一個元組，該元組通過source_tid 和target_tid 兩個字段的值分別確定唯一的來源表和目標(biāo)表，因此，該元組也稱作一個元數(shù)據(jù)映射關(guān)系，在下文中簡稱為映射關(guān)系。字段field_relations 的值用以下JSON 格式存儲：

field_relations 用來記錄來源表和目標(biāo)表的字段映射關(guān)系，對于其中任意一組由花括號包裹的“屬性?值”對集合，屬性“source_fid”的值為來源表的某個字段在元數(shù)據(jù)表metadata_field 中的唯一標(biāo)識，屬性“target_fid”的值為目標(biāo)表的某個字段在元數(shù)據(jù)表metadata_field 中的唯一標(biāo)識。

對于具體應(yīng)用而言，創(chuàng)建映射關(guān)系可分為自動生成和手動設(shè)置兩種方式。映射關(guān)系的自動生成主要基于SQL 腳本的解析來完成：在SQL 編譯階段，對SQL 腳本進行語法、詞法分析，得到抽象語法樹（Abstract Syntax Tree，AST）；然后遍歷抽象語法樹的葉子節(jié)點及葉子節(jié)點中可能出現(xiàn)的子樹，通過分析得到映射關(guān)系。由于不同的關(guān)系型數(shù)據(jù)庫的SQL 語法不統(tǒng)一，且對于某些特定類型的SQL，如存儲過程，其存在變量定義、游標(biāo)操作和控制結(jié)構(gòu)等不在抽象語法樹的SQL 操作范圍內(nèi)，基于SQL 腳本解析的生成方式有可能會失敗，而手動設(shè)置映射關(guān)系則允許人為地創(chuàng)建和修改映射關(guān)系數(shù)據(jù)，彌補自動方式的不足之處，并提供對錯誤映射關(guān)系的修正途徑。

2 算法描述

數(shù)據(jù)質(zhì)量問題按粒度大小可分為表級、字段級和元組級，血緣分析的執(zhí)行粒度也應(yīng)以此劃分。由于映射關(guān)系是基于表和字段的，本節(jié)將闡述針對特定表和字段的血緣分析算法。

2.1 表級血緣分析

設(shè)待分析的產(chǎn)生數(shù)據(jù)質(zhì)量問題的表為t，表級血緣分析的主要思路是：分析第1 節(jié)所述映射關(guān)系表mapping_relation 中的映射關(guān)系數(shù)據(jù)，得到最終目標(biāo)表為t的所有映射關(guān)系的集合；然后以有向圖的方式展示t數(shù)據(jù)的來源（上游表）和流轉(zhuǎn)過程，以便數(shù)據(jù)分析人員快速定位和找到數(shù)據(jù)問題的原因。用算法1 描述表級血緣分析的具體步驟。

算法1：表級血緣分析

輸入：t在元數(shù)據(jù)表metadata_catalog 中的唯一標(biāo)識tid；

輸出：產(chǎn)生t的映射關(guān)系集合resultSet。

resultSet=null，tidQueue=null；

tidQueue.add（tid）；

while（tidQueue.isNotEmpty（））do

{

targetTid= tidQueue.remove（）；

relations=getRelationsByTargetTid（targetTid）；

{

resultSet.add（relations[]）；

tidQueue.add（relations[].targetTid）；

} //end for

} //end while

算法1 的核心是廣度優(yōu)先搜索（Breadth First Search，BFS）。首先初始化一個隊列tidQueue，用來存放未訪問過的上游表的id。 每次從tidQueue 彈出targetTid，使 用getRelationsByTargetTid 函 數(shù) 查 找 以targetTid 對應(yīng)的表為目標(biāo)表的映射關(guān)系集合relations。然后遍歷relations，將relations 的每個元素（一個上游映射關(guān)系）放入結(jié)果集resultSet 中，再將該映射關(guān)系的targetTid 加入tidQueue 中，直到while 循環(huán)結(jié)束。

3.1.4 蓖麻PIP5K蛋白跨膜結(jié)構(gòu)域的預(yù)測與分析 膜蛋白這種特殊的環(huán)境決定了跨膜區(qū)必須由強疏水的氨基酸組成，同時磷脂雙層的厚度又決定了膜蛋白的跨膜區(qū)一般大約由20個強疏水性的氨基酸組成[17]?？缒そY(jié)構(gòu)域的預(yù)測和分析，有利于正確認識和理解蛋白質(zhì)的結(jié)構(gòu)、功能、分類及在細胞中的功能部位。用CBS的TMHMM2.0對蓖麻PIP5K蛋白氨基酸序列的跨膜結(jié)構(gòu)域進行預(yù)測，結(jié)果如圖1-A所示。結(jié)果表明，7個PIP5Ks基因家族對應(yīng)的PIP5K蛋白跨膜結(jié)構(gòu)域均小于1，即均不存在跨膜結(jié)構(gòu)域，所有氨基酸均位于細胞膜表面。

圖2 為關(guān)于某張表tf 的表級血緣分析的結(jié)果示例，其中tf的上游表包括ta，tb，tc，td，te 五張表。

圖2 表級血緣分析結(jié)果

2.2 字段級血緣分析

第1 節(jié)中建立字段間映射關(guān)系的目的是實現(xiàn)字段級別細粒度的數(shù)據(jù)血緣分析。數(shù)據(jù)質(zhì)量檢測工具可依據(jù)規(guī)則將數(shù)據(jù)質(zhì)量問題定位到表的字段及元組（數(shù)據(jù)行）上。字段級血緣分析的意義在于：當(dāng)能確定一張表的數(shù)據(jù)質(zhì)量問題發(fā)生在哪些字段上時，找出對問題字段有影響的上游表和上游字段，以更快速、精確地定位分析問題產(chǎn)生的位置和原因。算法2 展示了字段級血緣分析的具體步驟。

算法2：字段級血緣分析

輸入：t在元數(shù)據(jù)表metadata_catalog 中的唯一標(biāo)識tid，f在元數(shù)據(jù)表metadata_field 中的唯一標(biāo)識fid；

輸出：對f有貢獻的映射關(guān)系集合resultSet，f的上游字段在元數(shù)據(jù)表metadata_field 中的唯一標(biāo)識的集合fidSet。

resultSet=null；fidSet=null；

traceField（tid，fid）；

//以下為traceField 函數(shù)定義

void traceField（targetTid，targetFids）{

relations=getRelationsByTargetTid（targetTid）；

for=1 to relations.length do

{

fieldRelations=relations[].fieldRelations；

recursionFlag=false；

tempFids=null；

for=1 to fieldRelations.length do

{

i（ftargetFids.cotains（fieldRelations[].targetFid））then

{

recursionFlag=true；

fidSet.add（fieldRelations[].sourceFid）；

tempFids.add（fieldRelations[].sourceFid）；

}

} //end for

i（frecursionFlag）then

{ relationResult.add（relations[]）；

traceField（relations[].sourceTid，tempFids）；

} } //end for }

算法2 結(jié)合了深度優(yōu)先搜索（Depth First Search，DFS）的思想，遞歸調(diào)用traceField 函數(shù)完成字段級血緣分析。traceField 函數(shù)的第1 個參數(shù)targetTid 的含義是待分析的目標(biāo)表的唯一標(biāo)識，第2 個參數(shù)targetFids 的含義是待分析的目標(biāo)字段的唯一標(biāo)識集合。在函數(shù)體內(nèi)，首先調(diào)用getRelationsByTargetTid 函數(shù)查找以targetTid對應(yīng)的表為目標(biāo)表的映射關(guān)系集合relations。對于relations 的每個元素relations[]，遍歷其包含的字段映射關(guān)系fieldRelations，判斷本次調(diào)用traceField 函數(shù)的參數(shù)targetFids 是否包含fieldRelations 中的targetFid，如果包含則代表當(dāng)前遍歷的映射關(guān)系relations[]中的來源表是t的 上 游 表，并 用tempFids 記 錄fieldRelations 中 與targetFids 對應(yīng)的所有sourceFid，和relations[].sourceTid一起作為下一次調(diào)用traceField 函數(shù)的參數(shù)。

圖3 為表tf 的字段ff2 的字段級血緣分析的結(jié)果示例，其中用實線表示的表tb，td 為字段ff2 的上游表，tb 的字段bf2，bf3 以及td 的字段df2 為ff2 的上游字段；ta，tc，te 雖然是tf 的上游表，但沒有對輸入字段ff2 產(chǎn)生貢獻，所以用虛線表示，表示它們并沒有被納入最終輸出。即字段級血緣分析算法根據(jù)字段映射關(guān)系對表級血緣分析的結(jié)果進行了約簡，只分析得到對輸入字段有貢獻的上游表及上游字段。

圖3 字段級血緣分析結(jié)果

3 結(jié) 語

本文提出的基于元數(shù)據(jù)映射關(guān)系的結(jié)構(gòu)化數(shù)據(jù)血緣分析方法，其價值在于：當(dāng)發(fā)現(xiàn)數(shù)據(jù)質(zhì)量問題時，可以通過分析關(guān)系表和字段的元數(shù)據(jù)映射關(guān)系追根溯源，快速地定位到問題數(shù)據(jù)的來源和加工過程，減少數(shù)據(jù)問題排查分析的時間和難度。本文所述的“血緣分析”一詞基于現(xiàn)有文獻的名詞定義，側(cè)重于指分析數(shù)據(jù)的來源，然而對于數(shù)據(jù)的綜合治理而言，除了獲取數(shù)據(jù)的來源信息以外，對于影響分析，即衡量數(shù)據(jù)在血緣關(guān)系網(wǎng)絡(luò)中的影響力、分析上游數(shù)據(jù)對下游數(shù)據(jù)的影響也有重要的研究價值和實踐意義。后續(xù)將重點研究數(shù)據(jù)血緣圖中的數(shù)據(jù)影響分析方法，并完善本文數(shù)據(jù)血緣分析方法的不足之處。