鐘 昊

（62421部隊(duì)信息中心，北京 100071）

1 概述

1998年互聯(lián)網(wǎng)協(xié)會(huì)（W3C）發(fā)布了可擴(kuò)展的標(biāo)記語(yǔ)言XML（eXtensible Markup Language）[1]，作為互聯(lián)網(wǎng)數(shù)據(jù)傳輸與交換的標(biāo)準(zhǔn)，使用XML格式描述的數(shù)據(jù)或文檔，成為目前互聯(lián)網(wǎng)上主要的數(shù)據(jù)表示和交換標(biāo)準(zhǔn)之一，被廣泛地應(yīng)用于各種Web服務(wù)（Web services）[2]，如電子商務(wù)、數(shù)字圖書、遠(yuǎn)程教育等應(yīng)用領(lǐng)域。XML的模式設(shè)計(jì)是XML應(yīng)用的核心，不合理的模式設(shè)計(jì)會(huì)導(dǎo)致數(shù)據(jù)冗余或XML文檔生成失敗。雖然XML的語(yǔ)法規(guī)范對(duì)XML模式做出了約束，但仍不能滿足規(guī)范化設(shè)計(jì)的要求。

2 問(wèn)題的提出

XML有自己的模式，本文主要以DTD為例進(jìn)行討論。

例1.XML模式如圖1所示：

圖1 例1DTD

圖2 例2DTD

在語(yǔ)法上來(lái)看，兩個(gè)例子中的模式定義是完全正確的，都符合DTD模式語(yǔ)法規(guī)范，卻存在兩個(gè)問(wèn)題：一是不能構(gòu)造出一個(gè)能夠?qū)崿F(xiàn)例1模式的XML文檔實(shí)例；二是即使能夠構(gòu)造出滿足例2模式的XML文檔實(shí)例，但該模式所定義的元素C和元素D，不可能產(chǎn)生在任何符合該模式的XML文檔中，即元素C和D不可被實(shí)例化。此外，不難看出上述例子給出的模式中存在的問(wèn)題是與XML模式的語(yǔ)義規(guī)范化設(shè)計(jì)無(wú)關(guān)[3，4]，而是由于XML模式設(shè)計(jì)中結(jié)構(gòu)不合理造成的，因此，我們將這類問(wèn)題稱之為XML模式的結(jié)構(gòu)規(guī)范化問(wèn)題。

3 XML模式結(jié)構(gòu)規(guī)范化定義

從例1和例2中可以看出XML模式結(jié)構(gòu)上的不合理設(shè)計(jì)，會(huì)導(dǎo)致XML文檔無(wú)法生成，然而XML的相關(guān)規(guī)范定義的僅僅是XML在模式語(yǔ)法規(guī)范上的基本約束，對(duì)XML模式設(shè)計(jì)的結(jié)構(gòu)方面并未做出相應(yīng)限制，無(wú)法滿足XML文檔規(guī)范化設(shè)計(jì)的要求。針對(duì)上述問(wèn)題，本文提出了XML模式設(shè)計(jì)在結(jié)構(gòu)上的合理性約束：一是XML模式的可實(shí)例化；二是XML模式中元素的可實(shí)例化。

為了便于描述，給定一個(gè)XML模式D和一個(gè)XML文檔T，如果D是T的模式，那么說(shuō)T滿足D，記為T|=D。

定義 給定一個(gè)XML模式D，當(dāng)且僅當(dāng)滿足以下兩個(gè)條件時(shí)，D是結(jié)構(gòu)規(guī)范化的。

（1）至少存在一個(gè)XML文檔T滿足D，即?T，T|=D；

（2）D中的每一個(gè)元素e，至少存在一個(gè)XML文檔T，T|=D，并且T包含e的實(shí)例。

由上述定義可知，例1和例2中的模式都不是結(jié)構(gòu)規(guī)范化的模式。

4 XML模式結(jié)構(gòu)規(guī)范化的判定

為了便于分析XML模式，本文引入元素關(guān)系的概念，并在元素關(guān)系的基礎(chǔ)上判定XML模式的結(jié)構(gòu)規(guī)范化問(wèn)題。

4.1 XML模式中的元素關(guān)系

XML元素關(guān)系是指XML模式中元素與元素之間的父子關(guān)系，并不考慮屬性和元素的值，XML模式中元素關(guān)系包含以下三種：

確定型元素關(guān)系：（1）元素定義表達(dá)式為“e”，表明元素e的基數(shù)值為1；（2）元素定義表達(dá)式為“e+”，表明元素e的基數(shù)值大于等于1。因而，這兩種表達(dá)式中元素e至少會(huì)產(chǎn)生一次元素實(shí)例。

