本節書摘來自華章出版社《大資料內建(1)》一書中的第2章，第2.2節，作者 [美] 董欣（xin luna dong）戴夫士·斯裡瓦斯塔瓦（divesh srivastava），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視
一個資料內建系統極大地依賴于資料源和中間模式之間的模式映射來完成查詢重寫。但是，衆所周知建立和維護這些映射并不容易，需要大量的資源、前期投入的經曆以及專業技術等。雖然已經有幫助生成模式映射的工具；但是，仍然需要領域專家來改進自動生成的映射。因而，模式對齊成為建立一個資料內建系統的主要瓶頸之一。在大資料情況下，有巨大數量的資料源而且資料的模式可能會不斷變化，要生成完美的模式映射并且使它們能随着不斷演化的資料源模式而更新是不可能的。
[franklin et al. 2005]提出一種資料空間支援平台，通過按需內建的資料管理方式來解決資料的多樣性和高速度：最初提供一些服務，然後按需逐漸發展不同資料源之間的模式映射。給定一個查詢，這樣一個平台會從那些不存在完美模式映射的資料源中生成最好可能的近似答案。當它發現在某些資料源上存在大量複雜查詢或資料挖掘的應用時，它會指導使用者投入額外的經曆更精确地內建這些資料源。
這一節将講述資料空間系統的一些關鍵技術。2.2.1節講述如何通過建構機率中間模式和機率模式映射來提供最好可能近似查詢。2.2.2節講述如何在按需內建方式中征求使用者回報來确認候選映射的對錯。
為了在資料空間上提供最好可能的查詢服務，系統必須處理各種級别的不确定性。第一，當資料源的數目非常大時，如何對領域模組化就存在着不确定性；因而中間模式的建立中存在不确定性。第二，屬性可能具有歧義，一些屬性的含義有重疊并且這些含義會随時間發生變化，因而屬性比對中存在不确定性。第三，資料的規模和資料源模式的不斷演化使得無法生成和維護精确的模式映射，因而模式映射中存在不确定性。
這些不确定性可以用兩種方法解決。第一，可以建立一個機率中間模式來展現領域模組化中的不确定性。機率中間模式中的每個可能的中間模式代表源屬性的一種聚類方式，同一類中的屬性被認為具有相同的語義 [das sarma et al. 2008]。
第二，每個資料源模式和機率中間模式的每個可能的中間模式之間可以建立一個機率模式映射。一個機率模式映射包含一組屬性比對，描述資料源屬性和中間模式中的屬性聚類之間的對應關系 [dong et al. 2009c]。
本節中我們主要讨論每個資料源僅包含一個關系表的情況，進而模式映射可以簡單地從屬性比對中推斷出。下面我們較長的描述每一部分，并在最後介紹這一新體系結構下的查詢問答。
1．機率中間模式
中間模式由一組模式詞語（如關系表、屬性名等）構成，用于在其上表達查詢。它描述了領域中對內建應用重要的部分。考慮從一組資料源自動推斷出一個中間模式的問題，其中每個資料源僅包含一個關系表。在這種情況下，中間模式可以被看成源屬性的一個“聚類”，相似的屬性被聚成一類，進而形成一個中間屬性。注意在傳統的中間模式中，每個屬性都有一個名字，但在上面這樣生成的中間模式中，屬性名不是必需的。使用者可以在查詢中使用任一源屬性，并且源屬性都可以用它所屬聚類所對應的中間屬性來替換。實際中，當将中間模式呈現給使用者時，可以用每個聚類中最頻繁的源屬性來代表此中間屬性。
查詢答案的品質關鍵依賴于聚類的品質。然而，由于被內建的資料源的異構性，通常源屬性的語義繼而導緻聚類的語義都是不确定的，如下例所示。
下面兩個源模式都是描述航班的。
s1(flight number (fn), departure gate time (dgt), takeoff time (tt),
landing time (lt), arrival gate time (agt)) s2(flight number (fn), departure time (dt), arrival time (at))
在s2中，屬性dt可以是離開登機口時間，也可以是起飛時間。類似地，at可以是到達登機口時間，也可以是着陸時間。
現将s1和s2的屬性進行聚類，可以有多種方式，它們分别對應不同的中間模式。下面給出一些例子：
med1({fn}, {dt, dgt, tt}, {at, agt, lt}) med2({fn}, {dt, dgt}, {tt}, {at, lt}, {agt}) med3({fn}, {dt, dgt}, {tt}, {at, agt}, {lt}) med4({fn}, {dt, tt}, {dgt}, {at, lt}, {agt}) med5({fn}, {dt}, {dgt}, {tt}, {at}, {agt}, {lt})
上面列出的中間模式中沒有一個是完美的。模式med1将s1中的多個屬性聚成一類。模式med2看上去不一緻，因為出發時間（departure time）和離開登機口時間（departure gate time）聚成一類，而到達時間（arrival time）和着陸時間（landing time）聚成一類。模式med3、med4和med5基本正确，但它們沒有展現出發時間（departure time）和到達時間（arrival time）可以是離開和到達登機口的時間，也可以是起飛和降落的時間。
是以，即使存在完美的模式映射，上面所列的中間模式也沒有一個會對所有使用者查詢傳回理想的結果。例如，使用med1無法正确回答查詢條件既包含離開登機口時間（departure gate time）又包含起飛時間（takeoff time）的查詢，因為它們被視為同一個屬性了。又如，如果一個查詢包含出發時間（departure time）和到達時間（arrival time），使用med3或med4作為中間模式将不必要地傾向于起飛和着陸時間，或者傾向于離開和到達登機口的時間。而使用med2作中間模式的系統将錯誤地傳回具有給定離開登機口時間和着陸時間的結果。使用med5作中間模式的系統或者會錯過提供dgt、tt、agt和lt的資料源中的一些資訊，或者會具有和使用med2～med4作為中間模式同樣的問題。 ?
作為一種解決方法，我們可以将那些非常可能為真的所有聚類建立一個機率中間模式，每種聚類被賦予一個機率值。例如，可以建立一個包含med3和med4的機率中間模式，分别被賦予機率值0.6和0.4。
機率中間模式被正式地定義如下。給定一組源模式{s1, …, sn}，模式si（i∈[1, n]）中的所有屬性記為a(si)，所有源模式屬性的集合記為a，即a=a(s1)∪…∪a(sn)。一組資料源上的一個中間模式被記為med={a1, …, am}，其中每個ai，i∈[1, m]，稱作一個中間屬性。每個中間屬性是資料源屬性的一個集合，即aia；對任意i, j∈[1, m]，i≠j，有ai∩aj=。如前所述，如果一個查詢包含一個屬性a∈ai，i∈[1, m]，則在回答該查詢時所有出現的a都被替換為ai。
一個機率中間模式是一個中間模式的集合，其中每個中間模式有一個機率，用以說明該模式正确描述資料源的領域的可能性。
[das sarma et al. 2008] 給定一組源模式{s1,…, sn}，{s1, …, sn}上的一個機率中間模式（p-med-schema）是如下一個集合
pmed = {(med1, pr(med1)), …, (medl, pr(medl))}
其中
對任意i∈[1, l?]，medi是s1, …, sn的一個中間模式；對任意i, j∈
[1, l]，i≠j，medi和medj分别對應于a中源屬性的兩個不同聚類。
* pr(medi)∈[0,1]，并且。
[das sarma et al. 2008]中提出了為資料源模式s1, …, sn建立一個機率中間模式的算法：首先建立pmed中的多個中間模式med1, …, medl，然後給每個中間模式賦一個機率值。
源模式中的兩種資訊可以為屬性聚類提供證據：1）源屬性間的兩兩相似度；2）源屬性的統計共現特性。第一種資訊指出兩個屬性什麼時候可能相似，被用來建立多個中間模式。很多屬性比對的算法可供選擇來計算屬性間的兩兩相似度。兩個源屬性ai和aj之間的相似度s(ai, aj)衡量這兩個屬性在表達同一個現實世界中的概念上有多接近。第二種資訊指出兩個屬性什麼時候可能不同，被用來給每個中間屬性賦一個機率值。
對例2.1中的模式s1和s2而言，計算兩兩字元串的相似度和字典比對會得到屬性dt可能和dgt與tt都相似，因為它們的屬性名相似并且取值相似。然而，由于第一個資料源模式同時包含dgt和tt屬性，則這兩個屬性不可能指代相同的概念。是以，第一個模式顯示dgt不同于tt，是以不太可能将dt、dgt和tt都聚成一類。
更具體地，給定資料源模式s1,…, sn，建立機率中間模式pmed的過程可以分成三步。第一，計算屬性間的相似度。将相似度大于門檻值τ+ε的所有屬性放到同一類裡，相似度在[τ-ε,τ+ε]區間内的屬性對稱作不确定對。第二，為不确定對集合的每個子集建立一個中間模式，把子集中的每對屬性放在同一個類中。得到的中間模式的集合構成了機率中間模式的所有可能的中間模式。最後，如果資料源模式si(i∈[1, n]）中的任何兩個屬性都沒有出現在中間模式medj（j∈[1, l]）的一個類（代表一個中間屬性）中，則稱si和medj一緻。每個可能的中間模式的機率正比于與其一緻的源模式的個數。
2．機率模式映射
模式映射描述了資料源的内容和中間資料之間的關系。在許多應用中，不可能預先給出所有的模式映射。機率模式映射可以展現模式間映射的不确定性。我們再從一個說明性的示例出發，然後正式地定義機率模式映射，并在最後描述它們是如何被生成的。
繼續例2.1。考慮s1和中間模式med3之間的映射。一個半自動的屬性比對工具可能生成s1和med3之間4種可能的映射。由于隻考慮單個關系表的模式，每種映射可以被表示為屬性比對的形式，如下所示，其中ddgt={dt, dgt}，aagt={ at, agt}。
盡管4種映射都将s1.fn屬性映射到med3.fn屬性，它們映射資料源的其他屬性到中間模式的不同屬性上。例如，映射m1将s1.dgt映射到med3.ddgt，而m3将s1.dgt映射到med3.tt。要展現映射是正确的具有不确定性，不是随意地或按照領域專家的幹預舍棄一些可能的映射，而是為查詢問答保留所有的映射并賦一個機率值表示每個映射為真的可能性。
類似地，在s1和med4之間存在着如下一個機率映射，其中dtt={dt, tt}，alt={at，lt}。
在定義機率模式映射之前，讓我們首先回顧一下非機率模式映射。一個機率映射的目标是說明一個源模式s和一個目标模式t（如中間模式）之間的語義關系。本節中所考慮的模式映射是一種受限的形式：它隻包含s和t中屬性之間一對一的比對。
直覺地，一個機率模式映射描述一個源模式和一個目标模式之間的一組可能的模式映射的機率分布。
[dong et al. 2009c] 假設s和t是兩個隻包含一張關系表的關系模式。在源模式s和目标模式t之間的一個機率映射，pm，是一個集合，pm = {(m1, pr(m1)), …, (ml, pr(ml))}，其中
對任意i∈[1, l?]，mi是s和t之間的一個一對一的屬性比對，對任意i, j∈[1, l?]，i≠j，mi和mj不同。
[das sarma et al. 2008]中提出一個建立機率的算法。首先，計算每一對源屬性和目标屬性之間的權重比對。一些現有的屬性比對技術可以用來計算這些權重比對。權重被歸一化在[0, 1]區間内。第i個源屬性和第j個目标屬性之間的權重比對記作mi,j=((i, j), wi,j)，其中wi,j是比對(i, j)的權重。
盡管權重比對給出了每對屬性的相似度，它們沒有指出一個源屬性應該被映射到哪個目标屬性。例如，一個目标屬性到達時間（arrival time）和源屬性到達登機口時間（arrival gate time）以及着陸時間（landing time）都相似，因而在一個模式映射中将到達時間映射為任何一個都是合理的。事實上，給定一組權重比對，可能有多個與它一緻的機率映射。
（一緻的機率映射）[das sarma et al. 2008] 一個機率映射pm與一對源屬性和目标屬性之間的一個權重比對mi,?j相一緻，如果pm中所有包含比對(i, j)的映射m∈pm的機率之和等于wi,?j，即
我們說一個機率映射和一個權重比對集合m是一緻的，如果它和該集合中的每個權重比對m∈m都一緻。
給定一組權重比對，可能有無數個與它一緻的機率映射，如下例所示。
考慮一個源模式s(a, b)和一個目标模式t(a', b'?)。假設源屬性和目标屬性之間的權重比對為wa,a'?=0.6，wb,b'?=0.5（其他為0）。與這組權重比對一緻的機率映射有無數個，下表中列出其中兩個。
從某種意義上說，pm1看上去要優于pm2，因為它假設a和a'之間的相似性與b和b'之間的相似性是互相獨立的。 ?
一般情況下，在與一組權重比對m一緻的多個機率映射中間，最優的是具有最大熵的那個機率映射，即其機率分布獲得的最大值。在例2.3中，pm1具有最大熵。
最大熵背後的直覺含義是當從一組互斥事件上的多個可能分布中選擇時，不傾向于任何一個事件的分布會被優先選擇。因而，不引入未預知的新資訊的分布會被優先選擇。最大熵原理在其他領域也被廣泛使用，如自然語言處理。
綜上所述，一個機率映射可以分三步來建立。第一，生成每一對源模式s的屬性和目标模式t的屬性之間的權重比對。第二，枚舉s和t之間所有可能的包含一組比對m的一對一的模式映射，記為m1, …, ml。第三，通過最大化結果機率映射的熵來給每個映射賦一個機率值，即求解下面有限制的優化問題：
3．查詢問答
在讨論如何通過機率中間模式和機率映射回答查詢之前，我們首先需要定義機率映射的語義。直覺地，一個機率模式映射展現了pm中哪個映射是正确的具有不确定性。當一個模式比對系統生成了一組候選比對時，有兩種方式來解釋不确定性：1）pm中的單個映射是正确的，并且它适用于s中的所有資料，或者2）有幾個映射是部分正确的，每個隻适用于s中所有元組的一個子集，盡管對一個具體的元組而言并不知道哪個映射是正确的。
查詢問答被定義在兩種解釋之下。第一種解釋稱為機率模式映射的表（by-table）語義而第二種解釋稱為元組（by-tuple）語義。注意我們不能贊成一種解釋而反對另一種；應用的實際需要會決定恰當的語義。下面的例子闡明了兩種語義。
繼續例2.2，考慮s1的一個執行個體如下所示。
fn dgt tt lt agt 49 18:45 18:53 20:45 20:50 53 15:30 15:40 20:40 20:50
記得使用者可以使用資料源中的任何屬性來建構查詢。現在考慮查詢q: select at from med3（其中med3如例2.1中給出），以及例2.2中給出的機率映射。在表語義下，每個可能的映射被應用于s1中的所有元組，會生成如下的答案。
表語義答案（at） 機率 m1 m2 m3 m4 機率映射 20:50 0.64 — 0.16 — 0.64+0.16=0.8 20:45 — 0.16 — 0.04 0.16+0.04=0.2 20:40 — 0.16 — 0.04 0.16+0.04=0.2
相比之下，在元組語義下，不同可能的映射被應用于s1中不同的元組上，生成下面的答案（細節略去）。
元組語義答案（at） 機率 20:50 0.96 20:45 0.2 20:40 0.2
相對于機率映射的查詢問答的定義是相對于一般映射的查詢問答的自然擴充，稍後做一回顧。一個映射定義了s的執行個體和t的與映射一緻的執行個體之間的一種關系。
（一緻目标執行個體）[abiteboul and duschka 1998] 假設m是源模式s和目标模式t之間的一個模式映射，ds是s的一個執行個體。
t的一個執行個體dt被認為與ds和m相一緻，如果對于每個元組ts∈ds，都存在一個元組tt∈dt使得對于每個屬性比對（as,at）∈m都有ts中的屬性as值和tt中的屬性at值相同。
給定一個關系映射m和一個源執行個體ds，可能存在無數個與m和ds相一緻的目标執行個體。所有這樣的目标執行個體的集合被記作。一個查詢q的答案的集合是在集合中的所有執行個體上的答案的集合的交集。
（肯定答案）[abiteboul and duschka 1998] 假設m是源模式s和目标模式t之間的一個關系映射，ds是s的一個執行個體，q是t上的一個查詢。
一個元組t稱作q相對于ds和m的一個肯定答案，如果對每個執行個體dt∈都有t∈q(dt)。
這些概念可以被推廣到機率映射中，從表語義開始。直覺地，一個機率映射pm描述了一組可能世界，每個有一種可能的映射m∈pm。在表語義中，一張源關系表可能屬于一個可能世界，即對應于該可能世界的可能映射應用于整張源關系表。順着這一直覺想法，與源執行個體相一緻的目标執行個體被定義如下。
（表一緻執行個體）[dong et al. 2009c] 假設pm是源模式s和目标模式t之間的一個機率映射，ds是s的一個執行個體。
t的一個執行個體dt被認為與ds和pm表一緻，如果存在一個映射m∈pm使得dt與ds和m相一緻。
在機率背景中，每個答案會被賦予一個機率。直覺地，所有肯定答案相對于每個可能的映射單獨被考慮。一個答案t的機率是使其成為一個肯定答案的所有映射的機率之和。表語義答案的定義如下。
（表語義答案）[dong et al. 2009c] 假設pm是源模式s和目标模式t之間的一個機率映射，ds是s的一個執行個體，q是t上的一個查詢。
假設t是一個元組，是pm的一個子集，其中每個m∈滿足對每個dt∈都有t∈q(dt)。
設p=，如果p>0，則(t, p)是q在ds和pm上的一個表語義答案。
在可能世界的概念中，按照元組語義，一張源關系表中的不同元組可能會屬于不同的可能世界；即和這些可能世界關聯的不同的可能映射會應用于不同的源元組。
正式地，元組語義和表語義的定義之間的關鍵差別在于一緻目标執行個體是通過一個映射序列将m中（可能不同）的映射賦給ds中每個源元組來定義的。（不失一般性，為了比較這些序列，執行個體中的元組被賦予一定的順序。）
（元組一緻執行個體）[dong et al. 2009c] 假設pm是源模式s和目标模式t之間的一個機率映射，ds是s的一個具有d個元組的執行個體。
t的一個執行個體dt被認為與ds和pm元組一緻，如果存在一個序列使得d是ds中元組的數目，并且對每一個1≤i≤d，
* m?1∈pm。
對ds的第i個元組ti，存在一個目标元組ti'∈dt使得對于每個屬性比對（as, at）∈m都有ti中的屬性as值和ti'中的屬性at值相同。
給定一個映射序列seq=，所有與ds和seq一緻的目标執行個體的集合記作。注意如果dt與ds和m表一緻，那麼dt也和ds以及每個映射都是m的映射序列元組一緻。
一個映射序列seq=可以被視為一個獨立事件，其機率為pr(seq)=。如果pm中有l個映射，則有ld個長度為d的序列，且它們的機率之和為1。從pm中生成的長度為d的映射序列的集合記為seqd(pm)。
（元組語義答案）[dong et al. 2009c] 假設pm是源模式s和目标模式t之間的一個機率映射，ds是s的一個具有d個元組的執行個體，q是t上的一個查詢。
假設t是一個元組，是seqd?(pm)的一個子集，其中每個seq∈滿足對每個dt∈都有t∈q(dt)。
設p=，如果p>0，則(t, p)是q在ds和pm上的一個元組語義答案。
q在ds上的表語義答案的集合記為qtable(ds)，元組語義答案的集合記為qtuple(ds)。
在表語義的情況下，回答查詢相對簡單。給定源模式s和目标模式t之間的一個機率映射pm和t上的一個spj查詢q，計算出q在每個映射m∈pm下的肯定答案，并将機率值pr(m)賦給每個答案。如果一個元組是q在pm中的多個映射下的答案，則将這些不同映射的機率加起來作為此元組的機率。
若将表語義下的查詢問答政策擴充到元組語義，則需要計算從pm中生成的每個映射序列下的肯定答案。然而，映射序列的數目相對于輸入資料的大小是指數級的。事實上，已經證明一般情況下，按照元組語義回答模式機率映射上的spj查詢是困難問題。
[dong et al. 2009c] 假設pm是一個機率映射，q是一個spj查詢。
按照表語義來回答pm上的查詢q的時間複雜度相對于資料和映射大小是ptime的。
得到q在pm上的一個元組答案的機率的時間複雜度相對于資料大小是#p-完全的，相對于映射大小是ptime的。
證明 ptime時間複雜度是顯然的。在元組語義下相對于資料大小是#p難複雜度可以通過将求滿足偶單調2dnf布爾公式的變量指派的個數問題規約到找查詢答案的問題來證明。 ?
最後，考慮在一個機率中間模式和一組機率映射（每個對應一個可能的中間模式）上的查詢問答的語義。直覺地，要計算查詢答案，必須首先在每個可能的中間模式上回答查詢，然後每個答案元組的機率是它在所有中間模式上的機率按照各中間模式的機率權重求和。表語義下的正式定義如下；元組語義下的定義類似。
（機率中間模式和機率映射上的查詢答案）[das sarma et al. 2008] 假設s是一個源模式，pmed={(med1, pr(med1)), …, (medl, pr(medl))}是一個概念中間模式，pm={pm(med1), …, pm(medl)}是一組機率映射，其中pm(medi)是s和medi之間的機率映射，ds是s的一個執行個體，q是一個查詢。
假設t是一個元組，pr(t|medi)，i∈[1, l]，是t作為q在medi和pm(medi)上的一個答案的機率。設p=，如果p>0，則(t, p)是q在pmed和pm上的一個表語義答案。
所有答案的集合記為qm,pm(ds)。
考慮例2.4中的s1執行個體和查詢q：select at from m。在表語義下，查詢在例2.1中的pmed和例2.2中的pm上的答案如下所示。
表語義答案（at） med3 med4 最終機率 20:50 0.8 0.2 0.80.6+0.20.4=0.56 20:45 0.2 0.8 0.20.6+0.80.4=0.44 20:40 0.2 0.8 0.20.6+0.80.4=0.44
這樣的答案有兩個優勢：1）離開和到達登機口時間産生的答案與起飛和降落時間産生的答案被平等對待，2）出發和到達時間正确對應的答案被優先選擇。 ? ?
4．主要結果
[das sarma et al. 2008] 在5個領域内爬取的web表格上測試了所提出的技術，其中每個領域包含50～800張web表格（即資料源）。主要結果如下。
1）和一個人工說明模式映射的內建系統相比較，所提出的方法在每個領域的查詢問答任務上都獲得了大于0.9的f值。
2）所提出的方法在關鍵詞搜尋任務中顯著地提升了pr曲線（相同查全率下，查準率常常提高了一倍），顯示用機率的方式利用結構資訊所帶來的好處。
3）使用一個機率中間模式比使用一個确定的中間模式得到更好的實驗結果。
4）系統設定時間随資料源的數目呈線性增長，對一個包含817個資料源的領域大概花費了3.5分鐘。
一個資料空間系統起始時通過機率模式對齊提供最好可能的服務。當更多的查詢到來時，它會發現一些可能的候選比對，如果是精确映射會獲益很大，因而讓使用者或領域專家人工地确認這些映射。但可能會有太多的候選比對需要使用者回報，為所有候選比對進行回報代價太大而且通常是不必要的。因而關鍵問題是找到确認候選比對的最佳順序。
[jeffery et al. 2008]提出使用一種決策理論方法來解決這個問題。這裡用到的決策理論中的關鍵概念是完美資訊價值（value of perfect information, vpi）[russell and norvig 2010]，它用來量化确定一些未知變量的真值可能帶來的潛在收益。我們下面詳細讨論如何應用vpi概念來确定候選比對回報的順序。
1．确認比對的收益
假設Ω是一個資料空間，包含一組資料源以及一些屬性對、實體對和值對之間的已知比對Λ是一組沒被包含在Ω中的候選比對。資料空間Ω相對于Λ的有用性記為u(Ω,Λ)。有用性是從查詢日志記錄的一組查詢q上聚集得到的。每個查詢qi有一個權值wi,由查詢的頻率或重要性決定。對每個查詢qi，它在Ω和Λ上的結果品質被記為r(q,Ω,Λ)。則Ω相對于Λ的有用性的計算如下：
假設查詢都不包含否定條件并且隻有被确認的比對才會被用來回答查詢，則知道更多映射會改善答案的覆寫率。因而，r(q,Ω,Λ)表示在現有資料空間Ω上得到的答案覆寫範圍與在根據使用者在Λ上的回報擴充後的資料空間上得到的答案覆寫範圍的比值，其中根據使用者回報擴充後的資料空間記為Ω∪Λp（ΛpΛ是使用者回報确認的正确比對）。
現在考慮确認一個候選比對λ∈Λ的收益。使用者回報會造成兩種可能的結果：λ或者被确認為真或者被判斷為假。兩種情況下導緻的資料空間分别記為和。假設比對為真的機率為p；此機率是根據自動比對結果的置信度計算的。确認λ的收益可以用以下等式計算：
2．近似計算收益
計算确認一個比對λ的收益需要估計查詢覆寫範圍，即需要了解在使用者回報Λ之後的資料空間，而它是未知的。我們可以通過假設Λ僅包含一個映射λ來近似計算有用性。則等式（2.2）可以被重寫為：
按照收益來對比對進行排序，則可以首先在高收益的比對上獲得使用者回報。
考慮例2.4中s1的一個執行個體，記為d(s1)，和例2.1中的med3。一個候選屬性比對λ=（agt, aagt）有0.8的機率為真。假設隻觀察到兩個查詢與λ有關。查詢q1：select at from med3，權重為0.9；查詢q2：select agt from med3，權重為0.5。
對q1來說，沒有比對λ則不會從d(s1)得到任何答案；即|q1(Ω)|=0。一旦λ已知，則可以得到所有的答案，即|q1(Ω∪{λ})|=1。然而對q2來說，即使沒有比對λ，依然可以從d(s1)中得到所有的答案；即|q2(Ω)|=|q2(Ω∪{λ})|=1。帶入等式（2.7），得到λ的收益為
3．主要結果
1）所提出的方法是有效的：在确認了前10%的候選比對之後，它将覆寫範圍改進了17.2%，在确認了前20%的候選比對之後，它已經能得到95%在全部候選比對上做回報可以得到的潛在收益。
2）提出的近似算法顯著優于一些最基本的方法，即求權重之和、計算被影響的元組的數目，或者随機排序。它的表現接近于假設已知整個查詢負載的運作結果的算法表現。