大數(shù)據(jù)上函數(shù)查詢解答的復(fù)雜度分析

吳文莉，劉國華，張君寶

（東華大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海201620）

0 引言

函數(shù)查詢是大數(shù)據(jù)應(yīng)用中一種重要的操作，隨著大數(shù)據(jù)地位的提升，如何解決大數(shù)據(jù)環(huán)境下函數(shù)查詢解答的復(fù)雜度問題是大數(shù)據(jù)應(yīng)用亟待解決的問題。針對大數(shù)據(jù)環(huán)境下查詢復(fù)雜度問題，文獻［1］進行了開創(chuàng)性研究：首先，指出了數(shù)據(jù)多樣化特性給查詢帶來了新的挑戰(zhàn)，即使是簡單的線性查找，在大數(shù)據(jù)環(huán)境下其所需時間也遠遠超出用戶可以接受的最大限度；其次，說明了大數(shù)據(jù)環(huán)境下P 類查詢也會變得難以處理；在此基礎(chǔ)上，對什么樣的查詢在大數(shù)據(jù)上是易處理的、如何求解大數(shù)據(jù)查詢的復(fù)雜度等問題進行了討論。

文獻［1］中所研究的查詢主要是傳統(tǒng)意義上的查詢，即查詢是一個由數(shù)據(jù)庫到關(guān)系的函數(shù)［2］，沒有涉及查詢本身包含函數(shù)的情況。作為對文獻［1］研究成果的一個補充，本文重點研究大數(shù)據(jù)上函數(shù)查詢解答的復(fù)雜度問題。

本文首先從計算理論角度對函數(shù)查詢解答問題進行研究，使用映射可歸約方法將函數(shù)查詢語言歸約到已知的可判定語言，證明函數(shù)查詢解答問題的可計算性；其次，使用一階語言描述函數(shù)查詢，從數(shù)據(jù)復(fù)雜度及表達復(fù)雜度兩個方面分析一階語言的復(fù)雜度；最后，在此基礎(chǔ)上分析了大數(shù)據(jù)上函數(shù)查詢解答的復(fù)雜度。

1 函數(shù)查詢相關(guān)定義

文獻［3］對關(guān)系查詢的結(jié)構(gòu)特征進行了詳細分析并且給出了查詢解答問題復(fù)雜度的分析方法和結(jié)論，本文首先引用文獻［3］關(guān)于數(shù)據(jù)庫及查詢的定義，并在此基礎(chǔ)上進行擴充定義。

定義1數(shù)據(jù)庫［3］。令U 是某個可數(shù)論域；數(shù)據(jù)庫是元組B=(D，R1，R2，…，Rk)，其中D ?U，D 是有限的。對于每一個1 ≤i ≤k，當(dāng)ai≥0 時，Ri?Dai。ai為Ri的秩，B 的類型可以看作=(a1，a2，…，ak)。將向量R1，R2，…，Rk簡寫成，將數(shù)據(jù)庫寫成B=(D，)。

例1 令論域U={2，3，4，5}，數(shù)據(jù)庫B=(D，R1，R2)，D={2，3，4，5}，R1={(2，5)，(3，2)，(4，3)，(5，2)}?D×D，R2={4，2}?D，k=2，a1=2，a2=1，則該數(shù)據(jù)庫如表1、表2所示。

定義2查詢［3］。類型為→b 的查詢是部分函數(shù)，如下：

滿足以下條件：

1）如果Q(B)是有定義的，那么有Q(B)?Db。

2）Q是部分函數(shù)。

表1 數(shù)據(jù)庫B中的關(guān)系R1Tab.1 Relation R1 of database B

表2 數(shù)據(jù)庫B中的關(guān)系R2Tab.2 Relation R2 of database B

下面對定義1的數(shù)據(jù)庫和定義2的查詢進行擴充定義。

定義3屬性。數(shù)據(jù)庫B=(D，)與定義1 含義相同，B中關(guān)系Ri中的每個屬性都是函數(shù)。Att={Att1，Att2，…，Attk}是個集族，Attj是個屬性集，Attj中屬性的個數(shù)與Ri的秩相同。Attj中每個屬性（即簡單屬性）表示如式（1）所示：

其中：l表示行號，i表示列號；函數(shù)ti：RO×CO →D，RO表示行號的集合，CO 表示列號的集合，由函數(shù)ti確定Attj中每個屬性Ai的屬性值。

EAtt={EA1，EA2，…，EAk}是擴充屬性集，擴充屬性EAi對應(yīng)于中的擴充屬性，擴充屬性的個數(shù)與關(guān)系Ri的個數(shù)相同。擴充屬性表示如式（2）所示：

