大數據背景下關于函數查詢解答的復雜度研究

呂鵬輝

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

引言

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

1 基于函數查詢，問題解答的可計算性

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

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

2 基于函數查詢，問題解答的復雜度

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

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

3 結束語

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