關系數(shù)據(jù)模型中函數(shù)查詢的結構特征

吳文莉， 劉國華,

(1 東華大學 計算機科學與技術學院, 上海 201620; 2 上海市數(shù)據(jù)科學重點實驗室(復旦大學)， 上海 201203)

0 引 言

查詢(即，由數(shù)據(jù)庫到關系的函數(shù))和查詢語言(即，用于表示這一函數(shù)的語言)[1]一直以來都備受人們關注。Codd于1970年提出關系數(shù)據(jù)模型后，關系模型的查詢及查詢語言成為研究熱點，出現(xiàn)了一批具有影響力的研究成果，如一階關系演算以及關系代數(shù)[2-3]、合取查詢[4]、表查詢[5]、函數(shù)查詢語言[6]等。

近年來，隨著大數(shù)據(jù)地位的提升，如何在大數(shù)據(jù)環(huán)境下準確、高效地得到查詢結果是函數(shù)查詢亟待解決的問題，其中如何解決查詢解答問題一直是人們關注的重點問題。大數(shù)據(jù)為查詢解答帶來了挑戰(zhàn)，大數(shù)據(jù)查詢的計算復雜性不再類似傳統(tǒng)查詢[7]。文獻[7]對查詢解答問題難易程度的判定提出了形式化的方法，并對預處理問題進行了研究，提出了數(shù)據(jù)驅動的預處理和查詢驅動的預處理兩種方法。文獻[8]明確了大數(shù)據(jù)環(huán)境下查詢解答問題難易程度的劃分標準，對什么查詢在大數(shù)據(jù)上是易處理的、如何求解大數(shù)據(jù)查詢的復雜性等問題給出了一系列預處理方案，對查詢解答問題的近似求解算法進行了探討。

在大數(shù)據(jù)應用環(huán)境下，函數(shù)查詢成為主要操作，如函數(shù)查詢語言可以用于定義大數(shù)據(jù)上的分析查詢，用其結果定義各種執(zhí)行任務[9]。為了便于表示大數(shù)據(jù)上的函數(shù)查詢，Nicholas等人[9]提出一種高級函數(shù)查詢語言(HIFUN)，但沒有給出函數(shù)查詢的形式化定義，也沒有對函數(shù)查詢的結構特征及復雜性問題進行研究。函數(shù)查詢的結構特征是分析查詢解答復雜性的基礎，本文以關系數(shù)據(jù)模型為對象，對經(jīng)典的關系數(shù)據(jù)庫進行了擴充定義。在此基礎上，給出函數(shù)查詢的形式化定義，分析函數(shù)查詢的可計算性，用一階語言描述函數(shù)查詢，并證明函數(shù)查詢的結構是一階查詢層次結構。

1 擴充數(shù)據(jù)庫及函數(shù)查詢

文獻[10]對數(shù)據(jù)庫的結構特征進行了詳細分析并且給出了經(jīng)典結論，但在其數(shù)據(jù)庫的定義中忽略了屬性的描述，因此該定義不適用于函數(shù)查詢的結構特征研究。本文針對文獻[8]中數(shù)據(jù)庫的定義進行擴充，文獻[10]關于數(shù)據(jù)庫的定義如下。

例1舉出一個數(shù)據(jù)庫B的實例。論域U= {2,3,4,5}，數(shù)據(jù)庫B= (D,R1,R2)，D= {2, 3, 4, 5}，R1= {(2, 5), (4, 2), (4, 3), (5, 2)} ?DD，R2= {4, 2} ?D，見表1、表2。k= 2，a1= 2，a2= 1。

表1 例1中的關系R1

表2 例1中的關系R2

以上定義的不足之處是沒有給出屬性的描述，為了擴充數(shù)據(jù)庫的定義，把屬性看作函數(shù)。給出屬性的形式化定義如下。

(1)

其中，l表示行號，i表示列號，ti是一個如下形式的函數(shù)：

ti:ROCO→D，

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

(2)

其中，l表示行號，i表示列號，eti是一個如下形式的函數(shù)：

eti:Dc→U，

其中，Dc表示Attj中某些屬性的屬性值的笛卡爾積。由函數(shù)eti確定屬性EAi的屬性值。

擴充數(shù)據(jù)庫的定義如下。