其中：l 表示行號，i 表示列號；函數(shù)eti：Dc→U，Dc表示Attj中某些屬性的屬性值的笛卡爾積，由函數(shù)eti確定屬性EAi的屬性值。

定義4擴充數(shù)據(jù)庫。令U是某個可數(shù)論域；擴充數(shù)據(jù)庫是元組Bf=(D，R1，R2，…，Rk，S1，S2，…，Sk)，其中D ?U，D 是有限的。對于每一個1 ≤i ≤k，函數(shù)集合Si對應(yīng)關(guān)系Ri中的屬性的集合，當(dāng)(ai+1)≥1 時Ri?Uai+1。(ai+1)為Ri的秩，亦是Si中函數(shù)的個數(shù)。其中前ai個函數(shù)Sai為簡單函數(shù)（即簡單屬性），第(ai+1)個函數(shù)Sai+1為復(fù)雜函數(shù)（即擴充屬性）。B的 類 型 可 以 看 作=((a1+1)，(a2+1)，…，(ak+1))。將向量R1，R2，…，Rk簡寫成，將向量S1，S2，…，Sk簡寫成，將擴充數(shù)據(jù)庫寫成假設(shè)擴充數(shù)據(jù)庫每個關(guān)系中只有一個擴充屬性。

例2 令論域U={2，3，4，5，6，7}，擴充數(shù)據(jù)庫Bf=(D，R1，R2，S1，S2)，D={2，3，4，5}，R1={(2，5，7)，(3，2，5)，(4，3，7)，(5，2，7)}?U×U×U，R2={(4，6)，(2，3)}?U×U，S1={A1，A2，EA1}，S2={A3，EA2}。k=2，（a1+1）=（2+1），（a2+1）=（1+1）。該擴充數(shù)據(jù)庫如表3、表4 所示。其中擴充屬性集EAtt=｛EA1，EA2｝。

表3 擴充數(shù)據(jù)庫Bf中的關(guān)系R1Tab.3 Relation R1 of extended database Bf

表4 擴充數(shù)據(jù)庫Bf中的關(guān)系R2Tab.4 Relation R2 of extended database Bf

定義5函數(shù)查詢。類型為的函數(shù)查詢是部分函數(shù)：

滿足以下條件：

1）Qf滿足部分遞歸；

2）如果Qf(Bf)是有定義，那么Qf(Bf)?Ub且Qf(Bf)是有限的；

3）函數(shù)查詢Qf滿足一致性條件。

2 大數(shù)據(jù)上函數(shù)查詢解答的復(fù)雜度

2.1 函數(shù)查詢解答問題的可計算性

問題描述：已知擴充數(shù)據(jù)庫Bf以及函數(shù)查詢Qf，問該查詢計算機是否可計算。

在計算理論［5］中，論證一個問題是否可計算可以把該問題轉(zhuǎn)化為一個判斷一個串是否屬于一個語言問題，因此，該問題轉(zhuǎn)化為如下形式：

定義6映射可歸約性［5］。如果存在可計算函數(shù)f：Σ*→Σ*使得對每個ω，有：

那么語言Lg1是映射可歸約到語言Lg2的，記作Lg1≤mLg2。稱函數(shù)f為Lg1到Lg2的歸約。

引理1［3］語言E=｛〈B，Q（B）〉|B 是數(shù)據(jù)庫，Q（B）是能夠在B上解答的查詢｝是可判定的。

引理2［5］如果Lg1≤mLg2且語言Lg2是可判定的，則Lg1也是可判定的。

定理1語言F={〈Bf，Qf(Bf)〉|Bf是擴充數(shù)據(jù)庫，Qf(Bf)是能夠在Bf上解答的函數(shù)查詢} 是可判定的。

證明 由引理1可知E是可判定的。設(shè)M是E的判定器，f是從F到E的歸約。F的判定器N的描述如下：

N=“輸入查詢Qf的編碼〈Bf，Qf(Bf)〉：

1）計算f〈(Bf，Qf(Bf)〉)。

2）在f〈(Bf，Qf(Bf)〉)上運行M，輸出M的輸出。”

因為f 是從F 到E 的歸約，如果〈Bf，Qf(Bf)〉∈F，則f〈(Bf，Qf(Bf)〉)∈E。因此，只要〈Bf，Qf(Bf)〉∈F，則M 接受f〈(Bf，Qf(Bf)〉)。故N 的運行可以判定F，即語言F 是可判定的。

2.2 函數(shù)查詢解答問題的復(fù)雜度

