資源描述:
《xml數(shù)據(jù)模型及相關(guān)技術(shù)綜述》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、XML數(shù)據(jù)模型及相關(guān)技術(shù)綜述:隨著Inter的發(fā)展,XML成為在X絡(luò)上用于數(shù)據(jù)描述和數(shù)據(jù)交換的新的標(biāo)準(zhǔn)。在介紹XML及其數(shù)據(jù)模型的同時(shí),對(duì)幾種查詢技術(shù)和更新操作作簡(jiǎn)要的敘述?! £P(guān)鍵詞:XML;索引結(jié)構(gòu);編碼;更新 ?。篢P3:A:1671-7597(2011)0310038-01 0引言 隨著Inter的發(fā)展,XML(eXtensiveMarkupLanguage)[1]于98年被L文檔中的數(shù)據(jù),幾種查詢語(yǔ)言,諸如Lorel,XML-QL,XML-GL,Quilt,XPath,andXQuery,已經(jīng)被提出。本文簡(jiǎn)要介紹了XML語(yǔ)言及其數(shù)據(jù)模型,并對(duì)幾種
2、查詢技術(shù)和更新操作作了簡(jiǎn)要的敘述。 1XML數(shù)據(jù)模型 1.1擴(kuò)展標(biāo)記語(yǔ)言(XML) XML是一種描述性的語(yǔ)言,作為SGML(標(biāo)準(zhǔn)通用標(biāo)記語(yǔ)言StandardGeneralizedMarkupLanguage)的一個(gè)子集,XML保留了SGML的可擴(kuò)展的功能,并將SGML的豐富功能和的易用性結(jié)合到L數(shù)據(jù)模型 定義XML數(shù)據(jù)模型是執(zhí)行XML數(shù)據(jù)操作的前提和基礎(chǔ)。由于XML文檔的嵌套的,層次的結(jié)構(gòu),我們可以把一個(gè)XML文檔定義為一個(gè)具有如下特點(diǎn)的結(jié)構(gòu),如圖1: 1)是一個(gè)被標(biāo)記節(jié)點(diǎn)的圖(或者樹(shù))結(jié)構(gòu),其中的每一個(gè)節(jié)點(diǎn)用原文檔中的元素的標(biāo)簽來(lái)標(biāo)記; 2)邊用來(lái)表
3、示文檔中元素間的嵌套關(guān)系; 3)該結(jié)構(gòu)中有一個(gè)明確的根節(jié)點(diǎn)?! ?XML索引和查詢技術(shù) 由于XML已經(jīng)成為Inter上廣為流行的標(biāo)準(zhǔn),如何對(duì)XML數(shù)據(jù)進(jìn)行索引和查詢也就成為近些年來(lái)研究的熱點(diǎn)。這些方法概括起來(lái),可以分為兩類:1)基于結(jié)構(gòu)化索引的方法;2)基于結(jié)構(gòu)化連接的方法,它們都是以樹(shù)型結(jié)構(gòu)為基礎(chǔ)的?! ?.1結(jié)構(gòu)化索引 利用圖的相似性的概念,我們把XML文檔結(jié)構(gòu)圖中具有相似性的節(jié)點(diǎn)合并為一個(gè)被稱為索引節(jié)點(diǎn)的節(jié)點(diǎn),從而建立了一個(gè)索引結(jié)構(gòu)圖,可見(jiàn)該索引圖的規(guī)模比原圖小了很多,從而有利于進(jìn)行快速的查詢。 典型的索引結(jié)構(gòu)為1-index[2](如圖2),利用從
4、根節(jié)點(diǎn)開(kāi)始的路徑的信息,定義了一個(gè)索引結(jié)構(gòu)圖,它能夠?qū)Σ樵冏鞒鼍_的判斷。然而,對(duì)一些較為復(fù)雜的,不規(guī)則的文檔結(jié)構(gòu),l-index[2]結(jié)構(gòu)圖往往會(huì)變的很大,影響了查詢的性能。局部相似性概念的提出,權(quán)衡了查詢性能和查詢精度,減小了索引結(jié)構(gòu)圖的規(guī)模,從總體上提高了查詢效率。A(k)-index[3]是這一家族的一個(gè)很好的代表,通過(guò)調(diào)整k的值,它建立了一個(gè)索引序列,改善了1-index[2]中存在的問(wèn)題。之后提出的D(k)-index[4],具有了動(dòng)態(tài)的特性,通過(guò)對(duì)索引結(jié)構(gòu)圖的調(diào)整,很好的適應(yīng)了不斷變化的查詢模式。 2.2結(jié)構(gòu)化連接 不同于結(jié)構(gòu)化索引,結(jié)構(gòu)化連接采
5、用了另一種思想,即把找到XML數(shù)據(jù)中基本的結(jié)構(gòu)關(guān)系作為XML查詢處理的核心操作。它基于編碼方式,利用節(jié)點(diǎn)間編碼的關(guān)系來(lái)快速的決定XML文檔結(jié)構(gòu)中的節(jié)點(diǎn)間祖先后代關(guān)系和父子關(guān)系。編碼方式以其良好的查詢性能引起了人們的廣泛的研究,目前的編碼方式主要包括區(qū)域編碼方式[6,7,8],前綴編碼方式[9,10]和素?cái)?shù)編碼方式[11]。例如,利用元素在文檔中開(kāi)始和結(jié)束位置[6],構(gòu)成了一種區(qū)域編碼方式。樹(shù)型結(jié)構(gòu)中的兩個(gè)節(jié)點(diǎn)a和b,a是b的祖先節(jié)點(diǎn)的充要條件是a的開(kāi)始位置小于b的開(kāi)始位置,并且a的結(jié)束位置大于b的結(jié)束位置。假設(shè)a編碼為(1,7),b的編碼為(3,4),因?yàn)?4,所
6、以a一定是b的祖先節(jié)點(diǎn)。前綴編碼則是通過(guò)與節(jié)點(diǎn)的前綴進(jìn)行比較來(lái)判斷節(jié)點(diǎn)間的關(guān)系。素?cái)?shù)編碼[11]方式是利用了素?cái)?shù)的獨(dú)特的性質(zhì)來(lái)決定節(jié)點(diǎn)間的關(guān)系?! ?更新 更新通常包括邊(或節(jié)點(diǎn))的插入和刪除,以及子樹(shù)的插入和刪除,這兩類基本操作分別對(duì)應(yīng)了在XML文檔中對(duì)一個(gè)標(biāo)簽和一個(gè)子文檔的操作。有關(guān)更新的研究,大致分為兩類,它伴隨著不同的查詢技術(shù),即前面提到的索引方式和編碼方式。 針對(duì)1-index[2],R.kaushik[12]等人首先提出了一套更新算法,包括邊的插入和刪除,以及子樹(shù)的插入和刪除。它避免了更新操作發(fā)生時(shí),對(duì)索引圖的重構(gòu)。之后,[13]對(duì)以上算法進(jìn)行了改
7、進(jìn),進(jìn)一步減小了更新后的索引圖的規(guī)模,并針對(duì)A(k)-index[3]提出了更新算法?! 』诰幋a模式的更新,往往依賴于具體的編碼技術(shù),對(duì)更新的操作,也就是編碼的過(guò)程。 4小結(jié) XML數(shù)據(jù)是一種半結(jié)構(gòu)化數(shù)據(jù)的實(shí)例。隨著XML的逐漸流行,關(guān)于XML的相關(guān)技術(shù)的研究,特別是如何快速的對(duì)結(jié)構(gòu)化的XML文檔進(jìn)行查詢,也已經(jīng)成為人們關(guān)注的焦點(diǎn),也是以后XML數(shù)據(jù)研究人員工作的重點(diǎn)。