例2舉一個擴充數(shù)據(jù)庫Bf的實例。論域U= {2, 3, 4, 5, 6, 7}，擴充數(shù)據(jù)庫Bf= (D,R1,R2,S1,S2)，其中D= {2, 3, 4, 5}，R1= {(2, 5, 7), (4, 2, 6), (4, 3, 7), (5, 2, 7)} ?UUU，R2= {(4, 6), (2, 3)} ?UU，關系R1、R2分別見表3、表4。S1= {A1,A2,EA1}，S2= {A3,EA2}。k= 2，(a1+1) = (2+1)， (a2+1) = (1+1)。其中擴充屬性集EAtt= {EA1,EA2}。

表3 例2中的關系R1

表4 例2中的關系R2

下面給出函數(shù)查詢的形式化定義。

滿足以下條件：

(1)Qf滿足部分遞歸。

(2) 如果Qf(Bf)有定義，Qf(Bf)?Ub且Qf(Bf)是有限的。

(3) 如果函數(shù)查詢滿足：函數(shù)查詢是部分遞歸并且滿足一致性條件：如果BfhBf，那么Qf(Bf) =h(Qf(Bf))，那么函數(shù)查詢是可計算的。

補操作與組合操作是查詢中的2個基本操作，現(xiàn)給出函數(shù)查詢中補操作和組合操作的定義。

(3)

C= {Qf|QfC}，

(4)

例3已知有例2所示的擴充數(shù)據(jù)庫Bf= (D,R1,R2,S1,S2)，以及擴充數(shù)據(jù)庫Bf上的函數(shù)查詢Qf，如果查詢結果的秩b= 2，那么函數(shù)查詢Qf可以表示為：

Qf:{Bf= (D,R1,R2,S1,S2)}2(UU)

函數(shù)查詢Qf的查詢結果見表5。

表5 Qf的查詢結果

Qf(Bf) = {(7, 4), (6, 2), (7, 2)}

(5)

例4舉出一個擴充數(shù)據(jù)庫Bf的實例。論域U= {2, 3, 4, 5, 6, 7, 12, 15}，擴充數(shù)據(jù)庫Bf= (D,R1,R2,R3,S1,S2,S3)，其中D= {2, 3, 4, 5, 6}，R1= {(2, 5, 7), (4, 2, 6), (4, 3, 7), (5, 2, 7)} ?UUU，R2= {(2, 4, 6), (4, 2, 3)} ?UUU，R3= {(3, 5, 15), (2, 6,12)} ?UUU，關系R1、R2、R3分別見表6～表8。S1= {A1,A2,EA1}，S2= {A1,A3,EA2}，S3= {A2,A4,EA3}。即k= 3，(a1+1) = (a2+1) = (a3+1) = (2+1)。

表6 例4中的關系R1

表7 例4中的關系R2

表8 例4中的關系R3

已知有如上擴充數(shù)據(jù)庫Bf,Bf上的函數(shù)查詢Qf，Qf1，Qf 2，其類型分別為(1，1)2，(2+1)1，(2+1)則的查詢結果見表9。

表的查詢結果

2 函數(shù)查詢層次結構

查詢語言是用來描述查詢的工具[11]，為了從理論上研究查詢問題，人們通常使用一階語言描述查詢[10]。本文的研究也是基于一階語言，下面給出描述函數(shù)查詢的一階查詢語言的定義。

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

(6)

例5如下表達式:

(x,s2)(R1,R2)(y)(R1(x,y,s1) ∧R2(y,s2))

定義8 一階查詢QfM記為由M表示的函數(shù)查詢，MFO，QfW= {QfM|MW}，W?FO。集合QFO是一階查詢的集合，并用F表示。

例6令M為(x,s2)(R1,R2)(y)(R1(x,y,s1) ∧R2(y,s2))，則M為(x,s2)(R1,R2)(y)(R1(x,y,s1) ∨R2(y,s2))。

引理1對于任意MFO，有Qf(M)=QfM，對于任意W?FO，有Qf(W)=QfW。

同樣地，定義替換操作類比函數(shù)查詢中的組合操作。

例7令M=s1.(T1,T2).(y)(T1(x,y,s1) ∧T2(y,s2))，N1= (y,s4,z).(R1,R2).(w)(R1(y,z,s3) ∨R2(w,z,s4))，N2= (u,s6).(R1,R2).(y)(R1(u,u,s5) ∧R2(u,y,s6))，那么M°=s1.(R1,R2).(y)((w)(R1(s1,s1,s3) ∨R2(w,s1,y)) ∧ (z)(R1(s1,s1,s5) ∧R2(s1,z,y)))。

定義11對于集合W，V?FO，其組合操作記為W°V= {M° (N1,N2, ... ,Nn) |MW，NiV，1≤i≤k}。

