投影運算對數據庫數據質量的傳遞影響研究

摘 要：針對在關系代數運算下數據質量傳遞影響問題，在屬性粒度給出了一個數據質量評價模型，定義了正確性評價指標。通過分析量化前后屬性錯誤率對質量評價的不同含義和作用，在數據錯誤隨機分布的假設前提下，證明了兩種錯誤率之間的定量關系；并研究了投影運算對正確性評價指標的質量傳遞影響，定量地給出了傳遞關系，分別對用量化前后屬性錯誤率進行了表示。

關鍵詞：數據庫； 數據質量； 質量傳遞； 關系代數; 投影運算； 正確性

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2008)09275103

Data quality propagation of projection operation for relational database

CHEN Weidong， ZHANG Weiming

(College ofInformation System Management， National University of Defense Technology， Changsha 410073， China)

Abstract:The paper presented a data quality model at attribute level， and defined the accuracy metric. After analysising the difference of error rate before and after quantification， and with the assumption of random errors occurrence， the quantities relationship between them was presented. The paper also discussed the quality propagation of project operation， and represented the propagation formula with error rate before and after quantization separately.

Key words：database; data quality; quality propagation; relation algebra; projection; accuracy

0 引言

隨著信息技術的廣泛應用，數據更多地由計算機采集、處理和存儲。由于數據量越積越多，信息系統越來越復雜，數據質量問題變得越來越突出，并正在對組織的正確決策起著越來越重要的作用。信息系統中的數據質量問題不是單純的質量問題，還涉及到數據存儲、數據集成、數據分發、數據檢索和使用等諸多方面，數據質量問題變得更為復雜。這促使人們從多方面對數據質量進行更為廣泛和深入的研究。

數據質量的核心問題之一是如何進行科學、有效的評價。通常對數據質量的評價采取直接方式進行，即針對全集數據（如所有員工的基本信息數據），采用適當方法得到評價結果。顯然，這種方式容易理解、方法多樣，也相對較成熟。然而，這種評價方式存在兩方面問題： a）對數據全集的直接評價一般不能表達用戶的要求。事實上，用戶得到的數據是通過信息系統（軟件）經過加工處理后的關于全集數據的一幅或多幅視圖，通常僅僅是全部數據中的一個組成部分。用戶關于數據的質量感受、需求和評價必然由這部分數據來反映，而不是全體數據。因此，全局數據的質量評價對用戶而言是間接的，而非直接的。根據數據質量符合使用者使用（fit for use）的程度這個廣為接受的定義^[1，2]，可以看出，與使用者密切相關的部分數據的質量決定了數據符合使用者要求的程度，因此，兩者相比后者更重要，更能反映用戶的質量訴求。

b）經過加工處理后數據的質量與原始數據的質量相比未必一定呈線性關系。一般，直覺上認為，如果知道全集數據的質量，則部分質量與全局質量可以認為相差不多或者是無差別的。這種直覺忽略了數據加工處理過程帶來的影響。事實上，對于關系數據庫，經過一個或多個SQL語句處理的結果集的質量與原數據集質量兩者之間可能存在較大的差異。在理論上可以證明，某些關系代數運算將使數據質量在運算前后產生較大的變化^[3~5]。正是由于這樣的原因，對數據全集的質量評價更加不能反映用戶使用數據的質量狀況。

要解決上述兩方面存在的問題，可以有兩種方式：a)采取對用戶獲得的數據視圖逐一（或部分）進行評價。顯然，由于處理的多變性和需求的靈活性，這種方式必然是費時、費力不可行的。b)考慮是否能夠依據對原始數據的質量評價結果導出用戶視圖的質量評價結果，即數據質量在處理運算下的質量傳遞關系具有什么樣的規律。只要找到這樣的傳遞規律就可以同時解決上述兩方面存在的問題，而且效率高。通過b)來研究數據質量在代數運算下的質量傳遞問題是本文的研究背景和出發點。

數據質量在代數運算下的質量傳遞影響可以形式化如圖1所示。其中： f()是數據處理變換函數，它將數據集合X變換成為結果數據集Y=f(X)；fDQ()是數據質量評價函數。按照一般的做法，對數據集合X、Y的評價需要分別經過評價函數fDQ()的作用得到評價結果fDQ(X)和fDQ(Y)。這就需要進行兩次質量評價，工作量明顯增大，而且多變的變換函數f()也使得評價實際上不可行。于是考慮，對于處理變換f()而言，如果能夠找到質量傳遞函數FDQ()，使得f()在FDQ()的作用下能夠轉換成為質量的代數表達形式，就可以通過FDQ(f(X))表達式直接計算得到fDQ

這樣可以方便、靈活地獲得f()作用下的質量評價結果，從而使數據質量評價更加符合用戶的使用和要求。在具體的研究中，一般以關系數據庫為研究對象，針對關系代數運算研究數據質量的傳遞影響。

