本站小編為你精心準備了視圖確定性問題研究參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《計算機工程與應用雜志》2014年第十四期

1問題描述

1.1視圖確定性視圖確定性問題形式化描述為：給定模式R上的一個查詢Q和一組視圖V如果對于R上的任意兩個數據庫實例D1和D2都有V(D1)=V(D2)蘊含Q(D1)=Q(D2)則稱視圖V確定查詢Q。實際上，如果確定性成立，則可以找到一個算法，對每一個視圖查詢實例I=V(D)返回Q的查詢結果Q(D)。算法描述如下：按照某一順序遍歷模式R上的數據庫實例；假設當前遍歷的數據庫為D′首先判斷V(D′)=I是否成立，若成立，則計算Q(D′)并結束，否則繼續遍歷。一方面，因為V確定Q如果V(D′)=I=V(D)則必有Q(D′)=Q(D)保證了算法的正確性；另一方面，總能夠找到一個數據庫D′（例如D′=D）使得V(D′)=I=V(D)保證了算法的終止性。因此，如果視圖V確定查詢Q則必存在一個算法利用視圖V計算出Q的查詢結果，也即從理論上保證視圖V含有足夠的信息來回答查詢Q。

1.2查詢重寫與基于視圖的查詢回答相關的另一個問題是基于視圖的查詢重寫（QueryRewriting），形式化描述如下：給定模式R上的一個查詢Q和一組視圖V以及查詢語言類L如果存在一個查詢PÎLP僅對V中的視圖進行訪問并且對于R上的任意數據庫D都有Q(D)=P(V(D))則稱Q能夠使用V在語言L中查詢重寫。顯然，如果Q能使用V在某一語言類L中進行查詢重寫，則V必定確定Q；反之不一定成立，因為查詢重寫和重寫語言L的表達能力有關。換言之，查詢重寫其實是從語法的角度回答“如何形式化地描述一組視圖V含有足夠的信息來回答一個查詢Q”這一問題。如果Q能使用V在某一語言類L中進行查詢重寫，則V必定含有足夠的信息回答Q。但是查詢重寫限定了重寫的語言類L如果Q不能使用V在語言類L內進行重寫，并不能說明V中的信息不足以回答Q因為很有可能是由于L的表達能力太弱而不能夠表達出利用V計算Q的算法（或稱可計算函數）。實際上，文獻[9-11]均舉例指出，對于一個合取查詢Q和一組使用合取查詢描述的視圖V不存在Q使用V的合取查詢重寫，但是存在一個一階邏輯查詢可以利用V計算出Q。

1.3語言完全性根據查詢重寫和視圖確定性之間的關系，Segoufin等人[8]提出重寫語言完全性（Completeness）的概念：給定查詢定義語言類LQ和視圖定義語言類Lv稱語言類L對于LV到LQ的查詢重寫（記作LV-to-LQ）是完全的，當且僅當對于LQ中的任意查詢Q和Lv中的任意一組視圖V如果V確定Q則存在一個Q使用V在語言L中的查詢重寫P。語言完全性實質上是說如果視圖確定性成立，則依靠該語言類的表達能力足夠描述利用視圖計算查詢結果的算法（或稱可計算函數）。

2研究維度

