本节书摘来自华章出版社《大数据集成(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）提出的近似算法显著优于一些最基本的方法，即求权重之和、计算被影响的元组的数目，或者随机排序。它的表现接近于假设已知整个查询负载的运行结果的算法表现。