具有不確定數據的XML數據編碼設計*

姜　巖， 李　欣， 金　鑫

(1. 沈陽工業大學 a. 軟件學院， b. 信息科學與工程學院， 沈陽 110870； 2. 沈陽合興檢測設備有限公司 技術部， 沈陽 110180)

?

具有不確定數據的XML數據編碼設計*

姜巖1a， 李欣1b， 金鑫2

(1. 沈陽工業大學 a. 軟件學院， b. 信息科學與工程學院， 沈陽 110870； 2. 沈陽合興檢測設備有限公司 技術部， 沈陽 110180)

為了解決模糊數據對XML文檔中各元素造成的內容和結構上的改變，使得XML數據模型中的不確定信息能夠被有效地管理，提出了一種基于前綴編碼的四元組編碼方案.在語法分析器XML Schema中，根據模糊數據的特征，利用增加的元素對XML文檔中的模糊元素進行約束，進而為每一個元素建立一個四元組，其參數由文檔號、遍歷序號、元素模糊性及組內標志符構成.通過大量的實驗對比分析，驗證了該編碼方案的有效性，其更適用于具有較低XML樹高度的XML文檔.

模糊數據； 不確定信息； 四元組編碼； 語法分析器； 增加的元素； 模糊性； XML樹高度

隨著人們對Web要求的不斷提高，XML(eXtensible Markup Language)數據庫引入了模糊數據這一概念[1-3]，用戶可以通過數據的編碼判斷XML文檔中各節點的結構關系[4].然而，目前的編碼方案多數針對于精確數據[5-9]，即使是預留空間的編碼方案也不能體現出模糊數據的模糊性，往往只能滿足對模糊數據多種情況的存儲，此外，需要完成模糊數據在XML的兩種語法分析器XML DTD(Document Type Definition)和XML Schema中的定義，才能完成模糊XML文檔中的數據規范.

近年來，很多XML研究工作致力于模糊數據在其語法分析器XML DTD中的定義[10-11]，前人提出了在XML DTD中增加兩個元素用來規范XML文檔中模糊數據的方法，然而，只完成模糊數據在XML DTD中的定義并不能夠完全解決XML中模糊數據的問題，XML DTD有很多缺點，最重要的就是不能支持對數據類型的定義.例如，有些城市的電話區號是三位，而有些城市的是四位，XML DTD是不能完成此功能的.此外，XML DTD不支持命名空間，每一個XML文檔只能有一個DTD，XML DTD以其自身語法規定了相應XML文檔的語言信息，不支持繼承，因此，必須完成對模糊數據在XML Schema中的定義，XML Schema本身就是格式良好的XML文檔，在管理上也更有優勢.

在完成了模糊數據在語言分析器中的規范后，必須要了解數據的編碼方式，XML文檔中任意兩個節點之間的結構關系都是通過編碼來確定的.目前的相關編碼工作主要針對于精確數據的預留空間編碼方案，大致分為基于路徑及基于區間兩種，無論哪種編碼方案都不能較好地完成XML文檔中模糊數據的編碼.針對編碼方案的不足，本文在模糊集理論的基礎上，提出了一種能夠直接對模糊數據進行編碼的方案，它能夠對XML文檔中的模糊節點進行更全面的表示，不僅能判斷各節點的結構關系，還可以知道各元素的模糊性、層次等信息.該方法對層次較低文檔具有更高效率，對用戶更透明，更符合用戶要求，提高了用戶和系統之間的交互能力.

1　XML Schema中的模糊數據

1.1模糊數據

在XML文檔中，模糊數據有兩種存在形式，一種模糊是元組的模糊，例如一名叫李莎莎的學生信息元組是否屬于三年二班這個班級；另一種模糊是屬性的模糊，進一步分析屬性的模糊又可以分為模糊吸取和模糊合取.模糊吸取正如一個人的年齡屬性，取值為一個集合，可以取{20，21，25，29，30}中的某一個值；模糊合取正如郵箱地址屬性取值，一個人可以有多個郵箱.元組模糊表示為具體的元組屬于相應類實例的隸屬度；屬性模糊表示屬性取值的不確定性，模糊吸取代表其模糊值僅能取可能值中的一個，模糊合取代表可以取多個可能值[12].