視圖確定性相關的研究主要圍繞以下兩個問題展開：（1）給定一個查詢Q和一組視圖V是否有V確定Q?（2）給定查詢定義語言類LQ和視圖定義語言類Lv對于LV到LQ的查詢重寫完全的語言類是什么?其中第一個問題屬于判定問題，主要考慮問題的判定性以及判定復雜度。一般來說，問題的判定復雜度和輸入參數所屬語言類的表達能力之間存在著制約關系。例如，上下文無關語言的包含判定是不可解的[12]，但是正則語言（使用正則表達式表示時）的包含判定問題則可以在PSPACE內解決[13]，進一步縮小到確定性正則語言時判定復雜度可以降低為PTIME[14]。因此，對于視圖確定性問題的判定復雜度按照輸入參數即查詢Q和視圖V所屬的不同語言類LQ和LV來進行分析。第二個問題本質上屬于證明性問題，一般解決思路是先猜測一個語言類L然后嚴格證明L對LV到LQ的查詢重寫是完全的。同樣，猜測的語言類L與輸入參數LQ和LV有關。一般而言，LQ和LV的表達能力越強，其完全語言類L的表達能力也越強。因此，與第一個判定問題類似，尋找查詢重寫完全語言類也按照不同語言類LQ和LV來進行。關系數據庫中常見的查詢語言是SQL（StructuredQueryLanguage）。其表達式基本結構包括三個子句：select子句、from子句和where子句，分別對應于關系代數中的投影、笛卡爾積和選擇謂詞。另外兩種具有影響力的商業語言是QBE和Quel，以及一種在系統研究中使用的語言Datalog。QBE基于域關系演算，Quel基于元組關系演算，Datalog基于邏輯編程語言Prolog[15]。判定問題主要考慮查詢語言的表達能力，只關注這些商業語言的底層理論基礎，因此需要從理論的角度對查詢進行刻畫。理論上，關系查詢可以從邏輯（Logic）、規則（Rule）和代數（Algebra）三個角度進行定義。例如，給定模式R=(R1R2)關系R1和R2的元數均為2，要求查詢R1的第二列和R2的第一列相同的那些元組，返回R1的第一列和R2的第二列。該查詢從以上三個角度分別定義如下。視圖確定性問題的研究主要考慮以下幾類查詢語言：合取查詢（CQ）、并合取查詢（UCQ）、一階邏輯查詢（FO）和Datalog查詢。這些語言的具體定義參見文獻[16]，此處只簡單從邏輯和代數的角度給出其描述，如表1所示。其中與Datalog對應的RE算子表示遞歸，也即Datalog是在UCQ的基礎上增加了一個不動點（Fixpoint）操作。合取查詢從關系代數的角度而言是指只使用選擇（Selection）、投影（Projection）和笛卡爾乘積（CartesianProduct）操作構成的一類查詢，因此又稱為選擇-投影-乘積（簡稱SPC）查詢。視圖確定性問題的研究中還考慮合取查詢的如下幾個特殊子類：SP查詢，僅有選擇和投影操作構成的查詢；PC查詢，僅有投影和乘積操作構成的查詢；SC查詢，僅有選擇和乘積操作構成的查詢。除了從輸入參數所屬不同語言類進行劃分外，視圖確定性問題還從以下兩個角度進行研究：單個視圖vs多個視圖：單個視圖是指視圖V中只含有一個，換言之，視圖定義中只有一條查詢語句。即使對于最簡單的合取查詢CQ，單個視圖下的和多個視圖下的視圖確定性問題是否等價尚未可知[10]。因此研究時往往從比較簡單的單個視圖情況開始，繼而擴展到多個視圖情況下。下文中如未特別指出均指的是多個視圖情況下。無限制數據庫vs有限制數據庫：無限制（unrestricted）數據庫沒有限制數據庫實例必須是有限的（即數據庫中的元組可以無限），有限制（restricted）數據庫則相反。實際使用中的數據庫實例都是有限的，但是在理論研究時允許有無限數據庫實例的情況，而且往往這種情況下問題證明會變得比較簡單，因為在進行構造證明時可以向構造的數據庫中添加任意需要的元組而不用考慮最終構造的數據庫是否會違反無限性。視圖確定性問題的研究大多都是針對有限制的情況，在下文中除非特別說明均指有限制情況下。

3研究進展

視圖確定性問題由Segoufin和Vianu于2005年首次提出，之后得到眾多數據庫理論方面研究學者的持續關注。下面總結已有的主要研究成果以及未解決的開放性問題。

