前言

第1章 XML概述

    1.1 XML和DTD簡介

    1.2 XML的優勢與特點

        1.2.1 XML的優勢

        1.2.2 XML的特點

        1.2.3 XML應用概述

    1.3 基於編碼的XML數據庫存儲方法

    1.4 不完全信息下XML

        1.4.1
不完全信息下關繫數據庫數值理論

        1.4.2
不完全信息下XML數值理論

    1.5 概率XML數據

    1.6 本章小結

第2章 基於編碼的XML數據庫存儲方法

    2.1 DTD完全一致性判定的相關定理和算法

    2.2 基於編碼的XML關繫數據庫存儲方法

        2.2.1 編碼方法

        2.2.2 模式映射

        2.2.3 路徑查詢的實現

    2.3 XML文檔的重組與更新

        2.3.1 XML文檔的重組

        2.3.2 XML文檔的更新

        2.3.3 DTD的更新

        2.3.4 遞歸模式的處理

    2.4 本章小結

第3章 不完全信息下XML強函數依賴推理規則

    3.1 基礎知識

        3.1.1 不完全信息的語義分類

        3.1.2 不完全信息之間的關繫

        3.1.3
不完全信息函數依賴的保持條件

    3.2 不完全信息下XML文檔樹相關基本概念

    3.3 不完全信息下XML強函數依賴的性質

    3.4 不完全信息下XML強函數依賴推理規則集

        3.4.1
XSFD推理規則集的正確性

        3.4.2
XSFD推理規則集的完備性

    3.5 本章小結

第4章 不完全信息下XML數據依賴規範化

    4.1 不完全信息下XML強閉包依賴

        4.1.1
不完全信息下XML強閉包依賴的定義

        4.1.2
不完全信息下XML強閉包依賴的性質

    4.2 不完全信息下強閉包依賴的推理規則集

        4.2.1
不完全信息下強閉包依賴推理規則集的正確性

        4.2.2
不完全信息下強閉包依賴推理規則集的完備性

    4.3 XSIND範式

        4.3.1
XSFD和XSIND之間的關繫

        4.3.2
XSIND產生數據冗餘的原因

        4.3.3
XSFD和非循環XSIND互不影響的判定條件

        4.3.4 XSIND範式的判定條件

        4.3.5
規範S為XSIND範式的算法

    4.4 不完全信息下XML強多值依賴

    4.5 不完全信息XML文檔樹滿足XSMVD範式的條件

    4.6 規範不完全信息XML文檔樹為XSMVD範式

    4.7 本章小結

第5章 存在XSFD的XML Schema規範化

    5.1 基本定義

    5.2 XSFD的推理規則集

    5.3 XSFD的成員籍問題

    5.4 不完全信息下規範XML Schema為XSFD範式

        5.4.1
XML雙類結點強函數依賴範式

        5.4.2
XML雙類結點強函數依賴規範規則

        5.4.3 XML
Schema規範化算法

    5.5 存在XSMVD的性質

    5.6 XSMVD的推理規則集

        5.6.1
XSMVD推理規則集的正確性

        5.6.2
XSMVD推理規則集的完備性

    5.7 XSMVD弱範式

    5.8 規範XML Schema為XSMVD弱範式

        5.8.1 規範XML
Schema為XSMVD弱範式規範規則

        5.8.2 規範XML
Schema為XSMVD弱範式算法

    5.9 本章小結

第6章 概率數據模型分析和數據的轉換

    6.1 概率XML數據管理簡述

        6.1.1 概率XML數據模型

        6.1.2 概率XML代數

        6.1.3 概率XML數據查詢

        6.1.4 概率XML數據庫繫統

    6.2 概率數據模型分析

        6.2.1 概率關繫數據模型

        6.2.2 概率XML數據模型

        6.2.3
概率XML樹的路徑表達式的類型

        6.2.4
概率XML樹的路徑表達式的關繫

        6.2.5
概率XML樹的路徑表達式中結點的關繫

    6.3 概率關繫數據與概率XML數據的轉換

        6.3.1
概率關繫模式轉換為概率XML模式

        6.3.2
概率XML模式轉換為概率關繫模式的算法

        6.3.3
概率關繫數據轉換為概率XML數據樹的算法

        6.3.4
概率關繫數據轉換為概率XML數據的算法

    6.4 本章小結

第7章 概率XML XQuery和XML EXQuery

    7.1 以概為操作對像的概率運算

        7.1.1 葉子結點概率運算

        7.1.2 概率閾截取運算

        7.1.3 平凡化運算

    7.2 概率XML樹的基本運算

        7.2.1 並運算

        7.2.2 交運算

        7.2.3 差運算

        7.2.4 連接運算

    7.3 概率XML代數繫統的相關特性

        7.3.1