1.2XML Schema中模糊數據的定義

XML Schema是一種格式良好的XML文檔，可以使用XML編輯器來編輯，功能是對XML文檔進行語言規范，決定XML文檔中可以添加哪些元素、屬性、相同元素的數量及出現順序等信息.為適應模糊信息的引入，XML Schema必須做出修改以完成XML文檔中節點結構關系的判定.

XML Schema對模糊數據的處理方法是：對于每一個具有元組模糊的元素在其XML Schema定義中添加一個chance元素，其數據類型為浮點類型，取值范圍為[0，1]，用來表示元組屬于相應類實例的隸屬度，具體語法如下：

type=”xs：float”/>

對于每一個具有屬性模糊的元素在其XML Schema定義中增加Forms元素與Fuzzytype元素，Forms元素用來引導屬性的多種可能取值，Fuzzytype標志著屬性模糊是模糊吸取還是模糊合取，數據類型為布爾型，具體語法如下：

type=”xs：boolean”/>

每一個Forms元素包含多個Table元素，具體語法如下：

Table元素是一個二元組，由屬性P和Value構成，表示相應的多種可能值以及每種可能值的隸屬度，其語法構成如下：

type=”xs：string”/>

2　支持模糊數據的XML編碼方案

為適應模糊數據的引入，本文提出了一種直接支持模糊數據的編碼方案.

2.1編碼規則

定義1在對含有模糊元素的XML文檔進行編碼時，可以為每一個元素建立一個四元組，即，其中各參數含義如下：

1) “Docld”是文檔的標志符；

2) “LeftPos”與“RightPos”是對XML文檔進行先序遍歷時的開始序號和結束序號；

3) “FuzzyNumber”是文檔的模糊號，其位數由其所在層次決定，根元素有一位，末位表示當前元素的模糊性，0表示當前元素為精確值，1表示當前元素為模糊值，其它位取值繼承其雙親節點；

4) X是組內標志，相同的兄弟節點放在同一組.

2.2判斷節點的結構關系

定義函數h為h→int，返回參數“FuzzyNumber”中0和1的數量總和，即獲取當前元素所在層次.

定義函數f為f→int，返回參數“FuzzyNumber”中的末位數，即獲取當前元素的模糊性.

定義2祖先/后裔關系(ancestor-child).假設節點u，v∈N，N為節點集合，C(u)和C(v)為其編碼，且滿足條件：

1)C(u).Docld=C(v).Docld；

2)C(u).LeftPos

3)C(u).RightPos>C(v).RightPos；

4) ?k∈(u+1，v-1)，?C(u+1).f∧C(k).f∧C(v-1).f=0.

則稱u是v的祖先節點.

定義3雙親/孩子關系(parent-child).假設節點u，v∈N，N為節點集合，C(u)和C(v)為其編碼，且滿足條件：

自由貿易區是目前世界上政策最為寬松的特殊經濟區，自由貿易港是基于自貿區的改革開放升級版，將成為我國對外開放的新高地。汪洋副總理在人民日報署名文章指出，我國即將出爐的自由貿易港將瞄準全球最高開放水平、貨物資金人員進出自由、絕大多數商品免征關稅等標準而建，致力于打造開放層次更高、營商環境更優、輻射作用更強的開放新高地[1]。

1)C(u).Docld=C(v).Docld；

2)C(u).LeftPos

3)C(u).RightPos>C(v).RightPos；

4)C(u).h-C(v).h=1.

則當節點u、v都是精確節點時，u是v的精確雙親節點，否則u是v的模糊雙親節點.

定義4兄弟關系(brother).假設節點u，v∈N，N為節點集合，C(u)和C(v)為其編碼，且滿足條件：

1)C(u).Docld=C(v).Docld；

2)C(u).h=C(v).h；

3)C(u).X=C(v).X.

則稱u是v的兄弟節點.

2.3性質

2) 對于?u∈N，如果存在C(u).h=A，那么節點u位于第A層，根節點位于第1層；

