大數(shù)據(jù)背景下關(guān)于函數(shù)查詢(xún)解答的復(fù)雜度研究

呂鵬輝

天津凱立達(dá)眾創(chuàng)空間孵化器有限公司 天津 300000

引言

對(duì)于大數(shù)據(jù)應(yīng)用而言，函數(shù)查詢(xún)是重要操作。即便是查詢(xún)較為簡(jiǎn)單的線(xiàn)性，基于大數(shù)據(jù)背景，查詢(xún)所需時(shí)間是人們難以接受的，遠(yuǎn)超過(guò)人們可接受的范圍；在大數(shù)據(jù)時(shí)代下，對(duì)于P類(lèi)函數(shù)查詢(xún)，存在較大的困難，是難以進(jìn)行處理的。對(duì)于傳統(tǒng)查詢(xún)而言，主要基于數(shù)據(jù)庫(kù)，是一個(gè)從其至關(guān)系的函數(shù)，然而，沒(méi)有包括查詢(xún)函數(shù)本身情況[1]。

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

問(wèn)題解釋?zhuān)阂阎瘮?shù)查詢(xún)Qf，同時(shí)獲知擴(kuò)充數(shù)據(jù)庫(kù)Bf，試問(wèn)對(duì)于該查詢(xún)計(jì)算機(jī)而言，能否進(jìn)行計(jì)算。依據(jù)相關(guān)計(jì)算理論得知，對(duì)于判斷某一問(wèn)題能否計(jì)算，可將問(wèn)題進(jìn)一步轉(zhuǎn)化，來(lái)判定該問(wèn)題是否屬于語(yǔ)言問(wèn)題范疇，由此，可將問(wèn)題進(jìn)行如下轉(zhuǎn)化：得知語(yǔ)言F=｛｝，在Bf解答中，Qf（Bf）是可以進(jìn)行函數(shù)查詢(xún)的，在式子中，Bf表示擴(kuò)充數(shù)據(jù)庫(kù)，某一串為，在Bf＇中，Qf＇（Bf＇）是函數(shù)查詢(xún)，Bf＇作為擴(kuò)充數(shù)據(jù)庫(kù)，通過(guò)以上已知條件，試問(wèn)是否含于語(yǔ)言F。定義1 ，映射的歸約性特點(diǎn)。若已知某一可計(jì)算函數(shù)，記為函數(shù)f:∑*指向于∑*，促使基于任何一個(gè)ω，都存在ω屬于Lg1，同時(shí)又等價(jià)于f（ω）屬于Lg2，則可基于語(yǔ)言Lg1，將其映射至Lg2，且記為語(yǔ)言Lg1小于或者等于m Lg2。此時(shí)由Lg1至Lg2，將函數(shù)f稱(chēng)為歸約。

引理一，若某一語(yǔ)言E=｛B，Q（B）>｝是可以進(jìn)行判定的，在B中，Q（B）是可進(jìn)行解答查詢(xún)的，B作為數(shù)據(jù)庫(kù)。引理2。若語(yǔ)言Lg1小于或者等于m Lg2，再加上可對(duì)Lg2進(jìn)行判定，那么亦可對(duì)語(yǔ)言Lg1進(jìn)行判定。定理一。若某一語(yǔ)言F=｛｝，在Bf解答中，Qf（Bf）是可以進(jìn)行函數(shù)查詢(xún)的，在式子中，Bf表示擴(kuò)充數(shù)據(jù)庫(kù)。求證，依據(jù)引理一可以得知，可對(duì)語(yǔ)言E進(jìn)行判定?；谡Z(yǔ)言E，將M設(shè)為其的判定器，從由語(yǔ)言F至語(yǔ)言E，將函數(shù)f稱(chēng)為歸約?；谡Z(yǔ)言F，其判定器描述如下，記為N：N等于查詢(xún)編碼，記為Qf，也就是：（1）對(duì)f（）進(jìn)行計(jì)算。（2）基于f（），來(lái)對(duì)判定器進(jìn)行運(yùn)行，隨之輸出判定器的輸出。從由語(yǔ)言F至語(yǔ)言E，將函數(shù)f稱(chēng)為歸約，若包含于語(yǔ)言F，則表明f（）含于語(yǔ)言E。所以，當(dāng)包含于語(yǔ)言F時(shí)，那么判定器可接受f（）。所以，通過(guò)查詢(xún)編碼的運(yùn)行，可對(duì)語(yǔ)言F進(jìn)行判定，具體而言，說(shuō)明語(yǔ)言F具有可判定性[2]。

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