概率XML代數繫統的封閉性

        7.3.2 查詢操作有效性和完備性

    7.4 EXQuery函數

        7.4.1 與路徑表達式有關的函數

        7.4.2
與路徑表達式轉換有關的函數

        7.4.3 概率計算有關的函數

        7.4.4
路徑表達式的劃分有關的函數

        7.4.5
路徑表達式關繫判斷的有關的函數

        7.4.6 結點關繫判斷有關的函數

        7.4.7 結點概率的計算函數

        7.4.8 與樹類型的判斷有關的函數

    7.5 本章小結

第8章 概率XML樹的結點概率查詢算法

    8.1 子樹個數的估計算法

    8.2 基於可能世界原理的結點概率查詢算法

    8.3 基於路徑表達式劃分的結點概率查詢算法

    8.4 本章小結

參考文獻

第 1 章 XML 概 述

1. 1 XML 和 DTD 簡介

XML（xtensible Markup Language）是標準通用標記語言（SGML）的一種變

體 ，它采用了優化瀏覽器顯示文檔視圖的嚴格的規則集合 。 從 SGML 中經過精心

修剪而來的 XML ，既保持了 SGML 的功能 ，又減少了 SGML 的復雜性 。 與 HT-

ML 不同 ，XML 允許文檔開發人員創建描述數據的標記 ，並使開發人員可以創建

被稱為文檔類型定義（Document Type Description ，DTD）的規則集合 。 任何標準

的 XML 語法分析器都可以讀取 、解碼和檢驗這種基於文本的自描述文檔 ，並以獨

立於平臺的方式提素 ，因此 ，使應用程序可以通過另一種名為文檔對像模

型（DOM ）的標準訪問數據對像 。

一個 XML 文檔包含素開始素結構 。素有一個標簽

（Tag）與之相對應 ，除了字符串數據 ，它還可以包含屬性值對和素 。 同時

包含字符串數據素被稱為具有混合內容 。 XML素標簽

必須良好嵌套 ，這樣的 XML 文檔是良構的 。

DTD 規定了 XML 文檔的結構 ，可視為 XML 文檔的模式 。 DTD 通過描述子
<素和屬性的名字及類型來定義 X素的結構 。 素的出現次數用類

似正則表達式的如下符號規定 ：* （包含零素的集合） ，+ （至少包含一個
<素的集合） ，？ （包含零素）和沒有修飾（包含且僅包素） 。 同時

DTD 也嚴格規定了 XML 素的出現順序 ，素定義的正

則表達式順次展開素允許包含至多一個類型為 ID 的屬性 ，由該屬性在文檔域

內素 ，同素也可以通過類型為 IDREF 的屬性對其加以引

用 。 IDREF 屬性並沒有指明該屬性所素類型 ，在這一意義上說 ，IDREF

屬性是沒有類型的 。 屬性定義中可以用 # REQUIED 和 # IMPLIED 等修飾符類

似描述其在出現次數上的約束 ，同時屬性的取值範圍也可在 DTD 中定義 。 一個

良構且滿足 DTD 的定義的 XML 文檔被視為是有效的 。

很多學者也提出了各種 XML 存儲模型 ，根據存儲方式的不同 ，處理 XML 數

據的基本方式可分為三類 ：

（1） 文件繫統 。 HTML 的存儲管理都是基於這種平面的文件繫統 。 但 XML

和 HTML 有著很大的區別 ，XML 是層次結構的 ，而 HTML 不是 。 主要方法是將

XML 數據以 BLOB 的形式進行存儲 ，然後在每一次使用時將它進行解析 。 這存

在著很大缺陷 ，為了提高查詢效率可以建立索引 ，索引的維護是需要解決的關鍵

問題 。

（2） 數據庫管理繫統 。 這是一種基於層次數據庫的存儲管理技術 。 由於

XML 本身是層次結構的 ，所以可以將 XML 數據存儲在層次數據庫中 。 在層次數

據庫中 ，可以利用 ：① pseudo query 的語法來編寫查詢語句對數據進行查詢 。 但層

次數據庫技術非常的不成熟 ，而且操作非常復雜 ，因此不是一種很有效的方法 。

② 基於關繫數據庫的存儲管理技術 。 關繫數據庫是目前成熟的數據庫技術 ，可

以將 XML 的模式映射到關繫數據庫中 。 例如 ，將 DTD（文檔類型定義）映射到關

繫數據庫中 ，這種基於關繫數據庫的存儲管理技術被應用的非常廣泛 。 ③ 基於面

