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

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

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

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

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

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

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

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

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