關系代數運算下數據質量的傳遞影響研究可以在元組和屬性兩個粒度上進行。元組粒度將元組視為一個不可分割的整體，只要元組的數據項有錯誤，則整個元組被認為是錯誤的，對關系的評價以元組的質量來表示。顯然，元組粒度的評價是嚴格條件下的評價。這方面文獻[3~7]分別對元組粒度進行了研究，揭示了基本代數運算下的質量傳播基本規律。其中以Parssian等人研究最為突出。屬性粒度的研究，元組不再被看做是一個整體，而是細化至屬性粒度，以屬性的質量來表示關系的質量。這方面Scannapieco等人^[8]在元組和屬性粒度定義了完整性指標，并對并、交等運算的傳播問題進行了研究。Even等人^[9]從價值驅動（valuedriven）的角度給出了數據質量評價指標的抽象測度描述，在元組和屬性粒度定義了完整性、有效性、準確性和時效性指標測度。

目前，關于屬性粒度的數據質量傳遞影響研究尚不多見。本文在借鑒Parssian評價模型的基礎上，在屬性粒度定量的研究了投影運算對正確性評價指標的質量傳遞影響。

1 數據質量模型

Parssian研究數據質量傳播問題在元組粒度^[4]，以Kon等人^[6]提出的基本模型為依據，將關系中元組分為正確（SA）、錯誤（SI）、誤屬（SM）以及本應存儲的元組（SC）四種類型，并定義只要元組中存在錯誤則元組整體是錯誤的。正確性指標定義為正確元組（SA）占總元組（S）的比率。顯然，它是嚴格條件下的定義。然而，在一些情況下，元組中一個數據項出錯與多數數據項出現錯誤，其質量對使用者而言是存在差異的，因此，有必要對屬性粒度進一步研究。

圖2是筆者定義在屬性粒度的數據質量模型。其中理想關系是實體完整無誤的反映，沒有質量問題；存儲關系是理想關系的實際映射，由于數據獲取時的偏差使得關系中出現質量問題。正確性指標定義在屬性粒度，即衡量數據項是否正確，元組的質量通過屬性質量來反映。

在元組粒度的模型中，元組要么正確，要么錯誤，量化后非0即1。而屬性粒度的模型下，元組的量化結果已不再是二值邏輯，而處于[0，1]的閉區間。于是可以按質量類型將元組分為五種類型：a)正確元組（SA）由沒有任何錯誤的元組組成；b)部分屬性正確的元組介于正確與不正確之間形成模糊元組（SF）部分；c)錯誤元組（SI）由完全錯誤的元組組成；d)誤屬元組（SM）是存儲關系中包含了本不屬于概念關系中的元組和e)本應存儲的元組（SC）。其中：正確元組、誤屬元組和本應存儲的元組與Parssian模型相同；模糊元組和錯誤元組共同構成Parssian模型中的錯誤部分。

記正確性指標為α，在屬性粒度定義關系S的正確性測度如下：

定義1 數據項正確性（αi，j）。如果i行j列數據項正確則為1；否則為0。

定義2 元組正確性（αti）。元組（ti行）中正確數據項與總數據項的比率。定義3 屬性正確性（αAj）。屬性（Aj列）中正確數據項與總數據項的比率。定義4 關系正確性（αS）。關系S中正確數據項個數與總數據項之比。

顯然，關系的正確性可用元組或屬性的正確性來表示，即

αS=1/(m｜S｜)∑｜S｜i=1∑mj=1αi，j=（1/｜S｜）∑｜S｜i=1αti=（1/m）∑mj=1αAj(2)

其中：m為關系S的屬性個數。

定義5 誤屬性（γS）。誤屬元組占總元組的比率，即γS=｜SM｜/｜S｜。如表1數據（姓名是關鍵字，斜體下畫線為錯誤數據項）。其中：1#、2#、3#為正確元組（SA）；4#、5#、6#、7#為模糊元組（SF）；8#是錯誤元組（SI）（鍵屬性必須是正確的，否則元組是誤屬的）；9#、10#元組的鍵屬性錯誤，不應屬于關系S，因而是誤屬元組（SM）。

根據定義對表1進行量化得到表2。

表2中9#、10#是誤屬元組，即便有部分屬性是正確的，但它們對關系S而言仍然是錯誤的，因此元組所有屬性量化結果全為0。計算可得αS=0.63，γS=0.20。

2 屬性錯誤率

從定義4可以看出，關系的正確性可以由元組或者屬性的正確性來表示。比較而言，元組的數量眾多，計算比較困難；而屬性數量較少，計算相對容易得多，而且可以通過屬性的錯誤率來反映。然而，比較表1和2又可以看出，地址列在表1中的錯誤率為0.20，而在表2中卻是0.40。造成屬性錯誤率量化前后存在不同的根本原因在于：元組的質量類型首先決定了屬性的量化結果。也就是說，即便誤屬元組中存在正確的數據項，但是，由于元組本不應屬于關系，是元組的誤屬特性決定了表1中9#、10#元組中正確的數據項量化結果被強制為0，這使得屬性錯誤率在量化前后存在差異。

