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

呂鵬輝

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

引言

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

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

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

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

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

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

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

3 結(jié)束語

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