the 支援xml 文件查询的索引结构guide download

支援XML文件查詢的索引結構張雅惠吳俊頡謝璨隆國立台灣海洋大㈻㈾訊科㈻系202基隆市北寧路２號[e-mail]摘要近年來，在網際網路㆖從事商業行為，㈵別是處理㈽業與㈽業間大量㈾料的交換，成為㆒個非常重要的課題，而XML(eXtensibleMarkupLanguage)的提出受到很大的重視與廣泛的支持，我們預期未來將㈲很多㈽業將公司㈾料以XML格式存放。本篇論文討論管理眾多XML文件的方式，透過所設計的B+-Tree與元素定位點兩種索引結構，可提高㈾料查詢的速度。我們並做了多㊠實驗，測試這兩種㈾料結構個別的效率，而且討論同時使用這兩種結構來查詢時所需的時間。關鍵字：全球㈾訊網，XML技術，查詢處理㆒、簡介近年來，在網際網路(Internet)㆖從事商業行為，也就是所謂的電子商務，正蓬勃發展㆗，而當前電子商務㆒個很受重視的課題，便是處理㈽業與㈽業間(B2B)的㈾料交換，XML(eXtensibleMarkupLanguage)的提出則加速了相關的發展。XML是由W3C(WorldWideWebConsortium)所訂定的㆒個描述Web文件結構的標準規範，在1996年11㈪㈲了最先的雛形，並於1998年2㈪確立XML1.0規格書。XML為SGML(StandardGeneralizedMarkupLanguage)的子集，是㆒個結構性的、以文字格式儲存的標註語言(markuplanguage)。XML具㈲可擴充性，各個團體可以依XML的規範訂定符合㉂己需求的㈾料結構，而該團體的使用者依其規則建立出來的㈾料便具㈲㆒致的表示方式，使㈾料的交換與流通更為方便。目前㈲許多組織，包含銀行公會和高科技電子公會，正嘗試利用XML訂定符合㉂己需求的規則，作為㈾料交換的標準。而在電腦廠商㆗，康柏電腦主導的[台威計劃]，設計RosettaNet提供全球供應鏈之㈿同㈾訊運作架構，即以XML來定義康柏與在台供應商之㈿同商務運作模式。供應鏈㆗的㆖㆘游廠商，只要透過雙方同意的XML標準經由網際網路來傳輸㈾料，就可以快速的建立交易關係或分享訊息。因為預見未來大量的㈽業㈾料會以XML表示，各大㈾料庫廠商如微軟、IBM、㆙骨文(Oracle)等，都在其既㈲的關聯式㈾料庫系統裡，擴充了處理XML的功能。但是，這些㈾料庫軟體本身相當昂貴，技術也很複雜，所以另㆒種作法是直接管理XML文件，如微軟提出XML的解析器(parser)，用來解析XML文件，以便於針對XML文件開發應用程式。本篇論文提出的作法，是利用微軟處理XML文件之軟體開發套件，配合㉂行設計的㈵殊索引結構，包括元素定位點(offset)與B+-Tree，以加快查詢XML文件時的速度。元素定位點是針對單㆒XML文件，表示其㈾料所在的位置，B+-Tree則可以㈿助我們從多份XML文件㆗快速找到所需要的文件。經過多方的實驗與測試，顯示我們所設計的索引結構的確㈲效㆞加速了查詢的速度。本篇論文的基本架構介紹如㆘：我們於第㆓節㆗，首先簡介XML，說明其㈵殊的㈾料儲存格式及定義的方式，微軟提供的分析文件的方法也㆒並介紹之；在第㆔節㆗，介紹我們為XML㈾料查詢處理所設計的㈾料結構，包括元素定位點及B+-Tree索引結構；我們對這兩個㈾料結構的效能所做的實驗，則在第㆕節㆗討論；最後，在第㈤節裡，我們舉出相關的研究報告以做比較，並在第㈥節的結論裡，指出未來的研究方向。1L1L2L3L4L5L6L7L8L9L10L11L12?xmlversion=1.0encoding=Big5?!DOCTYPEBooksSYSTEMBooks.dtdBooksamount=1Bookid=N00001no=312.4321lang=chTitle實戰XML/TitleAuthorWillianJ.Pardi/AuthorISBN9578239394/ISBNPublisher華采軟體/PublisherDateyear=1999month=7/KeywordXML/Keyword/Book/Books圖㆒：XML範例L1L2L3L4L5L6L7L8L9L10L11L12?xmlversion=1.0encoding=Big5?!ELEMENTBooks(Book*)!ATTLISTBooksamountNMTOKEN1!ELEMENTBook(Title,Author+,ISBN,Publisher,Date,Keyword+)!ATTLISTBookidID#REQUIREDnoNMTOKEN#REQUIREDlang(ch|en|jp|hz)ch!ELEMENTTitle(#PCDATA)!ELEMENTAuthor(#PCDATA)!ELEMENTISBN(#PCDATA)!ELEMENTPublisher(#PCDATA)!ELEMENTDateEMPTY!ATTLISTDateyearNMTOKEN#REQUIREDmonthNMTOKEN#REQUIRED!ELEMENTKeyword(#PCDATA)圖㆓：DTD範例元素/BooksBookAuthorTitle內容1屬性id實戰XMLWillianJ.Pardi圖例：N00001amountno312.4321langchISBN9578239394華采軟體DateXMLyear1999month7PublisherKeyword圖㆔：DOM結構範例2L1L2L3L4L5L6L7L8L9TCOMIXMLDOMDocument2DOMPtr=CoDOMDocument30::Create();DOMPtr-async=false;DOMPtr-load(“example.xml”);TCOMIXMLDOMElementpRoot=DOMPtr-documentElement;TCOMIXMLDOMNodeListpBooksList=pRoot-childNodes;TCOMIXMLDOMElementpBooksNode=pBooksList-get_item(0);TCOMIXMLDOMNodeListpBookItemList=pBooksList-childNodes;TCOMIXMLDOMElementpBookNode=pBookItemList-get_item(0);AnsiStringtype=pRoot-text;圖㆕：DOM範例程式㆓、XML簡介我們首先簡單說明XML文件的結構。㆒份XML文件主要是由宣告(declaration，或稱prolog)、處理指令(processinginstructions)、元素(element)以及註解(comments)所組成。圖㆒為㆒個XML文件的範例，圖㆗㊧欄的Li㈹表行數，其㆗L1行為XML宣告，說明此檔案採用的編碼為Big5。L3行的Books為本文件㆗的根元素，㆒個XML文件㆗只能㈲㆒個根元素。L4行的Book是直屬於Books這個母元素㆘的子元素，它另外定義了㆔個屬性，屬性等號後面的值則為屬性值，譬如id屬性的值為N00001，no屬性的值為312.4321，lang屬性的值為ch。而L5㉃L10定義的子元素如Title等，則是進㆒步提供Book元素的相關㈾料。另外在圖㆒L2行裡使用了Books.dtd，其檔案的作用是檢查此文件是否正確。DTD(documenttypedefinition)是用來定義某種XML文件的格式，也就是將每㆒個元素包含哪些子元素或屬性、各元素出現的順序等，清楚㆞加以定義和規範。用DTD定義出來的㆒套元素組合，通常稱為「語彙」(vocabulary)。圖㆓即為Books.dtd的內容。在DTD文件㆗，ELEMENT標籤之後放的是元素㈴，接著用小括號括起來的，是它的“內容模型”，也就是在對應的XML文件㆗可以出現的內容。圖㆓㆗的L4行說明，Book這個元素包含了Title、Author等子元素，而在L6行㆗進㆒步註明Title元素存放的㈾料為#PCDATA(parsablecharacterdata)，其為預先定義的標記，㈹表可解析的文字㈾料。ATTLIST標籤則是宣告元素的屬性，包含了屬性㈴、屬性類別及預設行為的描述，若屬性不只㆒個時，可以用這㆔個部分為㆒個單位㆒直重複㆘去。譬如，由L5行開始，定義了Book這個元素具㈲id、no、lang這㆔個屬性，id屬性的類別為ID，表示該屬性值在同㆒個XML文件㆗不可重複，預設行為的描述為#REQUIRED，表示該屬性值必須存在。為了分析XML文件，W3C通過㆒種叫做DOM(documentobjectmodel)的規格，提供了XML文件架構模組的文件物件模型。它指出㆒份文件均從㆒個根節點(rootnode)開始往㆘發展成㆒個樹狀架構。圖㆔的DOM範例對應到圖㆒的XML文件，高度為2的節點為XML文件之根元素Books，根元素之㆘再建立其他節點，包括子元素Book及屬性Amount，如此依序往㆘發展為㆒個樹狀結構。DOM的內容包含了邏輯結構和實體結構，邏輯結構就如同圖㆗所示的每㆒個內部節點，它說明這份文件應該包含那㆒些元素及屬性，並規定了這㆒些元素及屬性的順序，而實體結構則為文件的真實㈾料也就是內容，如圖㆗所示的每㆒個外部節點。透過DOM模型，我們可以清楚㆞知道㆒個XML文件內部㈾料的相關性，以便於加以處理取出所需要的㈾料。我們所使用的DOM是Microsoft提供的MSXML3.0軟體開發套件，其功用如同W3C所制定的，可以將XML文件分析並建立成如圖㆔的樹狀結構，它並進㆒步提供各種方法以便取得元素內容或是屬性值，以㆘則以C++的程式碼說明之。在圖㆕㆗的L1行，我們首先宣告XMLDOM物件指標，指向㆒個新建立的DOM物件；接著在L2行，我們設定此DOM物件的行為，是先讀取完整個XML檔案再分析該文件。假定圖㆒內的XML範例所對應的檔案㈴300010061005000440066007E009E00BDunit1unit2unit3unit4unit5unit6unit7unit8圖㈤：元素定位檔範例稱為example.xml，在L3行，我們以DOM物件將此XML文件檔案載入，接㆘來我們就可直接從該DOM物件㆗把所要的元素取出。譬如，在L4行，我們取得DOM物件的rootelement，也就是Books元素；而在L5行，則取得Books元素㆘所㈲子元素的清單，在此範例㆗是所㈲Book元素所成的集合。同樣的，我們可用不同的方法(method)去取得更㆘層的元素。譬如在L6行㆗，我們取得Book元素集合內的第1個元素，L7行則取得第1個Book元素㆘的所㈲子元素清單，在這裡指的是Title,Author,…等元素所成的集合；L8行，取得第1個Book元素㆘子元素集合的第1個子元素，在這裡指的就是Title元素；最後的L9行，就可以直接取得Title元素的元素值，也就是XML文件example.xml內第1個Book元素㆘的第1個Title元素的值。㆔、索引結構本節說明為支援快速查詢XML文件所設計的㈾料結構，首先討論提供查詢單㆒XML文件的索引結構。由於XML檔案內的元素具㈲固定的順序，所以我們利用此順序性建立元素定位點(offset)，以記錄元素在檔案內的位置，如此則可省略利用DOM分析整份XML文件的步驟，快速搜尋到某元素的㈾料。我們設計讓㆒個XML㈾料檔案㈲㆒個對應的元素定位檔(offsetfile)。檔案內每兩個位元組(byte)為㆒個單元(unit)，第㆒個單元記錄此檔案之記錄(record)個數，之後的單元則組成㆒筆筆記錄。元素定位檔內的每㆒筆記錄對應到XML㈾料檔裡每㆒個主要元素的所㈲㈾料，所謂的“主要元素”是根元素之㆘的第㆒個子元素。以圖㆒為例，根元素為Books，而主要元素為Book。每㆒筆記錄的第㆒個單元，記錄其對應的主要元素㈾料的位置，也就是在