易證得出研究引理，詳見如下。

引理2對于任意M，(N1,N2, ... ,Nn)FO，有Qf(M° (N1,...,Nn))=QfM°Qf(N1,...,Nn)。對于任意集合W，V?FO，有Qf(W ° V)=QfW°QfV。

定義12 存在查詢EX表示如下形式的表達式集合：

引理3對于任意函數(shù)查詢集合C，有：

C∪C?E°C=E°C=E° (C∪C)

證明函數(shù)查詢是函數(shù)。令C1為集合C中的任一函數(shù)查詢，其定義域為D1，值域為Rn1，則C1的定義域為D1，值域為Rn1，令E1為集合E中的任一存在性函數(shù)查詢，其定義域為D2，值域為Rn2。那么有：

(E1°C1):D1Rn2，

(E1°C1):D1Rn2，

(E1° (C1∪C1)):D1Rn2，

綜上所述，引理3成立。

本文將屬性視為函數(shù)，對數(shù)據(jù)庫重新定義，經(jīng)過研究發(fā)現(xiàn)，函數(shù)查詢的層次結構與多項式時間層次結構[12]、一階查詢層次結構[10]等已知層次結構相似。

下面給出表達式集合的層次結構的定義，由此引出函數(shù)查詢集合的層次結構。

定義13 表達式層次結構表達式集合FO的集合{∑i，Γi}i<ω定義如下：

(2)∑i+1=EX°Γi，

(3)Γi=∑i，

由引理1～3可以得出：

引理4令0(與0相等)記為一階語言L中無量詞的表達式集合，i+1(分別為i+1)記為(則對應于(形式的表達式集合，其中Ψ在i(對應于i)中且在Ψ中是自由的，那么：

證明(1) 當i= 0時，0為一階語言L中無量詞的表達式集合，∑0為|Ψ無量詞}，由定義可知i=0時成立。令Ψ表示((Θ表示或者)，Ψi+1。令N表示i。假設N在Γi中，令M表示則M在EX中，M°N在中，由定義可知M°N在∑i+1中。由公式i+1推導出Γi中的表達式的證明類似。

關系查詢語言主要有2種類型，一種是邏輯語言，比如關系演算，由公式組成；另一種為代數(shù)語言，比如關系代數(shù)，由程序組成，其基本操作是代數(shù)(如連接和投影)[13]。文獻[14]證明了關系演算與關系代數(shù)在語言表達能力上的等價性。因此，一階查詢層次結構同樣可以對前述定義的集合進行投影來定義。如果用P表示如下形式的表達式的投影查詢集合：

(7)

那么，可以得出：

由引理4還可以得出結論：一階層次結構可以精確描述一階查詢集合F。

組合可以看作是執(zhí)行查詢、保存查詢結果中間值的一種方式，任何可以將查詢結果存儲在數(shù)據(jù)庫中的查詢語言，都可以計算一階查詢[10]。組合是文獻[15]中計算所有一階查詢的方式，因此組合具有文獻[2]中提到的完備性。

定理3對于任意的i以及擴充數(shù)據(jù)庫Bf= (D,R1,R2, ... ,Rk,S1,S2, ... ,Sk)，其中Bf中的關系Ri{ }并且RiDai+1，集合N|N∑i并且QfN(Bf)}在中是完備的。

(1) 首先證明G如引理4(2)的證明，任意N∑i，N可以轉化為等價的表達式其中關系具有擴充的屬性的關系，Φ是無量詞的，并且轉化過程中其符號數(shù)量沒有增加。那么當且僅當(存在適當?shù)亩囗検絧oly)：

(8)

令T是Bf中的關系，T{ }且TDai+1。給定如下形式的量化布爾公式Ψ:

其中,Pi,ki是命題符號。當且僅當Ψ為真時， ((),N)G成立。其中N為表達式：().∑i。由量化布爾公式的完備性[12]可以得出G在中的完備性[10]。

類似證明見文獻[10,17]。

文獻[18]從類型角度給出相似證明，其證明2個長度相同的量化前綴在有限數(shù)據(jù)庫上沒有相同的表達能力。例如公式邏輯上不等于任何公式，反之亦然。

3 結束語

大數(shù)據(jù)環(huán)境下函數(shù)查詢解答的復雜度問題是制約大數(shù)據(jù)查詢的瓶頸，解決該問題的關鍵首先是了解函數(shù)查詢的層次結構特征。本文的研究成果為下一步研究基于函數(shù)查詢結構特征的查詢解答復雜度分析奠定理論基礎。