不一致弱可用數(shù)據(jù)近似計算可行性判定問題

劉雪莉 李建中

摘 要： 給定一個查詢結(jié)果的一致性程度閾值，可行性判定判斷不一致數(shù)據(jù)上查詢結(jié)果的一致性程度是否大于給定的閾值。若不是，則查詢結(jié)果對用戶來說是沒有意義的，此查詢不可行。對于數(shù)據(jù)量大，查詢開銷較大的應(yīng)用中，若是能在查詢之前預(yù)估查詢結(jié)果的準(zhǔn)確度，則能在很大程度上節(jié)省查詢的開銷以及用戶的時間。在查詢密集型場景，判定查詢的可行性具有重要的意義。查詢可行性的判定等價于預(yù)估查詢結(jié)果的一致性。本文采用抽樣方法預(yù)估查詢結(jié)果的一致性。抽樣算法分別對一致的數(shù)據(jù)部分和不一致的數(shù)據(jù)部分采樣，使得保證抽出的樣本大概率下滿足查詢條件并且服從不一致數(shù)據(jù)的分布。 根據(jù)抽出的樣本，本文給出了估計一致性程度的算法，證明了一致性程度的估計是漸進無偏的。

關(guān)鍵詞： 不一致弱可用數(shù)據(jù)；聚集查詢；上下界；近似

Abstract： When the consistency degree of the query results exceeds the user tolerable threshold the query results for the user is invalid. This query could be called not feasible. If the query can be estimated before implementation by a relatively small price the efficiency of query processing will improve greatly. It gets more gains for larger data sets and larger query overhead. This paper designs a sample method to estimate the query results consistency degree. The sample method take samples separately from consistent part and inconsistent part of inconsistent data by different sample strategy. Then based on the samples the consistency degree is estimated. It is proved that the estimate is gradually unbiased Also It is proved that the estimate is a＼ epsilon ＼ delta） estimate.

Key words： inconsistent weak available；aggregation query；upper and lower bound；approximate

引言

當(dāng)查詢結(jié)果的一致性較低時，查詢結(jié)果對用戶的指導(dǎo)意義隨之降低。如果能在計算查詢結(jié)果之前判斷查詢的結(jié)果是否有意義，就避免了在原始不一致數(shù)據(jù)上進行查詢以及對查詢結(jié)果估計的開銷，尤其當(dāng)數(shù)據(jù)量較大時，判定查詢是否可行具有重要的意義。

由于查詢和數(shù)據(jù)相關(guān)，數(shù)據(jù)的不一致性程度對不同的查詢具有不同程度的影響。顯然，若是生成查詢結(jié)果的數(shù)據(jù)在整個數(shù)據(jù)集中是一致的，則數(shù)據(jù)的不一致性程度對此查詢結(jié)果的一致性并沒有影響。此外，即使生成查詢結(jié)果的數(shù)據(jù)是不一致的，其結(jié)果也可能是一致的。這為預(yù)估查詢結(jié)果的一致性帶來了挑戰(zhàn)。首先需要確定查詢結(jié)果的一致性是否受不一致數(shù)據(jù)的影響。其次，若查詢結(jié)果的一致性受到了不一致數(shù)據(jù)的影響，如何預(yù)估其影響程度，即預(yù)估查詢結(jié)果的一致性。

本文采用抽樣方法解決了合取查詢上的上述問題，主要貢獻如下：

（1）類似于一致性查詢中一致性查詢結(jié)果的定義，本文中定義了查詢結(jié)果的強一致性：若查詢結(jié)果是一致的，查詢結(jié)果滿足不一致數(shù)據(jù)的所有修復(fù)。即對不一致數(shù)據(jù)的任意一個修復(fù)，在該修復(fù)下進行查詢，一定包含一致性的查詢結(jié)果。此外，還定義了查詢結(jié)果的弱一致性：通過一個查詢結(jié)果滿足修復(fù)的比例來定義查詢結(jié)果的一致性。