3.1不可判定的情況Segoufin和Vianu[8]利用一階邏輯的可滿足性以及有效性問題進行歸約，證明出當視圖語言或者查詢語言是一階邏輯查詢（FO）時，視圖確定性問題是不可判定的。并且，一階邏輯對于一階邏輯到一階邏輯的查詢重寫（FO-to-FO）是不完全的，也即，對于一個一階邏輯查詢Q和一組一階邏輯視圖V如果V確定Q則不一定仍舊存在一個一階邏輯查詢P使得對于任意數據庫實例D有Q(D)=P(V(D))。實際上，任何一種對FO-to-FO查詢重寫完全的語言必須是圖靈完全的。但是在無限制數據庫的情況下，一階邏輯對于一階邏輯到一階邏輯的查詢重寫（FO-to-FO）是完全的。Segoufin和Vianu[8]同時指出當視圖語言和查詢語言都是并合取查詢（UCQ）時，視圖確定性問題是不可判定的。即使視圖V是固定的，該問題仍舊是不可判定的。證明利用有限幺半群上的字問題進行歸約。并合取查詢對于并合取查詢到并合取查詢的查詢重寫（UCQ-to-UCQ）是不完全的。實際上，任何一種對于UCQ-to-UCQ查詢重寫完全的語言都是非單調的。查詢語言的單調性是指對于該語言中的任意查詢Q和任意數據庫實例D1、D2如果D1ÍD2則Q(D1)ÍQ(D2)。已知并合取查詢和合取查詢都是單調的[16]，而一階邏輯查詢是非單調的。Nash和Segoufin等人[8，10]指出對于UCQ-to-UCQ查詢重寫完全的語言的表達能力位于存在二階邏輯($SO)和任意二階邏輯("SO)[17]之內，但是仍不知道是否位于一階邏輯之內。Fan等人[18]考慮Datalog查詢語言類，利用Datalog查詢包含問題歸約證明出當查詢語言類是Datalog、視圖語言類是CQ或者相反地，當視圖語言類是Datalog、查詢語言類是CQ時，視圖確定性問題都是不可判定的。但是沒有分析有關Datalog查詢重寫相關的完全語言類。

3.2合取查詢的可判定子類合取查詢是一類使用比較廣泛并且較為簡單的查詢語言。Nash等人[10]證明出，與并合取查詢類似，任何一種對于合取查詢到合取查詢的查詢重寫（CQ-to-CQ）完全的語言都是非單調的，因此，合取查詢對于CQ-to-CQ查詢重寫是不完全的。但是如果已知查詢重寫P本身是單調的，則P可用合取查詢來表達，也即在這種情況下，CQ對于CQ-to-CQ查詢重寫是完全的。但是合取查詢的視圖確定性問題是否是可判定的至今尚不知道，并被指出具有相當難度和挑戰性[9-10]。視圖確定性問題的后續研究大多集中于合取查詢的可判定子類上。Nash、Segoufin和Vianu[9-10]給出了合取查詢的幾種特殊情況，對于這些特殊情況，視圖確定性問題是可判定的，并且合取查詢對于CQ-to-CQ查詢重寫仍舊是完全的。（1）當查詢是合取查詢，視圖是布爾合取查詢（BoolCQ）時。布爾合取查詢是指不含自由變量的查詢，其查詢結果只有“真”和“假”兩個值。例如定義在二元關系R上的如下查詢是布爾查詢：q()¬R(xx)R(ab)。（2）當查詢是合取查詢，視圖是一元合取查詢（MonadicCQ）時。一元合取查詢是指含有一個自由變量的查詢。例如定義在二元關系R1和R2上的如下查詢是個一元合取查詢：q(x)¬R1(xa)R2(bx)。（3）當查詢是合取查詢，視圖是單個的路徑合取查詢（PathCQ）時。路徑合取查詢是指定義在單個二元關系R上的具有如下形式的合取查詢：q(xy)¬R(xx1)R(x1x2)R(xk-1xk)R(xky)。Afrati[11，19]指出當查詢是合取查詢，視圖是完全合取查詢（FullCQ）時，視圖確定性問題是可判定的，并且合取查詢對于CQfull-to-CQ的查詢重寫是完全的。完全合取查詢是指不含有受限變量的合取查詢。例如，SC查詢即是典型的完全合取查詢。當查詢和視圖都是鏈合取查詢（ChainCQ）時，視圖確定性問題是可判定的，并且一階邏輯FO對于CQchain-to-CQchain的查詢重寫是完全的。鏈合取查詢是路徑合取查詢的擴展，其形式與路徑合取查詢的形式相同，但是允許定義在多個二元關系上。Pasailä[20]在Afrati的基礎上進一步指出當查詢是鏈合取查詢，視圖是連通圖合取查詢（ConnectedGraphCQ）時，視圖確定性問題是可判定的，并且在查詢最小化的情況下可在多項式時間內判定。一階邏輯FO對于CQchain-to-CQcgraph的查詢重寫是完全的。這里的連通圖合取查詢是指定義在二元關系上，只含有兩個自由變量并且滿足如下條件的合取查詢：當將查詢的體部看作一個無向圖時，圖是聯通的。體部無向圖定義為：以查詢中的變量為結點，結點x和y之間存在邊當且僅當查詢體部（即定義規則中）中存在R(xy)或者R(yx)其中R是任意一個二元關系符號。連通圖合取查詢是對鏈合取查詢的一種擴展，后者的體部無向圖實際上構成了一條連接兩個自由變量的簡單無環路徑。例如，如下定義的查詢Q1是鏈合取查詢，Q2是連通圖合取查詢但不是鏈合取查詢。q1(xy)¬R1(xz1)R2(z1z2)R1(z2y)q2(xy)¬R1(xz1)R2(z1z2)R1(z2z3)R2(z3z1)R1(z1y)當查詢和視圖都是連通圖合取查詢時，Pasailä給出了一個滿足視圖確定性的必要非充分條件，但是其判定性仍舊沒有解決。Zheng等人[21]證明出當查詢和視圖都是定義在一元模式上的合取查詢（unaryCQ）時，視圖確定性問題可在PTIME時間內判定，并且合取查詢對于CQunary-to-CQunary的查詢重寫是完全的。他們同時給出一個O(|Q||V|)復雜度的判定算法，其中|Q|和|V|分別指查詢Q和視圖V的大小，大小根據Q和V中出現的變量和常量的個數決定。這里的一元模式是指關系模式中的每個關系都是一元的，即只含有一個屬性。Fan等人[18]考慮合取查詢的三個特殊子類SP、PC和SC查詢，證明出當查詢Q是合取查詢，視圖V分別是SP、PC和SC查詢時，視圖確定性問題的判定復雜度分別是NP完全、PTIME和NP完全的。若查詢Q是最小化的，則在視圖V為SP查詢的情況下，判定復雜度會降低為PTIME。對于這三種情況，合取查詢對于查詢重寫而言仍舊是完全的。一個合取查詢Q是最小化的當且僅當不存在一個查詢Q′滿足Q與Q′等價并且Q′的規模（大小）比Q小。Marx[22]考慮一階邏輯查詢的一個子類，稱作Packed一階邏輯（記作PF），證明出對于這類查詢，視圖確定性問題是可判定的，并且PF對于PF-to-PF查詢重寫是完全的。當限定在合取查詢上時，也即Packed合取查詢（記作PCQ），結論仍舊成立。

3.3存在的問題目前，視圖確定性問題相關研究的最大開放性問題是關于合取查詢的判定性以及判定復雜度。合取查詢是一類使用比較廣泛并且較為簡單的查詢語言，但是不管是在無限制數據庫情況下還是有限制數據庫情況下，其視圖確定性問題至今尚為解決，具有相當難度和挑戰性。而且，在這兩種情況下視圖確定性問題是否等價也尚未可知。一種猜測是在無限制數據庫情況下，問題是可判定的；在有限制數據庫情況下則相反[10]。但是該猜測尚未得以證實。另外一個開放性問題是在有限制數據庫情況下對于CQ-to-CQ查詢重寫完全的語言類是什么?已知對于UCQ-to-UCQ查詢重寫完全的語言的表達能力位于存在二階邏輯($SO)和任意二階邏輯("SO)之內[8]。由于CQ的表達能力弱于UCQ，可以推知對于CQ-to-CQ查詢重寫完全的語言類其表達能力的上限是存在二階邏輯($SO)與任意二階邏輯("SO)的交集，但下限是什么至今還不知道。表2總結了視圖確定性問題已有的研究成果和存在的開放性問題。表中主要給出的是有限制數據庫的情況。目前為止，視圖確定性問題的研究都是理論方面的，主要關注判定復雜度。從實際應用的角度來講，設計和實現高效的判定算法也應該是一個重要的研究方向。應用研究可以從兩個方面著手：（1）對于在理論研究中已經證明出的可判定的情況，設計盡可能高效的算法，并進行實現和實驗；（2）對于理論上證明出不可判定的情況，尋找其可判定的子類。語言的表達能力和判定復雜度之間往往存在著制約關系，表達能力越強的語言類，其判定復雜度越高甚至是不可判定的。但是，實際應用中常見的查詢定義或者視圖定義往往對應于受限的表達能力。例如，關系查詢中一階邏輯的表達能力要強于合取查詢，但是常用到的是合取查詢（即簡單的SQL語句）。因此，尋找可判定或者判定復雜度較低但是在實際應用中常見的語言子類是很有意義的。同樣地，對于找到可判定子類，也要設計盡可能高效的算法。視圖確定性判定算法可應用于所有基于視圖的查詢回答中。如果通過判定算法已知確定性不成立，則說明視圖所含信息不足以回答查詢，因此沒有必要進一步尋找查詢重寫或查詢回答的算法。

4結束語

基于視圖的查詢回答中一個基本的問題是：如何形式化地描述一組視圖V含有足夠的信息來回答一個查詢Q。“視圖確定性”是從信息理論的角度回答該問題而提出的一個新概念。本文對視圖確定性問題的研究及進展進行了較全面的論述。視圖確定性問題是一個相對比較新的研究問題，目前為止的研究都是針對關系型數據，大部分集中在證明問題的判定復雜度和尋找可判定的合取查詢子類方面。隨著Web應用的發展，出現了大量的半結構化數據，典型代表是XML[23]數據。XML因其結構簡單靈活、允許用戶自定義標記、具有良好的可擴展性等優點，在推出的短短幾年內已被廣泛應用于電子商務、B2B通信、企業信息交換/集成、Web服務等應用中，成為網絡環境下進行數據、數據交換和數據集成的標準格式。因此，對于XML數據上相關問題的研究也將具有重要的意義。目前尚未發現有關XML數據上視圖確定性問題的研究成果發表。文中已指出視圖確定性問題與查詢重寫問題比較相近，但并不等價。因此，盡管目前對XML數據上的查詢重寫有大量的研究[24-26]，但是其成果并不能擴展到XML數據的視圖確定性問題上。解決關系型數據上的遺留問題以及由關系型數據擴展到XML數據將會是視圖確定性問題的后序研究重點。

作者：鄭黎曉常青玲徐世廷單位：華僑大學計算機科學與技術學院 中國科學院計算機網絡信息中心中國科學院大學