關(guān)系數(shù)據(jù)模型中函數(shù)查詢的結(jié)構(gòu)特征

吳文莉， 劉國華,

(1 東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 201620; 2 上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室(復(fù)旦大學(xué))， 上海 201203)

0 引 言

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

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

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

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

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

例1舉出一個(gè)數(shù)據(jù)庫B的實(shí)例。論域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中的關(guān)系R1

表2 例1中的關(guān)系R2

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

(1)

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

ti:ROCO→D，

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

(2)

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

eti:Dc→U，

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

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

例2舉一個(gè)擴(kuò)充數(shù)據(jù)庫Bf的實(shí)例。論域U= {2, 3, 4, 5, 6, 7}，擴(kuò)充數(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，關(guān)系R1、R2分別見表3、表4。S1= {A1,A2,EA1}，S2= {A3,EA2}。k= 2，(a1+1) = (2+1)， (a2+1) = (1+1)。其中擴(kuò)充屬性集EAtt= {EA1,EA2}。

表3 例2中的關(guān)系R1

表4 例2中的關(guān)系R2

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

滿足以下條件：

(1)Qf滿足部分遞歸。

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

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

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

(3)

C= {Qf|QfC}，

(4)

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

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

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

表5 Qf的查詢結(jié)果

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

(5)

例4舉出一個(gè)擴(kuò)充數(shù)據(jù)庫Bf的實(shí)例。論域U= {2, 3, 4, 5, 6, 7, 12, 15}，擴(kuò)充數(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，關(guān)系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中的關(guān)系R1

表7 例4中的關(guān)系R2

表8 例4中的關(guān)系R3

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

表的查詢結(jié)果

2 函數(shù)查詢層次結(jié)構(gòu)

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

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

(6)

例5如下表達(dá)式:

(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表示如下形式的表達(dá)式集合：

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

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

證明函數(shù)查詢是函數(shù)。令C1為集合C中的任一函數(shù)查詢，其定義域?yàn)镈1，值域?yàn)镽n1，則C1的定義域?yàn)镈1，值域?yàn)镽n1，令E1為集合E中的任一存在性函數(shù)查詢，其定義域?yàn)镈2，值域?yàn)镽n2。那么有：

(E1°C1):D1Rn2，

(E1°C1):D1Rn2，

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

綜上所述，引理3成立。

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

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

定義13 表達(dá)式層次結(jié)構(gòu)表達(dá)式集合FO的集合{∑i，Γi}i<ω定義如下：

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

(3)Γi=∑i，

由引理1～3可以得出：

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

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

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

(7)

那么，可以得出：

由引理4還可以得出結(jié)論：一階層次結(jié)構(gòu)可以精確描述一階查詢集合F。

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

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

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

(8)

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

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

類似證明見文獻(xiàn)[10,17]。

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

3 結(jié)束語

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