XML復雜路徑表達式查詢處理技術研究.pdf

1、該文提出了如何將具有各種運算符的正則表達式轉化為查詢自動機的方法.針對XPath規(guī)范中規(guī)定的"∥"操作符,即祖先—后代關系操作符,我們提出了一個稱為模式自動機(Schema Automata)的數據結構,模式自動機可以接收所有可能出現(xiàn)在XML文檔中的片斷,也就是說,它可以匹配任何可能出現(xiàn)在XML文檔中的路徑模式;而傳統(tǒng)的自動機要想支持包含連接這一類非正則運算符是非常困難的.為了進一步提高模式自動機的性能,該文還提出了兩種優(yōu)化方法PSA和

2、RWS.前者將模式自動機作為索引的一部分存儲在磁盤上,避免了每次計算都要生成模式自動機的開銷,后者則是通過following集合和preceding集合來過濾掉模式自動機中多余的狀態(tài)和轉換函數來達到提高查詢效率的目的.為了支持自動機匹配算法,該文還提出了高效地支持自動機匹配算法的數據結構:路徑模式樹和路徑實例樹.通過與結構連接算法進行性能測試對比,我們發(fā)現(xiàn)自動機匹配算法的效率遠遠高于結構連接算法,PSA和RWS對自動機匹配算法的優(yōu)化也很

3、顯著.與傳統(tǒng)的關系數據庫中的查詢不同,針對半結構化數據的查詢更多的是要找到滿足某些特定模式的節(jié)點.近來,在簡單路徑查詢的問題得到較好解決的基礎上,人們將注意力轉移到Twig查詢中來.該文提出了如何利用索引技術來更好地解決Twig查詢的問題.根據路徑模式樹索引,我們給出了利用自動機匹配路徑模式樹索引解決這一問題的方法,圍繞這一方法,該文對Twig查詢自動機的構建,Twig查詢自動機與路徑模式樹的匹配等算法進行了討論,并與用傳統(tǒng)的結構連接方