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

《計(jì)算機(jī)工程與應(yīng)用雜志》2014年第十四期

1問(wèn)題描述

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

1.2查詢重寫(xiě)與基于視圖的查詢回答相關(guān)的另一個(gè)問(wèn)題是基于視圖的查詢重寫(xiě)（QueryRewriting），形式化描述如下：給定模式R上的一個(gè)查詢Q和一組視圖V以及查詢語(yǔ)言類L如果存在一個(gè)查詢PÎLP僅對(duì)V中的視圖進(jìn)行訪問(wèn)并且對(duì)于R上的任意數(shù)據(jù)庫(kù)D都有Q(D)=P(V(D))則稱Q能夠使用V在語(yǔ)言L中查詢重寫(xiě)。顯然，如果Q能使用V在某一語(yǔ)言類L中進(jìn)行查詢重寫(xiě)，則V必定確定Q；反之不一定成立，因?yàn)椴樵冎貙?xiě)和重寫(xiě)語(yǔ)言L的表達(dá)能力有關(guān)。換言之，查詢重寫(xiě)其實(shí)是從語(yǔ)法的角度回答“如何形式化地描述一組視圖V含有足夠的信息來(lái)回答一個(gè)查詢Q”這一問(wèn)題。如果Q能使用V在某一語(yǔ)言類L中進(jìn)行查詢重寫(xiě)，則V必定含有足夠的信息回答Q。但是查詢重寫(xiě)限定了重寫(xiě)的語(yǔ)言類L如果Q不能使用V在語(yǔ)言類L內(nèi)進(jìn)行重寫(xiě)，并不能說(shuō)明V中的信息不足以回答Q因?yàn)楹苡锌赡苁怯捎贚的表達(dá)能力太弱而不能夠表達(dá)出利用V計(jì)算Q的算法（或稱可計(jì)算函數(shù)）。實(shí)際上，文獻(xiàn)[9-11]均舉例指出，對(duì)于一個(gè)合取查詢Q和一組使用合取查詢描述的視圖V不存在Q使用V的合取查詢重寫(xiě)，但是存在一個(gè)一階邏輯查詢可以利用V計(jì)算出Q。

1.3語(yǔ)言完全性根據(jù)查詢重寫(xiě)和視圖確定性之間的關(guān)系，Segoufin等人[8]提出重寫(xiě)語(yǔ)言完全性（Completeness）的概念：給定查詢定義語(yǔ)言類LQ和視圖定義語(yǔ)言類Lv稱語(yǔ)言類L對(duì)于LV到LQ的查詢重寫(xiě)（記作LV-to-LQ）是完全的，當(dāng)且僅當(dāng)對(duì)于LQ中的任意查詢Q和Lv中的任意一組視圖V如果V確定Q則存在一個(gè)Q使用V在語(yǔ)言L中的查詢重寫(xiě)P。語(yǔ)言完全性實(shí)質(zhì)上是說(shuō)如果視圖確定性成立，則依靠該語(yǔ)言類的表達(dá)能力足夠描述利用視圖計(jì)算查詢結(jié)果的算法（或稱可計(jì)算函數(shù)）。

2研究維度

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

3研究進(jìn)展

視圖確定性問(wèn)題由Segoufin和Vianu于2005年首次提出，之后得到眾多數(shù)據(jù)庫(kù)理論方面研究學(xué)者的持續(xù)關(guān)注。下面總結(jié)已有的主要研究成果以及未解決的開(kāi)放性問(wèn)題。

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

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

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

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

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

作者：鄭黎曉常青玲徐世廷單位：華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心中國(guó)科學(xué)院大學(xué)