大數據上函數查詢解答的復雜度分析

吳文莉，劉國華，張君寶

（東華大學計算機科學與技術學院，上海201620）

0 引言

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

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

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

1 函數查詢相關定義

文獻［3］對關系查詢的結構特征進行了詳細分析并且給出了查詢解答問題復雜度的分析方法和結論，本文首先引用文獻［3］關于數據庫及查詢的定義，并在此基礎上進行擴充定義。

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

例1 令論域U={2，3，4，5}，數據庫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，則該數據庫如表1、表2所示。

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

滿足以下條件：

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

2）Q是部分函數。

表1 數據庫B中的關系R1Tab.1 Relation R1 of database B

表2 數據庫B中的關系R2Tab.2 Relation R2 of database B

下面對定義1的數據庫和定義2的查詢進行擴充定義。

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

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

EAtt={EA1，EA2，…，EAk}是擴充屬性集，擴充屬性EAi對應于中的擴充屬性，擴充屬性的個數與關系Ri的個數相同。擴充屬性表示如式（2）所示：

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

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

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

表3 擴充數據庫Bf中的關系R1Tab.3 Relation R1 of extended database Bf

表4 擴充數據庫Bf中的關系R2Tab.4 Relation R2 of extended database Bf

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

滿足以下條件：

1）Qf滿足部分遞歸；

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

3）函數查詢Qf滿足一致性條件。

2 大數據上函數查詢解答的復雜度

2.1 函數查詢解答問題的可計算性

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

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

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

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

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

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

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

證明 由引理1可知E是可判定的。設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 函數查詢解答問題的復雜度

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

數據復雜度 首先確定一個查詢，將該查詢應用到任意數據庫，然后根據數據庫大小的函數給出其復雜度。

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

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

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

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

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

數據復雜度：First的數據復雜性是LOGSPACE［12］。

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

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

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

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

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

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

定義8如果存在語言L1和L2的分解因子和，以及NC 函數α（?）和β（?），使得對于所有Σ*中的B 和Q，當且僅當〈α（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分別為對應于O1、O2的語言。

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

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

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

1）BDS是ΠΤP-complete；

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

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

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

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

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

2.3 Π-tractable查詢應用實例

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

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

表5 學生表中的部分數據集D0Tab.5 Partial dataset D0 of student table

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

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

3 結語

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