（2）給定一個查詢，當(dāng)查詢不滿足其結(jié)果的一致性與不一致數(shù)據(jù)無關(guān)的充分條件時，本文設(shè)計了基于抽樣的算法預(yù)估查詢結(jié)果的一致性。抽樣算法分別對數(shù)據(jù)集中一致性和不一致性的數(shù)據(jù)部分分別采樣，最后通過對樣本進行查詢結(jié)果一致性計算，估計查詢結(jié)果的一致性。

（3）本文證明了估計的無偏性以及其置信區(qū)間，即給定一定的樣本，估計的誤差率不超過一定的范圍。

（4）實驗驗證了算法的有效性。

1 問題形式化定義

首先定義合取查詢。合取查詢包含查詢處理中的3種最基本的操作：選擇、投、等值連接，均為查詢處理中最常用到的查詢類型，其形式化定義如下。

4 多表查詢

多表查詢涉及到多表連接，其基本思想同2表查詢相同。需要做如下處理。

在數(shù)據(jù)預(yù)處理階段，假設(shè)一個表A的2個屬性C，D分別與其它表的屬性做連接，研究中在對其統(tǒng)計連接屬性值時，對C，D值做聯(lián)合處理，即若有一條元組其C屬性為c，D屬性為d 則對（c，d）做統(tǒng)計。在抽樣階段，對A表進行抽樣時，先抽?。╟，d）的概率，接著按q抽樣。其余處理保持不變。

5 實驗分析

實驗測試中使用了多種采樣方法，內(nèi)容展開如下：

（1）使用伯努利抽樣方法對整個數(shù)據(jù)集抽樣，不區(qū)分一致數(shù)據(jù)和不一致數(shù)據(jù)，記為Bernoulli1[2]。

（2）使用伯努利抽樣方法對一致性數(shù)據(jù)進行抽樣，使用蒙特卡洛抽樣不一致數(shù)據(jù)集，記為Bernoulli2。

（3）使用相關(guān)采樣方法對整個數(shù)據(jù)集抽樣，不區(qū)分一致數(shù)據(jù)和不一致數(shù)據(jù)，記為Correlated1[3]。

（4）使用相關(guān)采樣對一致性數(shù)據(jù)進行抽樣，使用蒙特卡洛抽樣不一致數(shù)據(jù)集，記Correlated2。

（5）使用end-biased[4]采樣對整個數(shù)據(jù)集抽樣，不區(qū)分一致數(shù)據(jù)和不一致數(shù)據(jù)，記為End-biased1。

（6）使用end-biased采樣對一致性數(shù)據(jù)進行抽樣，使用蒙特卡洛抽樣不一致數(shù)據(jù)集，記為End-biased2。

（7）使用兩層采樣方法對整個數(shù)據(jù)集抽樣，不區(qū)分一致數(shù)據(jù)和不一致數(shù)據(jù)，記為Two-Level1。

（8）使用兩層采樣方法對一致性數(shù)據(jù)進行抽樣，使用蒙特卡洛抽樣不一致數(shù)據(jù)集，記為Two-Level2。

為了驗證估計算法的效率，測試過程中還實現(xiàn)了根據(jù)原始數(shù)據(jù)計算查詢集合的一致性，記為Batch。

每次實驗重復(fù)采樣過程500次，計算其和真實結(jié)果一致程度的相對誤差，實驗圖返回最終的平均值。

5.1 數(shù)據(jù)集

實驗采用TPC-H數(shù)據(jù)集測試預(yù)估算法的性能。其中，規(guī)則集合＼Sigma采用TPC-H中已有的主鍵約束。此外，研究加入20個常數(shù)函數(shù)依賴。TPC-H數(shù)據(jù)集的規(guī)模因子設(shè)為10。由于實驗涉及到不一致數(shù)據(jù)，因此就在TPC-H數(shù)據(jù)中人工注入不一致信息，對于主鍵約束，隨機追加一些元組使其與主鍵約束相違背，針對常數(shù)函數(shù)依賴，修改元組的屬性值，使其出現(xiàn)不一致信息。2種類型注入不一致信息，數(shù)量比值為10∶1。注入不一致信息的規(guī)模從數(shù)據(jù)規(guī)模的5%到20%，每次遞增5%。