現(xiàn)如今，存在諸多復(fù)雜類(lèi)，比如NPTIME、PSPACE and LOGSPACE and so on。對(duì)于查詢(xún)解答的復(fù)雜，主要介紹2種方式，一種是表達(dá)復(fù)雜度，另一種是數(shù)據(jù)復(fù)雜度，接下來(lái)對(duì)這兩種衡量方法進(jìn)行闡述。對(duì)于數(shù)據(jù)復(fù)雜度而言，第一步需對(duì)函數(shù)查詢(xún)進(jìn)行明確，之后把查詢(xún)使用至任何一個(gè)數(shù)據(jù)庫(kù)中，之后結(jié)合數(shù)據(jù)庫(kù)函數(shù)，來(lái)對(duì)數(shù)據(jù)復(fù)雜度進(jìn)行判定。對(duì)于表達(dá)復(fù)雜度而言，首先需對(duì)數(shù)據(jù)庫(kù)進(jìn)行確定，基于查詢(xún)語(yǔ)言，來(lái)對(duì)其任何一個(gè)表達(dá)式進(jìn)行查詢(xún)，之后結(jié)合表達(dá)式長(zhǎng)度，來(lái)給出相應(yīng)的復(fù)雜度。定義2，一階語(yǔ)言。將L視為一階語(yǔ)言，該語(yǔ)言不存在函數(shù)符號(hào)，有著相應(yīng)的等式，將R1，R2等視為關(guān)系符號(hào)。用Ri代表關(guān)系自身，或者表示關(guān)系，對(duì)于關(guān)系Ri而言，在上下文中可找出其元數(shù)。把First視為一種語(yǔ)言，由下述表達(dá)式構(gòu)成，具體而言，。在其中，ψ是一階函數(shù)的公式，表示不一樣的變量向量，在其中，包括ψ公式中的全部變量；表示不一樣的謂詞符號(hào)，在其中，包括ψ公式中的全部關(guān)系。對(duì)于函數(shù)查詢(xún)而言，可借助于First語(yǔ)言來(lái)進(jìn)行表達(dá)。

若存在絕對(duì)值等于b，關(guān)系符號(hào)的秩為ai+1，可得First的表達(dá)式，也就是，其中代表一種函數(shù)查詢(xún)，并記為Qf。定理二，對(duì)于first語(yǔ)言而言，其數(shù)據(jù)復(fù)雜度是LOGSPACE，也就是對(duì)數(shù)空間復(fù)雜性，其表達(dá)復(fù)雜度為PSPACE，具體而言，也就是多項(xiàng)式復(fù)雜性。對(duì)于函數(shù)查詢(xún)而言，其實(shí)質(zhì)就是一種函數(shù)，基于某一個(gè)元組查詢(xún)難度，來(lái)對(duì)函數(shù)查詢(xún)的復(fù)雜進(jìn)行衡量。對(duì)于first語(yǔ)言數(shù)據(jù)復(fù)雜度而言，是表達(dá)式集合Gr（Qf）的復(fù)雜度。對(duì)于first語(yǔ)言而言，其表達(dá)復(fù)雜度為集合Grfirst（Bf）的復(fù)雜度。基于大數(shù)據(jù)環(huán)境，對(duì)于以往P類(lèi)問(wèn)題而言，始終是較難的問(wèn)題。例如對(duì)于掃描類(lèi)查詢(xún)而言，如其數(shù)據(jù)量為1PB時(shí)，完成結(jié)果的查詢(xún)，所需時(shí)間大概為1.9天。所以，以往對(duì)查詢(xún)復(fù)雜度的分析，難以滿(mǎn)足大數(shù)據(jù)解答[3]。

3 結(jié)束語(yǔ)

通過(guò)以上的分析可以得知，對(duì)于數(shù)據(jù)復(fù)雜度而言，第一步需對(duì)函數(shù)查詢(xún)進(jìn)行明確，之后把查詢(xún)使用至任何一個(gè)數(shù)據(jù)庫(kù)中，之后結(jié)合數(shù)據(jù)庫(kù)函數(shù)，來(lái)對(duì)數(shù)據(jù)復(fù)雜度進(jìn)行判定；對(duì)于函數(shù)查詢(xún)而言，可借助于First語(yǔ)言來(lái)進(jìn)行表達(dá)；基于大數(shù)據(jù)環(huán)境，對(duì)于以往P類(lèi)問(wèn)題而言，始終是較難的問(wèn)題；對(duì)于傳統(tǒng)查詢(xún)而言，主要基于數(shù)據(jù)庫(kù)，是一個(gè)從其至關(guān)系的函數(shù)，并沒(méi)有包括查詢(xún)函數(shù)本身情況；在大數(shù)據(jù)應(yīng)用過(guò)程中，函數(shù)查詢(xún)是關(guān)鍵環(huán)節(jié)，在數(shù)據(jù)庫(kù)理論問(wèn)題中，查詢(xún)解答問(wèn)題是重要問(wèn)題。