已有的復(fù)雜類有LOGSPACE、NLOGSPACE、PSPACE、NPSPACE、PTIME、NPTIME、EXPTIME、EXPSPACE［6-12］等。文獻［12］詳細介紹了兩種方法衡量查詢解答復(fù)雜度，分別為數(shù)據(jù)復(fù)雜度和表達復(fù)雜度，以下給出兩種復(fù)雜度的衡量方法。

數(shù)據(jù)復(fù)雜度 首先確定一個查詢，將該查詢應(yīng)用到任意數(shù)據(jù)庫，然后根據(jù)數(shù)據(jù)庫大小的函數(shù)給出其復(fù)雜度。

表達復(fù)雜度 需要確定數(shù)據(jù)庫，使用查詢語言的任意表達式表示查詢，然后根據(jù)表達式的長度給出復(fù)雜度。

定義7一階語言。L 是沒有函數(shù)符號、具有等式的一階語言，R1，R2，…作為關(guān)系符號。使用符號Ri表示關(guān)系及作為關(guān)系本身，關(guān)系Ri的元數(shù)隱含在上下文中。First 表示由以下表達式組成的語言：

例3如下表達式表示類型為（（2+1），（1+1））→2的函數(shù)查詢。

定理2語言First 的數(shù)據(jù)復(fù)雜度是LOGSPACE（對數(shù)空間復(fù)雜性類），表達復(fù)雜度是PSPACE（多項式空間復(fù)雜性類）。

證明 為了測試-d ∈Qf(Bf)，需要循環(huán)遍歷所有量化變量的可能替換。文獻［12］中的算法具有LOGSPACE 數(shù)據(jù)復(fù)雜度和PSPACE表達復(fù)雜度。

數(shù)據(jù)復(fù)雜度：First的數(shù)據(jù)復(fù)雜性是LOGSPACE［12］。

傳統(tǒng)意義上的P 類問題在大數(shù)據(jù)環(huán)境下仍然是很困難的問題。比如線性掃描查詢類中的每個查詢，當(dāng)數(shù)據(jù)庫中的數(shù)據(jù)量達到1 PB，得到查詢結(jié)果所需的時間約1.9 d［15］。因此，傳統(tǒng)查詢解答問題的復(fù)雜度分析已經(jīng)不適用于大數(shù)據(jù)上的查詢解答。那么，什么樣的查詢在大數(shù)據(jù)上是易處理的？哪些查詢可以轉(zhuǎn)換為在大數(shù)據(jù)上是易處理的？

文獻［1］提出了Π-tractable 查詢的概念，Π-tractable 查詢的集合記為，表示經(jīng)過PTIME（多項式時間）預(yù)處理后，可以在NC（并行多項式-對數(shù)）［16-17］時間內(nèi)求解的查詢類；用分別為ΠΤP）表示查詢類集合（對應(yīng)于語言集合），該查詢類中的查詢（對應(yīng)于語言）通過對其重新分解以進行預(yù)處理后，可以將其有效地轉(zhuǎn)換為Π-tractable查詢。

文獻［1］中所研究的查詢主要是傳統(tǒng)意義上的查詢，沒有涉及查詢本身包含函數(shù)的情況，即沒有涉及到函數(shù)查詢。本文使用量化布爾公式歸約將函數(shù)查詢類歸約到布爾查詢類中，使用NC-factor 歸約將函數(shù)查詢語言FL 歸約到集合ΠΤP中、將函數(shù)查詢類OFL歸約到查詢類集合ΠΤQ中，即初步證明函數(shù)查詢在大數(shù)據(jù)上可以將其有效地轉(zhuǎn)換為Π-tractable查詢。

遵循復(fù)雜性理論［18］的慣例，使用符號的有限字母表Σ 編碼數(shù)據(jù)庫和查詢。數(shù)據(jù)庫可以編碼為字符串B ∈Σ*，并且具有必要的分隔符；查詢Q也可以編碼為字符串Q ∈Σ*。語言Υ是Σ*×Σ*的子集。使用Υ 來編碼布爾查詢類O，使得對于每個〈B，Q〉∈Υ，Q 是O 中的查詢，B 是數(shù)據(jù)庫，Q 在B 上有定義，并且Q（B）為真。即，Υ 可以看作二元關(guān)系，當(dāng)且僅當(dāng)Q（B）為真時，〈B，Q〉∈Υ。Υ稱為布爾查詢類O的語言。

使用量化布爾公式歸約［13］，函數(shù)查詢類可以歸約到布爾查詢類O 中。類似地，語言FL 是Σ*×Σ*的子集。使用FL 來編碼函數(shù)查詢類OFL，使得對于每個是OFL中的查詢，Bf是擴充數(shù)據(jù)庫。FL稱為函數(shù)查詢類OFL的語言。

