XML多值依賴問題的研究.pdf

1、XML憑借著眾多優(yōu)勢已經(jīng)成為Web上數(shù)據(jù)表示與交換的標(biāo)準(zhǔn)。但XML模式所能表示的語義信息卻相對有限。同關(guān)系數(shù)據(jù)庫相似，設(shè)計不好的XML數(shù)據(jù)模式也會引起更新異常。而Internet的開放性使XML數(shù)據(jù)更新異常的危害性要遠(yuǎn)遠(yuǎn)大于關(guān)系數(shù)據(jù)。因此，完善XML數(shù)據(jù)庫規(guī)范化理論已成為必要。本文在對國內(nèi)外研究現(xiàn)狀進(jìn)行綜合分析的基礎(chǔ)上，基于DTD，在模式一級對XML中多值依賴進(jìn)行規(guī)范化研究。主要內(nèi)容如下。 首先，在分析XML文檔DTD設(shè)計的基礎(chǔ)

2、上，對XML多值依賴約束進(jìn)行研究，基于路徑表達(dá)式和樹元組提出了XML多值依賴的形式化定義。 其次，研究XML多值依賴的推理規(guī)則集問題。提出了XML路徑集閉包、路徑依賴基等基本概念，給出了XML多值依賴的一個有效且完備的推理規(guī)則集，并對其有效性和完備性進(jìn)行了證明。 再次，對XML多值依賴的成員籍問題進(jìn)行了研究。給出了求解路徑依賴基的算法。并基于求解路徑依賴基，給出了解決XML多值依賴成員籍問題的算法，并對兩個算法的可終止性

3、、正確性進(jìn)行了證明，對時間復(fù)雜度進(jìn)行了分析。 然后，對XML多值依賴下的范式及其規(guī)范化問題進(jìn)行研究。提出了在XML多值依賴下的范式MXNF的定義，并證明滿足MXNF的DTD消除了數(shù)據(jù)冗余。在此基礎(chǔ)上，提出了將任意DTD轉(zhuǎn)換為滿足MXNF的DTD的算法，并對算法的正確性、可終止性和時間復(fù)雜性進(jìn)行證明分析。 最后，對XML文檔對給定多值依賴集的滿足性的檢測問題進(jìn)行了研究。通過定義棧結(jié)構(gòu)和值元組等，定義了文檔的控制結(jié)構(gòu)。給出了