向對像數據庫的存儲管理技術 。 面向對像數據庫用自身的方法 、關繫和語義來管

理分層 XML 樹 ，同時提供了強大的導航和鏈接的功能 。 雖然面向對像數據庫的

體繫結構非常適合存儲 XML 數據 ，但它本身技術還不成熟 ，從而限制了它的

應用 。

（3） XML 數據庫 。 XML 數據庫是一個 XML 文檔的集合 ，這些文檔是持久

的並且是可以操作的 。 XML 文檔趨向於面向文檔處理或趨向於面向數據處理 。

面向文檔處理的文檔是使用 XML 來獲取自然語言的那些文檔 ，側重於給用戶提

供信息的終表示 。 面向數據處理的文檔是 XML 主要用於數據傳送的文檔 ，側

重於它被應用程序的使用和交換 。

XML 數據是一個面向數據處理的文檔的集合 。 XML 在數據庫與應用程序

之間 ，以及在多對應用程序之間進行數據交換是很有用的 。 在數據交換中 ，被交換

的數據可能需要被保留在一個存檔文件中 。 一個可搜索的 XML 數據庫可以作為

數據交換的中心部件 ，並且它也可以與其他使用 XML 的應用程序進行交互 ，或者

獲取 Web 服務的摘要信息 。

如果數據庫把數據保存為 XML ，那麼在存儲粒度上存在幾個選擇 。 XML 數

據可以被保存為一個文檔 、被分割為更小的部分並被保存為片段 ，或者被分解為單

用程序或用戶 。 通過解析文檔 ，並把數據保存在數據庫結構（如關繫）中 。 數據可

以作為 XML 被添加到數據庫中 。

XML 數據庫比傳統數據庫更具有表現力 ，能夠對半結構化數據進行有效的

存儲和管理 ，提供了對標簽名稱的操作 ，並且包括了對路徑的操作 ，顯示豐富多樣 。

但 XML 數據庫檢索速度和修改效率較低 ，解析手段有缺陷（基於文件解析的 SAX

方式速度慢 ，而基於內存解析的 DOM 資源消耗較大） ，且安全性和並發操作機制

也是需要重點解決的問題之一 。

其中 ，經過了 40 多年發展的關繫數據庫 ，具有管理方便 、存儲容量小 、檢索速

度快 、修改效率高 、安全性好等特點 ，技術已十分成熟 ，利用其管理 XML 數據能夠

保障 XML 數據的可移植性和完整性 ；另一方面 ，目前大量的 Web 數據主要存放

在關繫數據庫中 ，所以 ，不少的研究人員都致力於 XML 的關繫數據庫存儲方法的

研究 。

基於關繫數據庫的 XML 存儲方法的研究重點是 XML 文檔的模式到關繫模

式的映射 。 近幾年所提出的模式映射方法 ，主要分為兩類 ：

（1） 映射產生的關繫模式依賴於 XML 模式 。 它要求預先確定 XML 文檔的

結構 ，對 DTD（或 Schema）進行簡化 、分解等預處理 ，再將 DTD素 、屬性映

射成關繫數據庫中的表或表的屬性 ，即根據 DTD（或 Schema）產生存放 XML 文檔

數據的一個或幾個關繫表 。 這種方法在存儲特定的 XML 文檔的情況下 ，具有較

高的存儲和查詢效率 ，但是 ，如果需要存放的是海量的 、具有不同結構的 XML 數

據 ，如 Internet 上得到的各種數據 ，則具有很大的局限性 ：① 不同的 DTD（或 Sche-

ma）會產生大量的不同模式的關繫表 ；② 如果 XML 文檔的結構發生了變化 ，那麼

相應的關繫表必須適應這種變化 ，修改模式定義 ，重新對 XML 數據進行存儲 ，更

新粒度較大 。

（2） 映射方法產生的關繫模式獨立於 XML 模式 。 這類方法通常是將 XML

文檔解析成樹或圖結構 ，然後提供相應的關繫模式來儲存這些圖結構 ，關繫數據庫

中不但保存了 XML 數據 ，且同時保存了 XML 文檔的結構 。 能夠有效地解決

類映射方法中出現的部分問題 ，但對於 XML 路徑查詢 ，它通常需要遍歷整個數據

庫 ，進行多次連接操作纔能確定路徑的正確性完成查詢工作 ，因而效率相對類

方法要差些 。

1. 2 XML 的優勢與特點

1.2. 1 XML 的優勢

可擴展標識語言 XML 由萬維網聯盟 W3C 於 1998 年 2 月發布為 W3C 的 1.0

