11背景与研究动机

《11背景与研究动机》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章續論1.1背景與研究動機近年來隨著全球資訊網(WWW)的興盛發展，因其跨平台的特性與網路的快速，WWW已經成為資訊分享的主要平台，然而隨著WWW的廣泛使用，www上資料的增多，且也因為WWW的便利，許多的企業紛紛藉由WWW作為資料交換的管道'為此W3C制定了XML(ExtensibleMarkupLanguage)，其設計之目的主要用來描述資料本身的涵義，因此XML允許使用者制定文件所需之標籤和結構。然而因XML文件的可自定標籤與其結構化之特性，使其在WWW上被廣泛的用來當作資料交換的工具。隨著XML文件的廣泛

2、使用與日益增加，如何從大量的XML文料中萃取出符合使用者需求之資料已成為重要的議題。這個議題可將分成結構化限制和關鍵字查詢這兩個部分進行探討。結構化限制之部分，W3C制訂了XPath與XQuery。XPath為路徑語言，其主要目的為用來定址XML文件中的某部份。而XQuery則是建立在XPath基礎之上，設計用來查詢XML資料，根據使用者所下的限定式由XML文件中萃取出使用者所需要的資料，其中W3C更定義了XMLXQueryUseCase來描述XQuery可以處理的各種情況。關鍵字查詢的部分，一般文件針對關鍵字做查詢

3、處理時'主要運用資訊檢索(InformationRetrieval)的相關技術，比對關鍵字與文件之相似度，回傳給使用者相似度較高之文件，然而有越來越多的研究將資訊檢索(InformationRetrieval)之技術套用在XML文件之資料搜尋。因此，本論文將在［李04］的XQuery查詢處理演算法中，加入資訊索引之技術。在［李04］的作法中，主要將使用者輸入之查詢句建立為查詢樹，在將查詢樹分解成若干個後置路徑，最後比對符合後置路徑之元素組合出最後答案，而我們主要將資訊檢索之技術運用於關鍵字之處理以及抓取出符合後置路徑

4、之元素，關鍵字的部份我們將採用BM25Scoingfunction計算元素跟關鍵字之分數，在將符合結構之元素的分數相加以做TopK之處理。1.2相關研究隨著XML資料越來越廣泛的被應用，如何從大量的XML資料中淬取出使用者所要的資料成為一個重要的議題。近來有許多的研究從不同的觀點包含了XML的結構查詢處理以及資訊檢索技術來解決這個問題。在XMLQuery中常會有跳層的路徑表示法，如a//b，研究［AJKP+02］針對這樣的問題，將每個XML的節點以preorder及postorder編碉，以快速的決定任意兩個節點是否

5、有ancestor-descendant或parent-child的關係。但在XML中A節點可能會有多個descendant節點B，相對的B節點也可能會有多個ancestor節點A，所以作者又利用stack來解決這樣的問題，當一個A節點確定為B節點的ancestor或parent在將其push進stack中，直到它不會再是以後任一個B節點的ancestor»再將其從stack中pop掉。但是當要選取下一個需要作structuraljoin的節點時，必須選取剩餘節點中preorder最小的節點，研究［JWLY03］應用

6、研究［JLWO03］中所提出的XR-Tree作為Index，直接跳過一些不需要作structuraljoin的節點。XR-Tree是以B+Tree為基本的資料結構，當我們給與他一個節點的preorder及postorder，XR-Tree能快速的找回這個節點的所有ancestor及descendant節點。但當Query中有多個跳層時，如a//b//c，［WPJ03］討論如何選擇運算的先後順序以達到最好的效率，作者提出五種尋找的方式DP，DPP，DPAP-EB，DPAP-LD，FP，其中DPP能花較少的時間找到最好的

7、structuraljoin的順序，而FP則是能花更少的時間找到一個較好的(但並不一定是最好的)structuraljoin順序。另外也有數種不同編碼的方式被提了出來。在研究［WPFY03］中，作者將整個XML文件編碼成一個序列(sequence)，Query也編碼成一個序列(sequence)»這個序列包含了其原本的結構，例如a/b/c，他會將其編碼成(a,e)(b,a)(c,b)，如此一來處理XMLquery可轉化為在XMLdocument中尋找相同的子序列‘並可避免許多Join的過程。研究［RM04］則提出PR

8、IX(PRufersequencesforIndexingXML)，主要是利用Prufer(1918)所提出針對labeledtree和sequence之間的one-to-onecorrespondence，而將XML文件及TwigQuery查詢句轉換成各自相對應的PruferSequence，再經過一連串的結構與數值的檢查，來確認TwigQu