數(shù)據(jù)庫模式匹配算法的研究.pdf

1、模式匹配被廣泛應用于數(shù)據(jù)庫相關領域中，例如數(shù)據(jù)集成、數(shù)據(jù)空間、DeepWeb、數(shù)據(jù)倉庫、以及本體合并等。針對模式匹配的研究已有幾十年的歷史，從早期的手工完成匹配操作到目前的自動發(fā)現(xiàn)匹配，人們已經(jīng)取得了很多研究成果。給定源模式和目標模式，模式匹配的目標是發(fā)現(xiàn)兩個模式間元素的對應關系，具有對應關系的元素表示相同或者相似的語義。由于模式匹配的發(fā)現(xiàn)是一個利用已有知識對元素語義進行挖掘和理解的過程，所以其在一定程度上相當于自然語言處理，這也體現(xiàn)了

2、模式匹配固有的困難性。因此，為進一步提高模式匹配的質(zhì)量，人們?nèi)孕枰嗟年P于模式匹配的研究。近些年，隨著互聯(lián)網(wǎng)的發(fā)展以及通訊工具的普及，人們對數(shù)據(jù)共享和交換的需求越來越強烈，這也使得模式匹配問題成為目前的研究熱點。所以針對模式匹配的研究不但具有理論意義而且具有實際應用基礎。
　　本文從數(shù)據(jù)庫的查詢?nèi)罩局袨閷傩蕴崛】捎糜谄ヅ涞慕y(tǒng)計信息，并以此為基礎，提出一些模式匹配的發(fā)現(xiàn)及改進算法。同時，本文對模式匹配在模式集成領域中的應用進行了研

3、究，提出了基于用戶偏好的多模式產(chǎn)生算法。本文主要針對關系模式的匹配問題進行探討，具體研究工作如下:
　　(1)匹配的發(fā)現(xiàn)
　　首先，本文利用屬性的出現(xiàn)頻率來發(fā)現(xiàn)匹配。通過日志中每個屬性在相應查詢子句中的出現(xiàn)頻率構建特征向量。采用聚類技術對不同屬性的特征向量進行分組，處在同一聚類中的屬性則具有相同或者相似的語義。為進一步提高聚類結果的準確性，通過最大相似性閾值來發(fā)現(xiàn)聚類中語義異常的屬性，并設計了異常屬性去除算法。實驗結果表明所

4、提出的方法具有較高的準確率。
　　其次，本文利用屬性在查詢結果的模式結構中的出現(xiàn)順序發(fā)現(xiàn)匹配。本文方法包含三個階段。第一，從查詢?nèi)罩局谐槿〕霈F(xiàn)序列，并對屬性在這些出現(xiàn)序列中的出現(xiàn)順序進行統(tǒng)計。第二，利用矩陣對屬性出現(xiàn)順序的統(tǒng)計信息進行組織。第三，針對具有不同基數(shù)的映射，采用兩種打分函數(shù)度量不同輸入模式統(tǒng)計信息矩陣間的相似性，并采用模擬退火算法尋找最優(yōu)映射。實驗結果表明所提出的方法能返回較準確的匹配。
　　最后，本文利用日志中

5、關于SQL語句內(nèi)容和結構的統(tǒng)計信息進行模式匹配。本文方法包括四個階段。第一階段對SQL語句的子句進行統(tǒng)計，并構建子句關聯(lián)圖cag。其次，利用cag構建“匹配對”集合，每個匹配對表示一對屬性序列。第三，度量匹配對的兩種相似性，即屬性(property)相似性和結構相似性。最后，設計兩種將匹配對分解成單一匹配的算法，并利用閾值策略選擇最優(yōu)匹配。實驗結果表明基于查詢語句的匹配方法是有效的、準確的。
　　(2)匹配的改進
　　針對匹

6、配不能適應數(shù)據(jù)實例包含分類的情況，本文提出模式匹配的改進算法。從源模式的數(shù)據(jù)實例中發(fā)現(xiàn)隱含的分類語義，并將其與匹配進行關聯(lián)以提高匹配的質(zhì)量。本文方法包含三個階段。首先，通過聚類技術發(fā)現(xiàn)源實例中的可能分類。其次，通過信息熵技術去除干擾屬性得到真正的分類屬性。最后，通過引入一個稱為c-mapping的概念實現(xiàn)分類語義和匹配間的關聯(lián)。實驗結果表明本文方法具有較好的性能。
　　(3)匹配的應用
　　模式匹配的最終目標是解決實際問題。