定義6 量化前屬性錯誤率（Ej）為屬性Aj在量化之前錯誤數據項個數與總個數之比。表1量化前屬性錯誤率分別為0.20，0.30，0.20，0.40。

定義7 量化后屬性錯誤率（E＾j）為屬性Aj在量化之后錯誤數據項個數與總個數之比。表1量化后錯誤率為0.20，0.40，0.40，0.50（由表2計算得到）。

屬性量化前后錯誤率的含義也是存在差別的。量化前錯誤率反映屬性固有的質量分布，而量化后錯誤率反映質量的評價。對質量評價而言，量化后錯誤率對評價更為直接和簡潔。但是，實際中獲得量化前錯誤率更加方便、容易，一般只需統計得到樣本中的錯誤率即可，而無須考慮元組類型的具體歸屬。于是需要找到兩者的數量關系，為此，作如下假設。

假設1 關系中錯誤的出現是隨機的。

對于非鍵屬性Aj量化前后形態如圖3所示。Aj的ASFj部分由正確和錯誤兩部分組成。其中：正確部分記為AS（1）Fj；錯誤部分記為A

根據屬性量化前后錯誤率的定義有

由式（8）計算得到量化后錯誤率分別為-，0.44，0.36，0.52。式（8）表明隨著誤屬元組數量的增加，將使關系的正確性進一步下降，質量更糟。

3 投影運算質量傳遞

投影運算（π）是從源關系S選擇若干屬性得到新關系R的運算，即R=πA(S)。投影運算不改變元組總數。由于投影運算可以選擇任意數量的列形成新關系，通過前面的分析可知，元組的類型對屬性量化有決定性作用，投影結果的鍵屬性構成就成為影響質量傳遞的關鍵因素。本文考慮投影運算包含全部鍵屬性的情況，對于包含部分鍵屬性的情況，由于元組類型變化情況比較復雜，筆者將另文詳述。

不失一般性，記關系S有m列，k個鍵屬性，且為前k個（屬性無先后順序）。假設投影運算選擇了d個非鍵屬性，且為前d個，于是投影結果關系R的屬性總數為d+k個。顯然，投影運算并不改變量化前后屬性錯誤率和誤屬率，即

對表1數據，選擇姓名、籍貫、地址三列形成的新關系如表3所示。量化結果如表4所示。直接計算量化表4得到α=0.67。以量化前錯誤率（-，0.30，0.20，0.40）代入式(15)計算α=0.56；以量化后錯誤率（-，0.30，0.20，0.40）代入式(14)計算α=0.50；以式(8)計算得到的量化后錯誤率（-，0.44，0.36，0.52）代入式(14)計算α=0.49。

4 結束語

本文在屬性粒度研究了投影運算對正確性指標的質量傳遞影響，定量地給出了傳遞關系，并分別用屬性量化前后錯誤率進行了表示。Parssian在元組粒度研究了投影運算的質量傳播問題，結果以鍵屬性正確性乘以非鍵屬性平均正確性之積的形式表示^[3]。由于評價粒度的差異使得兩者的結論存在不同。對于投影結果包含部分鍵屬性等較為復雜情況下的質量傳遞影響問題，筆者將進一步深入研究。

參考文獻：

［1］HUANG K T，LEE Y W，WANG R Y. Quality information and knowledge[M]. New Jersey: Prentice Hall， 1999:4344.

[2]PRICE R J，SHANKS G. A semiotic information quality framework[C]//Proc ofIFIP International Conference on Decision Support Systems (DSS2004): Decision Support in an Uncertain and Complex World. Prato，2004:658672.

[3]PARSSIAN A，SARKAR S，JACOB V S. Assessing data quality for information products:impact of selection， projection， and cartesian product[J].Management Science，2004，50(7):967982.

[4]PARSSIAN A，SARKAR S，JACOB V S. Assessing information quality for the composite relational operation join[C]//Proc of the 7th International Conference on Information Quality.Cambridge:MIT，2002:225237.

[5]REDDY M P，WANGR Y. A data quality algebra for estimating query result quality[C]//Proc of CISMOD. Bombay:[s.n.]，1996:112120.

[6]KON H B，MADNICK S E，SIEGEL M D. Good answers from bad data:a data management strategy[D].Cambridge:Sloan School of Management，MIT， 1995:116.

[7]WANG R Y，ZIAD M，IEE Y W. Data quality[M]. New York: Kluwer Academic Publishers， 2001:6379.

[8]SCANNAPIECO M，BATINI C. Completeness in the relational model: a comprehensive framework[C]//Proc of the 9th International Conference on Information Quality. Cambridge:[s.n.]，2004:333345.

[9]EVEN A， SHANKARANARAYANAN G. Valuedriven data quality assessment[C]//Proc of the 10th Conference on Information Quality. Boston:[s.n.]，2005:221236.