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

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

0 引言

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

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

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

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

文獻(xiàn)［3］對(duì)關(guān)系查詢的結(jié)構(gòu)特征進(jìn)行了詳細(xì)分析并且給出了查詢解答問題復(fù)雜度的分析方法和結(jié)論，本文首先引用文獻(xiàn)［3］關(guān)于數(shù)據(jù)庫(kù)及查詢的定義，并在此基礎(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 的類型可以看作=(a1，a2，…，ak)。將向量R1，R2，…，Rk簡(jiǎn)寫成，將數(shù)據(jù)庫(kù)寫成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查詢［3］。類型為→b 的查詢是部分函數(shù)，如下：

滿足以下條件：

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的查詢進(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的 類 型 可 以 看 作=((a1+1)，(a2+1)，…，(ak+1))。將向量R1，R2，…，Rk簡(jiǎn)寫成，將向量S1，S2，…，Sk簡(jiǎn)寫成，將擴(kuò)充數(shù)據(jù)庫(kù)寫成假設(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ù)查詢。類型為的函數(shù)查詢是部分函數(shù)：

滿足以下條件：

1）Qf滿足部分遞歸；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）在f〈(Bf，Qf(Bf)〉)上運(yùn)行M，輸出M的輸出?！?/p>

因?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，即語言F 是可判定的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

引理4［1］對(duì)于所有查詢類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中的證明類似。

考慮一個(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í)例中無向圖G 的頂點(diǎn)編號(hào)和G 中的節(jié)點(diǎn)對(duì)(u，v)。因此，對(duì) 于 所 有，當(dāng) 且 僅 當(dāng)時(shí)，成 立。其 中為BDS 的語言，?BDS為BDS 的一個(gè)分解因子。因此，

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

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

例4 某學(xué)校學(xué)生部分信息如表5 所示。數(shù)據(jù)庫(kù)B 中的每個(gè)元組指定學(xué)生的姓名（NAME）、性別（GENDER）、班級(jí)（CLASS）以及成績(jī)（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

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

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

3 結(jié)語

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