版本標準 ，是一種用於網絡信息描述 、組織和顯示的語言 ，是 Internet 的“世界語” ，

目前它已經成為 Internet 上信息表示和數據交換的一個重要標準 。 它在當今世界

的網絡信息表示和數據交換上如此重要是因為它具有如下優勢 ：

（1） XML 具有良好的格式以及嚴格的驗證機制 ，數據編碼為 XML 格式的應

用將使信息能夠以一種簡單可用的方式加以表達 ，這些信息的提供者也能非常簡

便的提供互操作性 。

（2） 將內容與其表示相分離使得 XML 更能專注於表示數據的語義信息 。

（3） 用戶自定義標簽和無限嵌套的能力賦予 XML 無限的可擴展性 ，這使得

XML 能夠清晰自然的表示各行業的數據 。

（4） XML 解析器和訪問接口實現簡單 ，各種平臺都很容易獲取穩定的 XML

解析器和訪問接口 ，這使得開發基於 XML 的應用變得簡單高效 。

鋻於 XML 的上述優勢 ，XML 具有廣闊的應用前景 。 基於 XML 的行業標記

語言目前較多 ，如數學領域的 MathML 、化學領域的 CML 以及音樂領域的 Music-

ML 等 ；在電子商務等領域中逐漸代換傳統的電子數據交換（EDI）技術 ，成為數據

交換的新標準 ；業界領先的軟件提供商提供面向 XML 的工具和產品 ；眾多企業和

研究者以 XML 格式發布它們的數據 。 種種現像表明 ，XML 數據及面向 XML 數

據的應用將持續快速發展 ，使 XML 迅速成為數據交換的公共語言 。

1.2. 2 XML 的特點

XML 有以下幾個特點 。

（1） 開放的標準 。

XML 是基於 W3C 定制的開放的標準 ，從而使得基於 XML 的應用越來越

廣泛 。

（2） 具有良好的格式 。

XML 標記大都是成雙成對的 ，極少數不在此列的情況也需要遵守特殊格式

定義起始 。

（3） XML 支持對文檔內容進行驗證 ，或稱文檔有效性保證 。

目前 ，DTD 和 XML Schema 已經成為 XML 兩種主流模式 。 DTD 是一個專

門的文件 ，用來定義和檢驗 XML 文檔中的標記 。 XML Schema 用 XML 語法描

述 ，它比 DTD 優越 ，多個 Schema 可以滿足使用 XML 名稱空間 ，可以詳

素的內容和屬性值的數據類型 。

（4） 面向對像的特性 。

XML 文件是樹狀結構 ，也有屬性 ，這非常符合面向對像的編程 ，而且也體現

出對像方式的存儲 ，XML 是信息的對像化語言 。

（5） 選擇性更新 。

通過 XML ，數據可以在選擇的局部小範圍內更新 ，提高服務器的性能 。

（6） 支持高級搜索 。

在 Internet 上若 Web 頁是 XML 格式的 ，不僅可以搜索數據 ，而且還可以在搜

索中加入與數據相關的上下文信息 ，形成更精確的搜索機制 。

（7） XML 是電子數據交換的格式 。

XML 是為互聯網的數據交換而設計的 ，能夠應用於電子商務 、電子政務等各

個領域的數據交換 。

（8） XML 具有一套完整的方案 。

XML 是一個技術大家族 ，有一繫列相關技術 ，包括文件數據驗證 、顯示輸出 、

文件轉換 、文檔對像和鏈接等 。 XML 文檔是對像實例 ，DTD 和 Schema 是界面或

類 ，XSL 是方法和實現 ，XML 的資源描述框架是信息導航 、瀏覽 、搜索的用戶接口

標準 。

1.2. 3 XML 應用概述

XML 是一個網絡信息描述 、組織和顯示的語言 ，它的開放性 、嚴謹性 、結構性

和靈活性備受網絡開發者的青睞 。 在以下領域 ，XML 有廣闊的應用前景 。

1） 數據庫領域

關繫型數據庫行業的三大巨頭 —— Oracle 公司 、IBM 公司和 Microsoft 公司

都在它們的數據庫產品中提供了對 XML 的支持 。 從本質來看 ，XML 文檔就是數

據庫 ，是數據的集合 ，每個文件都含有某種類型的數據 。 在許多方面它和其他文件

沒什麼區別 ，但作為一種“數據庫”格式 ，XML 有一些優點 ，例如 ，它是可交換的 、

自描述的 ，能夠以樹狀或圖形結構描述數據 。

2） Agent

若把 XML 結構化的數據送到 Agent（智能體） ，Agent 就能很容易地理解這些

