基于元數(shù)據(jù)映射關(guān)系的結(jié)構(gòu)化數(shù)據(jù)血緣分析方法

唐雪飛，樊治強(qiáng)

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

0 引 言

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

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

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

1 關(guān)鍵概念

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

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

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

1.2 映射關(guān)系

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

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

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

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

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

表1 表mapping_relation 的主要字段

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

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

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

2 算法描述

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

2.1 表級(jí)血緣分析

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

算法1：表級(jí)血緣分析

輸入：t在元數(shù)據(jù)表metadata_catalog 中的唯一標(biāo)識(shí)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）。首先初始化一個(gè)隊(duì)列tidQueue，用來(lái)存放未訪問(wèn)過(guò)的上游表的id。 每次從tidQueue 彈出targetTid，使 用getRelationsByTargetTid 函 數(shù) 查 找 以targetTid 對(duì)應(yīng)的表為目標(biāo)表的映射關(guān)系集合relations。然后遍歷relations，將relations 的每個(gè)元素（一個(gè)上游映射關(guān)系）放入結(jié)果集resultSet 中，再將該映射關(guān)系的targetTid 加入tidQueue 中，直到while 循環(huán)結(jié)束。

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

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

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

2.2 字段級(jí)血緣分析

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

算法2：字段級(jí)血緣分析

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

輸出：對(duì)f有貢獻(xiàn)的映射關(guān)系集合resultSet，f的上游字段在元數(shù)據(jù)表metadata_field 中的唯一標(biāo)識(shí)的集合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ù)完成字段級(jí)血緣分析。traceField 函數(shù)的第1 個(gè)參數(shù)targetTid 的含義是待分析的目標(biāo)表的唯一標(biāo)識(shí)，第2 個(gè)參數(shù)targetFids 的含義是待分析的目標(biāo)字段的唯一標(biāo)識(shí)集合。在函數(shù)體內(nèi)，首先調(diào)用getRelationsByTargetTid 函數(shù)查找以targetTid對(duì)應(yīng)的表為目標(biāo)表的映射關(guān)系集合relations。對(duì)于relations 的每個(gè)元素relations[]，遍歷其包含的字段映射關(guān)系fieldRelations，判斷本次調(diào)用traceField 函數(shù)的參數(shù)targetFids 是否包含fieldRelations 中的targetFid，如果包含則代表當(dāng)前遍歷的映射關(guān)系relations[]中的來(lái)源表是t的 上 游 表，并 用tempFids 記 錄fieldRelations 中 與targetFids 對(duì)應(yīng)的所有sourceFid，和relations[].sourceTid一起作為下一次調(diào)用traceField 函數(shù)的參數(shù)。

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

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

3 結(jié) 語(yǔ)

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