為了分析數(shù)據(jù)偏斜對預(yù)估結(jié)果的影響，研究重新生成了lintitem表，使其服從Zipf分布。其中，偏斜的程度受Zipf的參數(shù)＼alpha的影響，則使其從0變化到2 每次變化0.5。Zipf分布導(dǎo)致有少量的供應(yīng)商提供了大量的產(chǎn)品，大量的供應(yīng)商只提供了很少的產(chǎn)品。

查詢的設(shè)計包括2種類型：兩表連接和三表連接。其中，兩表連接涉及到表lineitem和supplier，連接屬性l＼_suppkey = s＼_supperkey。選擇操作為discount=x和shipdate=y，投影操作包含2種類型。一種是投影所有的屬性，即查詢不涉及到投影操作；另外一種投影l(fā)ineitem到l＼_suppkey和quantity屬性，supplier到name和address屬性。三表連接設(shè)計到表customer＼Join^borders＼Join^b，前2個表在custkey上做連接，后2個在orderkey上做連接。選擇操作為nationkey=z，discount=x和shipdate=y。投影為在customer上投影l(fā)＼_suppkey 和nationkey，lineitem上投影l(fā)＼_suppkey和quantity，order上投影orderkey和totalprice。

5.2 實驗脈絡(luò)

實驗從以下幾個方面驗證了抽樣預(yù)估的性能，分別涉及兩表查詢和三表查詢。詳情內(nèi)容分述如下。

（1）通過比較抽樣預(yù)估與查詢結(jié)果后估計一致性驗證了抽樣預(yù)估的效率。

（2）抽樣算法的相對誤差。

所有實驗均在一臺頻率為1.90 GHz的4核CPU，內(nèi)存32 G的機器上運行，不一致數(shù)據(jù)集的抽樣在Matlab軟件上研究呈現(xiàn)，其余所有的算法使用C++實現(xiàn)。

5.3 抽樣預(yù)估的效率

首先通過與Batch算法的比較，測試了抽樣方法估計查詢結(jié)果一致性的效率。設(shè)不一致數(shù)據(jù)占數(shù)據(jù)集的比例為5%，分別在2個表以及3個表的查詢上設(shè)計測試。測試了當(dāng)抽樣樣本的規(guī)模為原始數(shù)據(jù)的0.03%、0.05%、0.1%、0.5%、1%時估計算法的運行時間。需要注意的是，這里并不考慮抽樣時間和數(shù)據(jù)預(yù)處理時間。

實驗結(jié)果如圖1和圖2所示。從圖1中可以分析得出如下結(jié)論：

（1）抽樣預(yù)估的時間要遠(yuǎn)遠(yuǎn)小于Batch算法的時間，此處驗證了使用抽樣預(yù)估準(zhǔn)確率的可行性。即，可以在較小的時間內(nèi)預(yù)估查詢結(jié)果的一致性，若一致性過低時，避免了在原始數(shù)據(jù)上的查詢及一致性計算。具體地，當(dāng)樣本數(shù)據(jù)從 0.0%增至1%時，估計算法比Batch算法快了9～80倍。

（2）Bernouli預(yù)估的時間要小于其他抽樣預(yù)估的時間，是因為 Bernouli產(chǎn)生的樣本是均勻隨機的，相同樣本量下生成的結(jié)果集要小于其它采樣方法，但相對誤差較高，將在下一組實驗中進行說明。

（3）對不一致和一致數(shù)據(jù)進行分別采樣的估計算法時間要略高于統(tǒng)一采樣的時間，因為統(tǒng)一采樣時，不一致數(shù)據(jù)由于其占據(jù)的比例較低，獲選采到的可能性較小，其計算一致性多花費的時間較少。

（4）Two-Level采樣預(yù)估的時間要高于其它抽樣算法，這是因為Two-Level算法采樣的結(jié)果集滿足查詢條件的大小要超過其它采樣方法，使得計算結(jié)果集以及計算一致性的時間增大。

