呂鵬輝
天津凱立達(dá)眾創(chuàng)空間孵化器有限公司 天津 300000
對(duì)于大數(shù)據(jù)應(yīng)用而言,函數(shù)查詢是重要操作。即便是查詢較為簡(jiǎn)單的線性,基于大數(shù)據(jù)背景,查詢所需時(shí)間是人們難以接受的,遠(yuǎn)超過人們可接受的范圍;在大數(shù)據(jù)時(shí)代下,對(duì)于P類函數(shù)查詢,存在較大的困難,是難以進(jìn)行處理的。對(duì)于傳統(tǒng)查詢而言,主要基于數(shù)據(jù)庫,是一個(gè)從其至關(guān)系的函數(shù),然而,沒有包括查詢函數(shù)本身情況[1]。
問題解釋:已知函數(shù)查詢Qf,同時(shí)獲知擴(kuò)充數(shù)據(jù)庫Bf,試問對(duì)于該查詢計(jì)算機(jī)而言,能否進(jìn)行計(jì)算。依據(jù)相關(guān)計(jì)算理論得知,對(duì)于判斷某一問題能否計(jì)算,可將問題進(jìn)一步轉(zhuǎn)化,來判定該問題是否屬于語言問題范疇,由此,可將問題進(jìn)行如下轉(zhuǎn)化:得知語言F={
引理一,若某一語言E={B,Q(B)>}是可以進(jìn)行判定的,在B中,Q(B)是可進(jìn)行解答查詢的,B作為數(shù)據(jù)庫。引理2。若語言Lg1小于或者等于m Lg2,再加上可對(duì)Lg2進(jìn)行判定,那么亦可對(duì)語言Lg1進(jìn)行判定。定理一。若某一語言F={
現(xiàn)如今,存在諸多復(fù)雜類,比如NPTIME、PSPACE and LOGSPACE and so on。對(duì)于查詢解答的復(fù)雜,主要介紹2種方式,一種是表達(dá)復(fù)雜度,另一種是數(shù)據(jù)復(fù)雜度,接下來對(duì)這兩種衡量方法進(jìn)行闡述。對(duì)于數(shù)據(jù)復(fù)雜度而言,第一步需對(duì)函數(shù)查詢進(jìn)行明確,之后把查詢使用至任何一個(gè)數(shù)據(jù)庫中,之后結(jié)合數(shù)據(jù)庫函數(shù),來對(duì)數(shù)據(jù)復(fù)雜度進(jìn)行判定。對(duì)于表達(dá)復(fù)雜度而言,首先需對(duì)數(shù)據(jù)庫進(jìn)行確定,基于查詢語言,來對(duì)其任何一個(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)系,對(duì)于關(guān)系Ri而言,在上下文中可找出其元數(shù)。把First視為一種語言,由下述表達(dá)式構(gòu)成,具體而言,。在其中,ψ是一階函數(shù)的公式,表示不一樣的變量向量,在其中,包括ψ公式中的全部變量;表示不一樣的謂詞符號(hào),在其中,包括ψ公式中的全部關(guān)系。對(duì)于函數(shù)查詢而言,可借助于First語言來進(jìn)行表達(dá)。
若存在絕對(duì)值等于b,關(guān)系符號(hào)的秩為ai+1,可得First的表達(dá)式,也就是,其中代表一種函數(shù)查詢,并記為Qf。定理二,對(duì)于first語言而言,其數(shù)據(jù)復(fù)雜度是LOGSPACE,也就是對(duì)數(shù)空間復(fù)雜性,其表達(dá)復(fù)雜度為PSPACE,具體而言,也就是多項(xiàng)式復(fù)雜性。對(duì)于函數(shù)查詢而言,其實(shí)質(zhì)就是一種函數(shù),基于某一個(gè)元組查詢難度,來對(duì)函數(shù)查詢的復(fù)雜進(jìn)行衡量。對(duì)于first語言數(shù)據(jù)復(fù)雜度而言,是表達(dá)式集合Gr(Qf)的復(fù)雜度。對(duì)于first語言而言,其表達(dá)復(fù)雜度為集合Grfirst(Bf)的復(fù)雜度。基于大數(shù)據(jù)環(huán)境,對(duì)于以往P類問題而言,始終是較難的問題。例如對(duì)于掃描類查詢而言,如其數(shù)據(jù)量為1PB時(shí),完成結(jié)果的查詢,所需時(shí)間大概為1.9天。所以,以往對(duì)查詢復(fù)雜度的分析,難以滿足大數(shù)據(jù)解答[3]。
通過以上的分析可以得知,對(duì)于數(shù)據(jù)復(fù)雜度而言,第一步需對(duì)函數(shù)查詢進(jìn)行明確,之后把查詢使用至任何一個(gè)數(shù)據(jù)庫中,之后結(jié)合數(shù)據(jù)庫函數(shù),來對(duì)數(shù)據(jù)復(fù)雜度進(jìn)行判定;對(duì)于函數(shù)查詢而言,可借助于First語言來進(jìn)行表達(dá);基于大數(shù)據(jù)環(huán)境,對(duì)于以往P類問題而言,始終是較難的問題;對(duì)于傳統(tǒng)查詢而言,主要基于數(shù)據(jù)庫,是一個(gè)從其至關(guān)系的函數(shù),并沒有包括查詢函數(shù)本身情況;在大數(shù)據(jù)應(yīng)用過程中,函數(shù)查詢是關(guān)鍵環(huán)節(jié),在數(shù)據(jù)庫理論問題中,查詢解答問題是重要問題。