可選型元素關(guān)系：（1）元素定義表達(dá)式為“e?”，表明元素e的基數(shù)值為0或1；（2）元素定義表達(dá)式為“e*”，即e的基數(shù)值大于等于0。這兩種表達(dá)式中元素e的實(shí)例是否生成是不確定的。

選擇型元素關(guān)系：元素定義表達(dá)式為“e1|e2|…|en”，表明各元素之間是互斥的關(guān)系，即在同一父元素下，有且只能擁有一個(gè)子元素ei（1≤i≤n）的實(shí)例。

在上述3種關(guān)系中，選擇型元素關(guān)系是一種元素互斥關(guān)系，因此必須去除這種關(guān)系，以便于分析XML模式的結(jié)構(gòu)范式，本文采用模式分解的方法來(lái)去除選擇型元素關(guān)系，舉例說(shuō)明：

例3給定一個(gè)XML模式D=（a?,（b*|c）,（d|e）），其中省略了對(duì)子元素的定義，為了消除選擇型元素關(guān)系，可將D分解為{D1,D2,D3,D4}，其中：

不難看出，給定一個(gè)XML模式D，如果一個(gè)XML文檔T，T|=D’，D’屬于D的模式分解集合，那么T|=D。如果D含有n個(gè)選擇符（“|”），那么D可分解為2n個(gè)子模式{D1,D2,…,D2n}。

4.2 結(jié)構(gòu)規(guī)范化的判定方法

從元素關(guān)系圖（圖1）來(lái)看，可以發(fā)現(xiàn)一個(gè)XML模式不能產(chǎn)生XML文檔實(shí)例的原因是其模式中存在環(huán)形嵌套的元素定義，而且這種環(huán)形嵌套的元素之間屬于確定型元素關(guān)系，因而，在生成XML文檔時(shí)不能終結(jié)循環(huán)；而可選型元素關(guān)系不是必選的元素關(guān)系，可以不用作元素實(shí)例化。具體判定方法如下：

給定一個(gè)XML模式D，如果給定的分解模式D'的元素關(guān)系描述中不存在確定型元素關(guān)系回路，那么D是結(jié)構(gòu)規(guī)范化的。

證明：由于D中不存在選擇型元素關(guān)系和確定型元素關(guān)系回路，那么生成XML文檔可以從D的根元素出發(fā)，在生成元素實(shí)例的過(guò)程中，如果路徑上不存在任何元素關(guān)系回路，那么路徑中的每個(gè)元素都能直接實(shí)例化到XML文檔中；如果路徑上存在可選型元素關(guān)系回路，那么可在回路中所有元素實(shí)例化后終止回路。顯然，這樣構(gòu)造出來(lái)的XML文檔是滿足模式D的，并且D中定義的元素都可實(shí)例化。因此，模式D是滿足結(jié)構(gòu)規(guī)范化定義的。

5 結(jié)論

通過(guò)對(duì)兩類XML模式的分析，可以看出XML模式中存在問(wèn)題，并且這種模式設(shè)計(jì)問(wèn)題是與語(yǔ)義無(wú)關(guān)的，而是由于模式設(shè)計(jì)中結(jié)構(gòu)不合理導(dǎo)致，本文稱之為XML模式的結(jié)構(gòu)規(guī)范化問(wèn)題。在此基礎(chǔ)上，本文提出了結(jié)構(gòu)規(guī)范化的概念，既確保XML模式能夠被實(shí)例化為XML文檔，又確保模式中的所有元素都能被實(shí)例化。最后，本文通過(guò)分析元素關(guān)系，提出了XML模式結(jié)構(gòu)規(guī)范化的判定方法。XML模式結(jié)構(gòu)規(guī)范化是對(duì)現(xiàn)有語(yǔ)義規(guī)范化的一個(gè)有益補(bǔ)充。

[1]T.Bray,J.Paoli,and C.M.Sperberg-McQueen.Extensible Markup Language （XML）1.0. World Wide Web Consortium Recommendation.1998.http://www.w3.org/TR/1998/REC-xml-19980210.html.

[2]P.Buneman,S.Davidson,W.Fan,et al.Reasoning about keys for XML.The 8th International Workshop.Lecture Notes in Computer Science.NY USA:ACM Press.2001:133-148.

[3]張忠平,曹順良,李榮.基于約束的XML模式規(guī)范化研究[J].計(jì)算機(jī)科學(xué),2003（30）:35-40.

[4]王慶,周俊梅,吳紅偉,等.XML文檔及其函數(shù)依賴到關(guān)系的映射[J].軟件學(xué)報(bào),2003,14（7）:1275-1281.