3) 對于?u∈N，如果其編碼C(u).FuzzyNumber中有n位1，那么從根節點到該節點的分支上有n位模糊元素；

4) 對于?u∈N，如果其編碼C(u).FuzzyNumber末位為1，那么當前元素為模糊數據，否則為精確數據.

2.4編碼實例

圖1是一棵存儲學院信息的XML文檔樹，圖2是針對圖1 XML文檔樹的具體實例進行編碼的方案.表1列出了XML文檔樹中各節點的具體編碼.

圖1　學院信息的結構文檔樹

圖2　編碼方案

表1　XML文檔樹節點編碼

學院有計算機系、法律系及機械系，和學院之間存在元組模糊.每個系有多名學生，具體每名學生有學號、姓名、年齡以及郵箱地址屬性.其中年齡屬性為模糊吸取數據，取值{20，25，30}，可以是集合中的任意一個，分別對應的隸屬度為0.2，0.4，0.7.也就是說模糊數據“年齡”一詞可以用模糊集的語言來表示，郵箱地址屬性為模糊合取數據.

圖2中，根節點R與C1節點和C3節點存在元組模糊，R與C1雙親節點的隸屬度是0.6，表示法律系屬于該學院的隸屬度為0.6，同理，機械系屬于該學院的隸屬度為0.2.由于R是一個模糊節點，R與C2之間是精確雙親關系，所以R與C2之間的隸屬度為1.缺省值默認為1，表示的是計算機系精確屬于該學院.此外，C2是S2的祖先節點，C2是S的精確雙親節點，S是S2的模糊雙親節點，S2是S3的兄弟節點.

3　模糊數據編碼方案的性能分析

為了檢驗本文所提出的針對模糊數據編碼方案的適用性，設計了相應的實驗.實驗電腦CPU為2.53 GHz Intel雙核處理器，內存為4 GB，操作系統為Windows 7，實驗環境采用Visual C++6.0，選用的測試數據集由XML自動生成工具Xmark生成，文檔樹的節點數和深度的信息如表2所示，圖3為5個數據集平均編碼位長對比圖，圖4為5個數據集編碼時間對比圖.

表2　XML測試數據集

圖4　數據集編碼時間對比

由圖3與圖4可以看出，并不是節點總數越多的數據集編碼位長越多，時間越長，說明模糊數據的編碼效率與深度有關.圖5繪制出了XML文檔層次與平均編碼時間曲線圖.

圖5　層次分布與平均時間曲線

4　結　論

本文對引入了模糊數據的XML文檔進行了編碼設計，提出了將模糊性體現在編碼中的方法.對XML文檔進行先序遍歷，并記錄訪問時的開始和結束序號，這是判斷節點之間結構關系的關鍵.本文編碼方案不僅可以得出元素所在層次及當前元素模糊性，還可以知道根節點到當前節點所在分支的模糊元素個數及位置等信息.同時，在實驗空間有限的情況下，對多組數據進行了實驗，驗證了該種方案的可行性，并且得出了編碼的效率與文檔層次有關的結論.

[1]朱興統，許波.一種面向XML文檔的模糊關聯規則算法 [J].科學技術與工程，2011，11(26)：5467-5470.

(ZHU Xing-tong，XU Bo.A fuzzy association rules algorithm for XML document [J].Science Technology and Engineering，2011，11(26)：5467-5470.)

[2]Chris T，Khamisy W，Toan V.University fuzzy system representation with XML [J].Computer Standards & Interfaces，2004，28(5)：218-230.

[3]Elisabetta B，Ignazio G，Cristina G，et al.An integra-ted fuzzy logic and web-based framework for active protocol support [J].International Journal of Medical Informatics，2007，77(8)：256-271.

[4]姜巖，潘平，袁琳，等.面向方面的XML結構連接算法的改進 [J].沈陽工業大學學報，2010，32(4)：427-431.

(JIANG Yan，PAN Ping，YUAN Lin，et al.Improvement of aspect-oriented XML structural join algorithm [J].Journal of Shenyang University of Technology，2010，32(4)：427-431.)

[5]文華南，劉先鋒，李文峰，等.高效查詢的XML編碼方案 [J].計算機應用，2010，30(3)：831-834.

