圖數(shù)據(jù)庫中子圖查詢技術(shù)研究.pdf

1、作為一種通用的數(shù)據(jù)結(jié)構(gòu)，圖被廣泛用來建模和表示多種復(fù)雜的結(jié)構(gòu)化數(shù)據(jù)。近年來，對(duì)累積的大量圖數(shù)據(jù)（即圖數(shù)據(jù)庫）的管理受到研究者的關(guān)注。子圖查詢是一種具有很強(qiáng)現(xiàn)實(shí)意義的查詢類型，主要包括精確子圖查詢和相似性子圖查詢。具體來說，給定圖數(shù)據(jù)庫Ｄ，查詢圖，精確子圖查詢返回集合{∈|?′?,.′與是同構(gòu)圖}，相似子圖查詢返回集合{∈|?′?′與是相似圖。本文針對(duì)上述兩種子圖查詢給出有效解決方法。
　　對(duì)于精確子圖查詢，本文采用過濾--驗(yàn)證機(jī)制

2、，從數(shù)據(jù)庫中提取出的特定頻繁子圖稱為特征，過濾器即是由特征壓縮而成的一棵索引樹，由于特征之間共享誘導(dǎo)子圖，過濾階段多個(gè)特征所共享的誘導(dǎo)子圖只與查詢圖做一次子圖同構(gòu)檢測(cè)，所以過濾效率明顯優(yōu)于現(xiàn)有方法?？紤]到提取特征開銷較大，本文又提出一種高效的提取特征方法，該方法可以保證提取出的特征的過濾效果。理論分析與實(shí)驗(yàn)驗(yàn)證均表明我們提出方法優(yōu)于現(xiàn)有方法。
　　對(duì)于相似性子圖查詢，相似圖定義為滿足拓?fù)渫瑯?gòu)的兩圖之間編輯距離小于某一給定域值，現(xiàn)有

3、方法多數(shù)采用過濾--驗(yàn)證框架，在此框架下，這些工作主要集中精力于建立有效索引來提高過濾效果上，卻很少考慮設(shè)計(jì)高效的驗(yàn)證方法，這些方法在驗(yàn)證查詢圖與數(shù)據(jù)庫中圖是否滿足相似性子圖查詢要求時(shí)均需枚舉中的與拓?fù)渫瑯?gòu)的子圖,直至找到一個(gè)與距離小于域值的子圖為止。枚舉拓?fù)渥訄D計(jì)算代價(jià)巨大。本文提出方法無需枚舉子圖，而是將問題轉(zhuǎn)化到高效計(jì)算兩圖編輯距離上來.通過分析問題具有的特殊性質(zhì),設(shè)計(jì)一種巧妙的計(jì)算編輯距離的啟發(fā)式方法,來顯著提高驗(yàn)證階段的效率。