（5）三表查詢的執(zhí)行時間要高于兩表查詢。

（6）隨著抽樣樣本的增多，估計的時間也隨之增加。

圖2的結(jié)果與圖1的結(jié)果保持一致。

5.4 抽樣預(yù)估的有效性

固定不一致的數(shù)據(jù)比例不變，同樣變化樣本規(guī)模，從0.03%、0.05%、0.1%、0.5% 到1% 接下來將分別在兩表查詢和三表查詢上測試抽樣方法，預(yù)估查詢結(jié)果一致性的相對誤差。實驗結(jié)果如圖3和圖4所示。

從圖3的運行結(jié)果可以推得如下研究結(jié)論：

（1）對不一致和一致數(shù)據(jù)進行分別采樣的估計誤差要低于統(tǒng)一采樣的誤差?？偟貋碚f，平均要高25%。因為統(tǒng)一采樣時，對不一致數(shù)據(jù)的采樣并不符合不一致數(shù)據(jù)的分布，降低了估計一致性的準(zhǔn)確率。

（2）Two-Level采樣預(yù)估算法的相對誤差要低于其它采樣方法的相對誤差，這是由于Two-Level采樣能夠更準(zhǔn)確地估計查詢結(jié)果。

（3）采樣方法的誤差最大不超過20%，各種抽樣方法的誤差對于兩表查詢，都是可以接受的。

（4）隨著抽樣樣本的增多，抽樣誤差隨之減小。當(dāng)抽樣在1%時，所有的抽樣算法都具有較好的準(zhǔn)確率。

同上，由圖4不難得出實驗分析結(jié)論可見如下：

（1）對不一致和一致數(shù)據(jù)分別采樣的估計誤差平均低于統(tǒng)一采樣的誤差，基本可達(dá)20%。

（2）Two-Level采樣預(yù)估算法的相對誤差要低于其它采樣方法的相對誤差，對于其它不同的采樣方法，準(zhǔn)確率高出20%到35%。

（3）三表查詢的相對誤差要高于兩表查詢的相對誤差，這是因為隨著查詢連接表的增加，查詢結(jié)果估計的誤差隨之增加。但是Two-Level2抽樣估計算法依然具有較好的準(zhǔn)確率，其相對誤差在15%之內(nèi)。

（4）同圖3的結(jié)果一致，隨著抽樣樣本的增多，抽樣誤差隨之減小。

6 結(jié)束語

本文提出了一種基于抽樣的算法，預(yù)估了不一致數(shù)據(jù)集合取查詢的結(jié)果一致性。該算法對不一致數(shù)據(jù)集合和一致性數(shù)據(jù)集合分別采樣：對未知分布的不一致數(shù)據(jù)采用MCMC抽樣方法 對一致性數(shù)據(jù)采用兩層抽樣方法。 兩層抽樣方法能夠很好地估計查詢結(jié)果，MCMC抽樣保證了抽取的不一致數(shù)據(jù)服從不一致數(shù)據(jù)在整個數(shù)據(jù)集中的分布。采用該采樣方法，證明了查詢結(jié)果不一致估計的漸進無偏性。并使用中心極限定理給出了誤差的保證。此外，實驗驗證了預(yù)估一致性的可用性以及其相對誤差在涉及到3個表的查詢時，誤差率低于20%。

參考文獻

[1] CHEN Yu YI Ki. Two-level sampling for join size estimation[C]// ACM International Conference on Management of Data. Chicago USA： ACM 2017：759-774.

[2] CARLITZ L. q-Bernoulli numbers and polynomials[J]. Duke Mathematical Journal 1948 15（4）：987-1000.

[3] LIPTON R J NAUGHTON J F. Query size estimation by adaptive sampling （extended abstract）[C]//PODS′90 Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems. Nashville Tennessee USA： ACM 1990：40-46.

[4] ESTAN C NAUGHTON J F. End-biased samples for join cardinality estimation[C]// International Conference on Data Engineering. Atlanta GA USA： IEEE 2006：20.