具有不確定數(shù)據(jù)的XML數(shù)據(jù)編碼設(shè)計*

姜　巖， 李　欣， 金　鑫

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

?

具有不確定數(shù)據(jù)的XML數(shù)據(jù)編碼設(shè)計*

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

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

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

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

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

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

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

1　XML Schema中的模糊數(shù)據(jù)

1.1模糊數(shù)據(jù)

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

1.2XML Schema中模糊數(shù)據(jù)的定義

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

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

type=”xs：float”/>

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

type=”xs：boolean”/>

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

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

type=”xs：string”/>

2　支持模糊數(shù)據(jù)的XML編碼方案

為適應(yīng)模糊數(shù)據(jù)的引入，本文提出了一種直接支持模糊數(shù)據(jù)的編碼方案.

2.1編碼規(guī)則

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

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

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

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

4) X是組內(nèi)標志，相同的兄弟節(jié)點放在同一組.

2.2判斷節(jié)點的結(jié)構(gòu)關(guān)系

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

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

定義2祖先/后裔關(guān)系(ancestor-child).假設(shè)節(jié)點u，v∈N，N為節(jié)點集合，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的祖先節(jié)點.

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

自由貿(mào)易區(qū)是目前世界上政策最為寬松的特殊經(jīng)濟區(qū)，自由貿(mào)易港是基于自貿(mào)區(qū)的改革開放升級版，將成為我國對外開放的新高地。汪洋副總理在人民日報署名文章指出，我國即將出爐的自由貿(mào)易港將瞄準全球最高開放水平、貨物資金人員進出自由、絕大多數(shù)商品免征關(guān)稅等標準而建，致力于打造開放層次更高、營商環(huán)境更優(yōu)、輻射作用更強的開放新高地[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.

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

定義4兄弟關(guān)系(brother).假設(shè)節(jié)點u，v∈N，N為節(jié)點集合，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的兄弟節(jié)點.

2.3性質(zhì)

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

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

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

2.4編碼實例

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

圖1　學(xué)院信息的結(jié)構(gòu)文檔樹

圖2　編碼方案

表1　XML文檔樹節(jié)點編碼

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

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

3　模糊數(shù)據(jù)編碼方案的性能分析

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

表2　XML測試數(shù)據(jù)集

圖4　數(shù)據(jù)集編碼時間對比

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

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

4　結(jié)　論

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

[1]朱興統(tǒng)，許波.一種面向XML文檔的模糊關(guān)聯(lián)規(guī)則算法 [J].科學(xué)技術(shù)與工程，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結(jié)構(gòu)連接算法的改進 [J].沈陽工業(yè)大學(xué)學(xué)報，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].計算機應(yīng)用，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]姚保峰，馬程，謝娜，等.基于分數(shù)的動態(tài)前綴XML編碼方案 [J].商丘師范學(xué)院學(xué)報，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]馮少榮，陳天爍.基于向量的動態(tài)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]劉先鋒，周舟，劉萍，等.一種分數(shù)前綴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模型的概念設(shè)計方法 [J].計算機科學(xué)，2011，38(12)：157.

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

[11]孟祥福，張霄雁，馬宗民，等.一種基于領(lǐng)域知識的XML數(shù)據(jù)模糊查詢 [J].智能系統(tǒng)學(xué)報，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]嚴麗，馬宗民，劉健，等.基于關(guān)系數(shù)據(jù)庫映射的模糊數(shù)據(jù)XML數(shù)據(jù)建模 [J].計算機學(xué)報，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.

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

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

10.7688/j.issn.1000-1646.2016.01.12

TP 311

A

1000-1646(2016)01-0069-05

*本文已于2015-12-07 16∶16在中國知網(wǎng)優(yōu)先數(shù)字出版. 網(wǎng)絡(luò)出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20151207.1616.012.html