(WEN Hua-nan，LIU Xian-feng，LI Wen-feng，et al.XML coding scheme for efficient query processing [J].Journal of Computer Applications，2010，30(3)：831-834.)

[6]姚保峰，馬程，謝娜，等.基于分數的動態前綴XML編碼方案 [J].商丘師范學院學報，2014，30(3)：71-74.

(YAO Bao-feng，MA Cheng，XIE Na，et al.Dynamic prefix XML encoding scheme based on fraction [J].Journal of Shangqiu Normal University，2014，30(3)：71-74.)

[7]馮少榮，陳天爍.基于向量的動態XML編碼方法研究 [J].計算機工程，2012，38(13)：64-66.

(FENG Shao-rong，CHEN Tian-shuo.Research of dynamic XML coding method based on vector [J].Computer Engineering，2012，38(13)：64-66.)

[8]劉先鋒，周舟，劉萍，等.一種分數前綴XML編碼方案 [J].計算機工程，2012，38(12)：29-31.

(LIU Xian-feng，ZHOU Zhou，LIU Ping，et al.Fraction and prefix XML encoding scheme [J].Computer Engineering，2012，38(12)：29-31.)

[9]郭麗紅，王箭，杜賀.一種基于同心圓切割的XML編碼方案 [J].計算機工程，2013，39(6)：52-54.

(GUO Li-hong，WANG Jian，DU He.An XML encoding scheme based on concentric circular cutting [J].Computer Engineering，2013，39(6)：52-54.)

[10]嚴麗，劉健.一種模糊XML模型的概念設計方法 [J].計算機科學，2011，38(12)：157.

(YAN Li，LIU Jian.Conceptual design methodology for fuzzy XML model [J].Computer Science，2011，38(12)：157.)

[11]孟祥福，張霄雁，馬宗民，等.一種基于領域知識的XML數據模糊查詢 [J].智能系統學報，2012，7(6)：527-528.

(MENG Xiang-fu，ZHANG Xiao-yan，MA Zong-min，et al.An XML fuzzy query answering approach based on domain knowledge [J].CAAI Transactions on Intelligent Systems，2012，7(6)：527-528.)

[12]嚴麗，馬宗民，劉健，等.基于關系數據庫映射的模糊數據XML數據建模 [J].計算機學報，2011，34(2)：292-300.

(YAN Li，MA Zong-min，LIU Jian，et al.XML modeling of fuzzy data with relational databases [J].Chinese Journal of Computers，2011，34(2)：292-300.)

(責任編輯：景勇英文審校：尹淑英)

Design for XML data encoding with uncertain data

JIANG Yan1a, LI Xin1b, JIN Xin2

(1a. School of Software, 1b. School of Information Science and Engineering, Shenyang University of Technology, Shenyang 110870, China; 2. Technology Department, Shenyang Hexing Testing Equipment Co. Ltd., Shenyang 110180, China)

In order to solve the change in both content and structure of each element in the XML document caused by fuzzy data and make the uncertain information be effectively managed in the XML data model, a quadruple encoding scheme based on the prefix encoding was proposed. In the syntactic analyzer XML Schema, the fuzzy elements were restrained with some added elements according to the characteristics of fuzzy data, and then each element could be created with a quadruple, where the parameters were consisted of document number, traversal number, element fuzziness and mark in group. Though the contrast and analysis for a great amount of experiments, the effectiveness of this encoding scheme is proved. The results show that the proposed coding scheme is more suitable for XML document with lower height of XML tree.

fuzzy data; uncertain information; quadruple encoding; syntactic analyzer; added element; fuzziness; height of XML tree

2015-07-06.

遼寧省科技廳自然科學基金資助項目(2013020032).

姜巖(1977-)，男，遼寧沈陽人，副教授，博士，主要從事XML數據管理、智能控制等方面的研究.

10.7688/j.issn.1000-1646.2016.01.12

TP 311

A

1000-1646(2016)01-0069-05

*本文已于2015-12-07 16∶16在中國知網優先數字出版. 網絡出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20151207.1616.012.html