Active XML數(shù)據(jù)管理基礎(chǔ)問題研究.pdf

1、Active XML(Active eXtensible Markup Language)的提出，能夠有效的解決當(dāng)前分布式數(shù)據(jù)管理中存在的數(shù)據(jù)源異構(gòu)性、交互性及自主性問題，為分布式Web數(shù)據(jù)管理提供了新的發(fā)展方向。AXML文檔是一部分?jǐn)?shù)據(jù)直接給出，另一部分?jǐn)?shù)據(jù)以Web服務(wù)調(diào)用方式隱含給出的XML文檔，通過觸發(fā)這這些服務(wù)調(diào)用，可以獲得其包含的隱含信息來擴(kuò)充文檔內(nèi)容。AXML模式定義了符合約束條件的AXML文檔集合。
　　AXML數(shù)據(jù)

2、管理需要考慮如下基礎(chǔ)問題：(1)AXML數(shù)據(jù)交換是AXML的主要應(yīng)用方式，而數(shù)據(jù)交換之前必須判定給定AXML文檔通過觸發(fā)其包含的服務(wù)調(diào)用是否能夠轉(zhuǎn)換成為符合目標(biāo)模式要求的文檔實(shí)例，從而引出了文檔重寫問題；(2)在某些情況下，還要考慮符合給定源模式的全部文檔是否能夠重寫為目標(biāo)模式實(shí)例，這就需要考慮模式之間的兼容性，該問題為模式重寫問題；(3)AXML數(shù)據(jù)交換過程中，通常以查詢方式來實(shí)現(xiàn)數(shù)據(jù)請(qǐng)求，而查詢可滿足性判定是執(zhí)行給定查詢的前提條件，

3、通過判定給定查詢的可滿足性，可以過濾掉一部分不可滿足查詢，從而提高查詢的執(zhí)行效率；(4)保證AXML文檔為有效文檔是AXML數(shù)據(jù)管理的關(guān)鍵，也是AXML數(shù)據(jù)交換、文檔查詢的先決條件。
　　本文基于樹自動(dòng)機(jī)理論，對(duì)AXML數(shù)據(jù)交換中存在的AXML文檔重寫和模式重寫、AXML文檔查詢可滿足性、AXML文檔有效性檢驗(yàn)問題進(jìn)行了深入研究，目的是對(duì)上述問題提出有效的解決方法，從而讓AXML能夠更好的服務(wù)于分布式數(shù)據(jù)管理。
　　第一，研

4、究了AXML文檔重寫和模式重寫問題。AXML文檔重寫問題是指判定給定文檔通過觸發(fā)其包含的服務(wù)調(diào)用是否能夠?qū)⑵滢D(zhuǎn)換成為符合目標(biāo)模式的文檔實(shí)例。AXML文檔重寫問題分為可能重寫和安全重寫，AXML文檔可能重寫是判定給定文檔是否能夠重寫為目標(biāo)模式的某一文檔實(shí)例；AXML文檔安全重寫是判定給定文檔的全部可生成文檔是否能夠重寫為符合目標(biāo)模式的文檔實(shí)例。AXML模式重寫問題是指判定符合給定源模式的全部文檔是否能夠重寫為目標(biāo)模式實(shí)例。首先，基于傳統(tǒng)樹

5、自動(dòng)機(jī)理論，定義了用于抽象描述AXML文檔樹的ADTA機(jī)(AXML Document Tree Automata)，基于ADTA機(jī)，給出了多項(xiàng)式時(shí)間復(fù)雜度的AXML文檔可能重寫判定算法，給出了算法的正確性證明；在ADTA機(jī)的基礎(chǔ)上，定義了ADTA機(jī)補(bǔ)自動(dòng)機(jī)，提出了多項(xiàng)式時(shí)間復(fù)雜度的AXML文檔安全重寫判定算法，給出了算法的正確性證明；然后，定義了用于描述AXML模式的ASTAr機(jī)(AXML Schema Tree Automata fo

6、r Rewriting)，給出了ASTAr機(jī)構(gòu)造算法，ASTAr機(jī)定義了所有符合給定AXML模式約束的AXML文檔集合；最后，通過分析AXML模式包含與模式重寫的關(guān)系，基于ASTAr機(jī)，提出了多項(xiàng)式時(shí)間復(fù)雜度的AXML模式重寫判定算法，分析了算法的正確性和有效性。
　　第二，研究了模式約束下的 AXML文檔樹模式查詢可滿足性問題。AXML文檔查詢可滿足性問題是指判定符合給定模式約束的AXML文檔是否滿足給定查詢表達(dá)式。首先，給出了

7、AXML文檔查詢可滿足性的形式化定義；然后，定義了用于抽象AXML模式的ASTAq機(jī)(AXML Schema Tree Automata for Queries)，用于描述符合給定AXML模式約束的文檔集合，定義了抽象樹模式查詢的TPQA機(jī)(Tree Pattern Query Automata)，TPQA機(jī)描述了包含滿足給定樹模式查詢表達(dá)式路徑的文檔集合；最后，基于ASTAq機(jī)和TPQA機(jī)，針對(duì)XPath樹模式查詢片段，提出了一種多項(xiàng)

8、式時(shí)間的AXML文檔查詢可滿足性檢驗(yàn)算法，分析了算法的正確性和有效性。
　　第三，研究了AXML文檔有效性檢驗(yàn)問題。AXML文檔有效性檢驗(yàn)問題是指給定AXML文檔及其服務(wù)調(diào)用規(guī)范，檢驗(yàn)文檔是否符合目標(biāo)模式。定義了用于抽象AXML模式的ASTAv機(jī)(AXML Schema Tree Automata for Validation)，該樹自動(dòng)機(jī)描述符合目標(biāo)模式約束的文檔集合，能夠完成對(duì)給定文檔當(dāng)前狀態(tài)的有效性檢驗(yàn)；基于ASTAv機(jī)，通