數據的含義 ，很容易理解這些數據與已有知識的關繫 。 基於 XML 的數據交換對

於解決Agent的交互性問題起著重要的作用 ，XML 及相關技術必將促進 Agent 技

術的發展 。

3） 軟素的交換

XML 能夠描述軟件設計中有關素 ，如對像模型 ，甚至能夠描述終

設計出來的軟件 。 這些基於 XML 素可以借助 Web 在開發組內進行交

換 ，在不同的開發工具之間交換 。

4） 網絡服務領域

XML 有利於信息的表達和結構化組織 ，從而使數據搜索更有效 。 XML 能夠

使用 URL 別名使 Web 的維護更方便 ，也使 Web 的應用更穩定 ；XML 還能夠使用

數字簽名使 Web 的應用更廣闊 。 信息發布在企業的競爭發展中起著重要的作用 ，

服務器隻需發出一份 XML 文檔 ，客戶就可根據自己的需求選擇和制作不同的應

用程序以處理數據 。 加上 XSL 的幫助 ，能夠實現廣泛的 、通用的分布式計算 。

5） EDI

傳統的 EDI（電子數據交換）標準缺乏可擴展性和靈活性 。 使用 XML ，程序能夠

理解在交換數據中所表示的商務數據及概念 ，根據明確的商務規則來進行數據處理 。

6） 電子商務領域

XML 的豐富置標能夠描述不同類型的單據 ，如保險單 、信用證 、索賠單以及

各種發票等 。 結構化的 XML 文檔發送至 Web 的數據可以被加密 ，並且很容易附

加上數字簽名 。

1.3 基於編碼的 XML 數據庫存儲方法

由於逐漸廣泛的應用 ，XML 正逐步將 Web 轉化為一個巨大的數據庫 ，但將數

據表示為 XML 隻是對 Web 這一巨大數據庫進行有效處理的步 。 如何對大

量的 XML 數據進行有效的管理已經成為數據庫研究領域的一個重要的研究問

題 。 同時 ，對傳統數據庫管理技術提出了巨大的挑戰 ，也為數據庫研究提供了良好

的機遇 。

目前大多數商業化的關繫數據庫支持 XML ，關繫數據庫和對像關繫數據庫繫

統也提供了各種 XML 數據的擴展和插件 。 同時 ，為 XML 數據管理量身打造的

XML 原生數據庫繫統也不斷湧現 ，也出現了 XML 數據管理的標準 。 XML 數據

庫繫統是 Web 技術和數據庫技術相結合的產物 。 很多學者對 XML 數據庫管理

技術進行了繫統深入的研究 ，取得了很多有意義的理論研究成果 ，XML 數據庫的

規範化理論是其中研究成果之一 。

XML 作為一種數據交換的標準和半結構化數據的表示模型 ，人們關注的問

題是 ：用 XML 表示的數據之間有什麼聯繫以及有什麼約束 ？ 因此 ，研究 XML 文

檔中普遍存在的關鍵字約束問題就非常重要 ，隨著 XML 成為 Web 上一種通用的

數據格式 ，將關鍵字（簡稱為鍵）的概念引入到 XML 領域 。 鍵也在不變的數據上

構成了一個重要的約束類 ，特別的 ，鍵與地址或者內部對像標識符相比 ，它在現實

世界中的一個對像與它在數據庫所表示的事物之間提供了一個不變的連接 。 這種

連接在更改數據庫作為世界模型的改變中是非常關鍵的 。 隨著 XML 越來越多地

應用在數據管理中 ，很自然就需要一個基於值的方法來確定一個 XML

素的位置 。 XML 數據通常也是來自數據庫 ，而在數據庫中關鍵字通常被用來傳

達數據的語義的本質的部分 ，為了使用 XML 來表示當前駐留在數據庫中的數

據 ，我們必須能夠表示數據的原始語義 ，特別是鍵 。 鍵對索引 、XML 數據的存檔

以及設計關繫存儲都是不可或缺的 。 為了獲得更加有效的應用 ，鍵所給出的約束

和結構經常在這樣的繫統中得到開發 。 XML 關鍵字在 XML Query 的數據模型

中也起到了非常重要的作用 。 因為索引通常建立在鍵之上 ，鍵為數據的結構提供

了信息 ，所以 ，XML 鍵在研究隊列優化的過程中也是非常重要的 。 這也是進行其

他 XML 相關研究的基礎 ，如 XML 模式的規範化 、查詢優化 、結構優化 、路徑約

束等 。

目前常見的 XML 文檔模式定義規範主要包括 DTD 和 XML Schema 。