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

吳文莉，劉國(guó)華，張君寶

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

0 引言

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

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

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

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

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

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

例1 令論域U={2，3，4，5}，數(shù)據(jù)庫(kù)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ù)庫(kù)如表1、表2所示。

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

滿(mǎn)足以下條件：

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

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

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

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

下面對(duì)定義1的數(shù)據(jù)庫(kù)和定義2的查詢(xún)進(jìn)行擴(kuò)充定義。

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

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

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

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

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

例2 令論域U={2，3，4，5，6，7}，擴(kuò)充數(shù)據(jù)庫(kù)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）。該擴(kuò)充數(shù)據(jù)庫(kù)如表3、表4 所示。其中擴(kuò)充屬性集EAtt=｛EA1，EA2｝。

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

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

定義5函數(shù)查詢(xún)。類(lèi)型為的函數(shù)查詢(xún)是部分函數(shù)：

滿(mǎn)足以下條件：

1）Qf滿(mǎn)足部分遞歸；

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

3）函數(shù)查詢(xún)Qf滿(mǎn)足一致性條件。

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

2.1 函數(shù)查詢(xún)解答問(wèn)題的可計(jì)算性

問(wèn)題描述：已知擴(kuò)充數(shù)據(jù)庫(kù)Bf以及函數(shù)查詢(xún)Qf，問(wèn)該查詢(xún)計(jì)算機(jī)是否可計(jì)算。

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

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

那么語(yǔ)言Lg1是映射可歸約到語(yǔ)言Lg2的，記作Lg1≤mLg2。稱(chēng)函數(shù)f為L(zhǎng)g1到Lg2的歸約。

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

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

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

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

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

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

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

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

2.2 函數(shù)查詢(xún)解答問(wèn)題的復(fù)雜度

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

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

表達(dá)復(fù)雜度 需要確定數(shù)據(jù)庫(kù)，使用查詢(xún)語(yǔ)言的任意表達(dá)式表示查詢(xún)，然后根據(jù)表達(dá)式的長(zhǎng)度給出復(fù)雜度。

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

例3如下表達(dá)式表示類(lèi)型為（（2+1），（1+1））→2的函數(shù)查詢(xún)。

定理2語(yǔ)言First 的數(shù)據(jù)復(fù)雜度是LOGSPACE（對(duì)數(shù)空間復(fù)雜性類(lèi)），表達(dá)復(fù)雜度是PSPACE（多項(xiàng)式空間復(fù)雜性類(lèi)）。

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

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

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

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

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

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

使用量化布爾公式歸約［13］，函數(shù)查詢(xún)類(lèi)可以歸約到布爾查詢(xún)類(lèi)O 中。類(lèi)似地，語(yǔ)言FL 是Σ*×Σ*的子集。使用FL 來(lái)編碼函數(shù)查詢(xún)類(lèi)OFL，使得對(duì)于每個(gè)是OFL中的查詢(xún)，Bf是擴(kuò)充數(shù)據(jù)庫(kù)。FL稱(chēng)為函數(shù)查詢(xún)類(lèi)OFL的語(yǔ)言。

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

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

引理3［1］對(duì)于所有語(yǔ)言L1、L2、L3：

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

引理4［1］對(duì)于所有查詢(xún)類(lèi)O1、O2、O3：

語(yǔ)言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）查詢(xún)類(lèi)OBDS是ΠΤQ-complete。

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

定理3函數(shù)查詢(xún)語(yǔ)言FL在集合ΠΤP中，函數(shù)查詢(xún)類(lèi)OFL在查詢(xún)類(lèi)集合ΠΤQ中。

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

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

2.3 Π-tractable查詢(xún)應(yīng)用實(shí)例

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

例4 某學(xué)校學(xué)生部分信息如表5 所示。數(shù)據(jù)庫(kù)B 中的每個(gè)元組指定學(xué)生的姓名（NAME）、性別（GENDER）、班級(jí)（CLASS）以及成績(jī)（SCORE）。假設(shè)查詢(xún)Q0為查詢(xún)2 班的學(xué)生姓名。求解該查詢(xún)，則需要找出D0中所有滿(mǎn)足條件“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

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

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

3 結(jié)語(yǔ)

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