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

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

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

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

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

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

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