下面分別介紹語言及查詢類的NC-factor 歸約定義及其相關(guān)引理。

定義8如果存在語言L1和L2的分解因子和，以及NC 函數(shù)α（?）和β（?），使得對于所有Σ*中的B 和Q，當(dāng)且僅當(dāng)〈α（B），β（Q）〉∈時，〈B，Q〉∈成立，則稱語言L1可以NC-factor歸約為語言L2。

引理3［1］對于所有語言L1、L2、L3：

定義9對于查詢類O1、O2，如果LO1可以NC-factor 歸約到LO2，那么O1可以NC-factor 歸約到O2，記為其中LO1、LO2分別為對應(yīng)于O1、O2的語言。

引理4［1］對于所有查詢類O1、O2、O3：

語言LBDS={(G，(u，v))}，存在分解因子使得BDS 可 以 轉(zhuǎn) 換 為Π-tractable。其 中π1(G，(u，v))=G，π2(G，(u，v))=(u，v)。

引理5［1］在NC-factor歸約下：

1）BDS是ΠΤP-complete；

2）查詢類OBDS是ΠΤQ-complete。

根據(jù)以上定義及引理，下面給出定理3。

定理3函數(shù)查詢語言FL在集合ΠΤP中，函數(shù)查詢類OFL在查詢類集合ΠΤQ中。

證明 由引理3～5 及定義9 可知，BDS 在ΠΤP中且OBDS在ΠΤQ中，若語言，則FL 在ΠΤP中，OFL在ΠΤQ中。下面證明。函數(shù)查詢類OFL在查詢類集合ΠΤQ中的證明類似。

考慮一個分解因子?FL=(π1，π2，ρ)，對于所有FL 中的實例，定義并 且。因 為 BDS 是P-complete［16］且FL 在P 中，那么存在NC 函數(shù)h(?)使得當(dāng)且僅當(dāng)在BDS中時，成立。然后存在NC函數(shù)α(?)和β(?)，使得和分別對應(yīng)于BDS 實例中無向圖G 的頂點編號和G 中的節(jié)點對(u，v)。因此，對 于 所 有，當(dāng) 且 僅 當(dāng)時，成 立。其 中為BDS 的語言，?BDS為BDS 的一個分解因子。因此，

2.3 Π-tractable查詢應(yīng)用實例

下面將具體分析Π-tractable 查詢類中連接查詢的復(fù)雜度。

例4 某學(xué)校學(xué)生部分信息如表5 所示。數(shù)據(jù)庫B 中的每個元組指定學(xué)生的姓名（NAME）、性別（GENDER）、班級（CLASS）以及成績（SCORE）。假設(shè)查詢Q0為查詢2 班的學(xué)生姓名。求解該查詢，則需要找出D0中所有滿足條件“CLASS=2”的元組，即元組（WU，F(xiàn)，2，80）、（WANG，F(xiàn)，2，92）、（FANG，M，2，87）。

表5 學(xué)生表中的部分?jǐn)?shù)據(jù)集D0Tab.5 Partial dataset D0 of student table

考慮有點-連接查詢類O1，Q1∈O1，Q1是數(shù)據(jù)庫B 上定義的查詢，查詢是否存在元組t 屬于D，使得t[Att]的值為c。其中Att是B 中的屬性，c是常量。利用索引查詢結(jié)果，可以得出點-連接查詢類O1在集合中。

對于點-連接查詢，首先，在離線的一次性預(yù)處理步驟中，可以為數(shù)據(jù)庫B 中的屬性Att 列的值構(gòu)建一個B+樹，此時，利用這些索引，點-連接查詢類O1中的所有D 上定義的查詢Q1可以在O(log|D|)時間內(nèi)求解。

3 結(jié)語

在大數(shù)據(jù)應(yīng)用環(huán)境下函數(shù)查詢成為主要操作，但目前還沒有人研究函數(shù)查詢解答復(fù)雜性問題。本文針對函數(shù)查詢解答的復(fù)雜度問題，首先對經(jīng)典的關(guān)系數(shù)據(jù)庫進行擴充，給出了擴充數(shù)據(jù)庫及函數(shù)查詢的形式化定義；然后證明了函數(shù)查詢解答問題的可計算性，使用一階語言描述函數(shù)查詢并且分析了其復(fù)雜度，并在此基礎(chǔ)上分析了大數(shù)據(jù)上函數(shù)查詢解答的復(fù)雜度。本文為大數(shù)據(jù)上函數(shù)查詢解答問題的進一步研究奠定了理論基礎(chǔ)，下一步工作將研究大數(shù)據(jù)上函數(shù)查詢解答問題的優(yōu)化策略。