ＸＭＬ多值依賴及其消除冗余模式的算法

摘 要：從消除XML文檔內數據冗余的角度出發研究了文檔的規范化問題。首先引入XML上的數據冗余及其消除處理示例，同時基于函數依賴，提出了規范化的DTD概念和XML DTD 規范化處理規則；其次通過XML多值依賴的定義，給出用于消除冗余模式的算法;最后給出用于XML模式及其消除冗余模式的算法。該算法相應于其他XML模式的研究，在算法產生的層次模式中，完全MVD和嵌入MVD的集合由給出的MVD集合導出；并且產生的XML模式具有消除冗余模式和滿足無損連接的特性。

關鍵詞：規范化； 函數依賴； 多值依賴

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)06-0061-05

0 引言

XML模式是伴隨著XML 1.0規范的制定而推出的。從模式的第一個方案到目前為止［1］，W3C成員共提交了五個模式規范，分別是XMLData、DCD(Document Content Description for XML)、SOX(Schema for Objectoriented XML)、DDML(Document Definition Markup Language)和XML Schema［2］。直到現在，關于模式還沒有一個正式的標準，它仍在不斷修改完善中。但是DTD良好的一致性、擴展性、易用性、互換性作為XML模式的應用備受研究者的青睞，在實際應用中，DTD是XML文檔使用最多和應用最成熟的模式。所以，規范化理論也是設計XML模式和半結構化數據庫的主要核心組成部分和基礎理論［3］。對于XML模式和DTD規范化設計，現在開展的研究還不多，而且才剛起步。主要的工作有:Provost提出將關系數據庫理論應用于XML模式規范化設計的思想［4］，這一思想還沒有付諸實施；Arenas等人給出的XML函數依賴的概念，定義XML模式的范式XNF，并提出將一個任意的DTD轉換為一個符合XNF的DTD算法，這一算法是通過移動屬性和建立新的元素類型以實現DTD的規范化設計［5］；Ling等人定義半結構化模式的范式S3NF、NFSS和ORASS，給出將一個半結構化模式轉換為一個滿足某個范式的XML模式的算法，這一算法是通過規范化規則對半結構化模式進行重新構造，以實現XML模式的規范化設計。

正如關系數據庫一樣，如果XML的模式設計不好，在XML文檔中同樣也有數據冗余和操作異常現象。下面首先通過一個例子來說明一個設計不好的DTD是如何在XML文檔中引起數據冗余的，以及如何通過合適的DTD變換和規范化處理來消除這種數據冗余。

由于存在上述數據依賴關系，造成XML文檔D1包含冗余的信息：選修了同一門課程的每一個學生，其子元素teacher的信息都要重復存儲；學生“sto1”的姓名(sname)“Joe”在他所選修的每一門課程中都要重復存儲。如果這些信息發生改變，在相應的子元素下面都要同時更新；否則在XML文檔中就會產生數據不一致。這種現象稱之為更新異常。另外，該模式也必然存在數據的操作異常現象：①更新異常。如果要更新學生Joe的信息，則必須同時更新XML文檔中在每一名老師下所有有關Joe的信息；否則就會造成系學生信息的不一致。②插入異常。如果要在該系中存入一名新生的信息，就必須在每一名老師下都插入該學生的信息；否則就會造成系學生信息的不一致。③刪除異常。如果要在該系中刪除一名學生的信息，就必須在每一名老師下都刪除該學生的信息；否則同樣會造成系學生信息的不一致。這種異常現象正是由于DTD D1在設計上存在問題。為了避免這種異常現象，需要對DTD模式進行規范化處理。t[courses.course.title.S]={DB，DW}，S為字符串類型。

1 XML函數依賴及其消除冗余的處理

1.1 XML函數依賴的概念

XML中存在的數據冗余會導致種種異常現象產生，而它的產生是由于文檔內部數據之間存在某種函數依賴關系。首先需要一種表示這種依賴關系的方法，引進關系模式中的概念，稱其為XML上的函數依賴。顯然它比平面或是嵌套關系中的函數依賴都復雜得多，也超出了已有的DTD和XML模式中鍵可以表達的范疇。在此基礎上，可以形式地討論怎樣才是一個消除了冗余的DTD，即規范化的DTD。最后給出DTD的規范化算法，它是基于函數依賴的推理規則集。函數依賴和規范化的理論源于關系數據庫更廣泛的研究，包括嵌套函數依賴和嵌套關系上的范式。目前的XML模式和DTD規范化設計的研究存在著一些共同特點:以函數依賴(FD)表示數據間的依賴關系;規范化設計算法通過對原模式的重構，產生一個符合某一范式的模式。盡管這樣能夠消除某些冗余，但也帶來一些問題:①規范化設計算法對原模式進行重新構造，會導致模式的原有語義發生改變；②在有些情況下，僅用一個模式可能無法很好地表示數據依賴和消除冗余，需要將原來的一個模式分解為幾個模式;③XML結構復雜，僅用FD不能充分地表示XML模式和DTD中數據間的語義關系，特別是層次間的數據依賴通常用MVD表示；④不僅在現有的XML模式和DTD規范化設計的研究中，而且在比較成熟的嵌套關系模式規范化設計的研究成果中，都沒有對冗余進行專門的研究和分類。因而目前的XML模式和DTD規范化設計沒有很好地消除冗余和體現數據間的依賴關系。

1.2 XML消除冗余的處理［6］

2 消除冗余模式的算法

2.1 XML多值依賴

2.2 算法設計

算法1 消除冗余模式的分解樹算法［11]

由算法1可知，產生的分解樹DT(O，M)是一棵有根樹。算法1產生的DT(O，M)消除了冗余模式，但所有的元素和屬性都包含在一棵有根樹中，結構比較復雜，需要作進一步處理。消除冗余模式并具有無損連接特性的算法設計為：在算法1的基礎上產生層次模式，如算法2所示。

算法2 消除冗余模式并具有無損連接特性的算法設計

由算法2產生的層次模式H(O)表示為一個弱連通的有向無環圖，且H(O)表示的數據依賴由給出的MVD集合M導出。因為嵌套關系可以通過非嵌套化操作轉換為INF關系，所以每個XML模式或DTD相應的XML文檔可以通過非嵌套化操作轉換為一個關系實例。要證明算法2產生的層次模式滿足無損連接的特性，就要證明相應的關系模式具有無損連接的特性。算法2產生的層次模式中的數據依賴由給出的簡單類型元素和屬性集合上的MVD集合M導出，并具有消除冗余模式和保持無損連接的特性。

3 結束語

XML的規范化理論還沒有成熟和完善。正如關系數據庫中的模式一樣，每一種范式都有它的應用范圍、特點和局限性，因而不可能解決所有數據冗余問題。通過引入函數依賴和多值依賴的概念，本文給出了一種處理DTD規范化的準則，闡述了將DTD轉換為規范化形式的處理過程。本文基于XML文檔的基本概念給出了XML函數依賴、XML范式和XML多值依賴等相關定義；提出XML模式規范化轉換規則。產生的層次模式具有消除冗余模式和滿足無損連接的特性。由此產生的層次模式能更好地保持數據依賴關系，并且消除了冗余模式。本文的工作對于基于Web的信息系統開發有一定意義。在以后的工作中，將對XML模式的冗余及其導致的異常進行更深入的分析，并以此定義范式，完善規范化設計算法。這將對未來的XML函數依賴保持、XML關鍵字及其求解、XML完整性約束、函數依賴推理規則、XML多值依賴以及XML模式的進一步規范化研究奠定理論基礎。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。