1、資源描述框架（Resource Description Framework，簡稱RDF）是語義Web網(wǎng)所使用的基本標記語言，在諸多領(lǐng)域中有廣泛應(yīng)用。由于現(xiàn)有的本體抽取、標注方法和測量技術(shù)存在誤差和噪聲，使得不確定RDF數(shù)據(jù)普遍存在。近年來，對于不確定RDF數(shù)據(jù)的查詢研究逐漸成為熱點。由于不確定RDF數(shù)據(jù)可以建模為不確定RDF圖，那么對于不確定RDF數(shù)據(jù)的關(guān)鍵字查詢的研究實際上就是對于不確定圖上關(guān)鍵字查詢的研究。本文在已有研究的基礎(chǔ)上，提

2、出了兩種基于r-clique的不確定RDF關(guān)鍵字查詢的算法——KSABR和HABR。
　　單詞”clique”的中文釋義是“極大團、子群體”，這里指不確定圖中的子圖，字母r是一個表示距離閾值的變量。所以，r-clique是指包含所有查詢關(guān)鍵字的任意兩個節(jié)點的距離不大于給定值r的子圖。為了提高查詢速度，本文提出了一種多項式時延的近似算法來構(gòu)建r-clique。
　　算法KSABR(Keyword Search Algorith

3、m Based on r-clique)將不確定RDF數(shù)據(jù)上的關(guān)鍵字查詢問題映射為尋找不確定圖上的r-cliques的問題。為了提高查詢結(jié)果的質(zhì)量，在KSABR的基礎(chǔ)上又進一步提出了精度更高的算法:HABR（Efficient Algorithm Based on r-clique）。HABR中采用了打分函數(shù)對結(jié)果進行排序。對于得到的k個結(jié)果，HABR算法調(diào)用打分函數(shù)對結(jié)果進行排序，然后將top-k個結(jié)果返回給用戶。
　　為了進一

4、步提高查詢的速度，本文設(shè)計了兩種索引結(jié)構(gòu)——KI(KeywordInverted Index)和PI(Probabilistic Inverted Index)。KI中存放的是關(guān)鍵字和節(jié)點之間的映射關(guān)系，它可以用來實現(xiàn)結(jié)構(gòu)剪枝和概率剪枝。PI中存放的是關(guān)鍵字節(jié)點和r-clique之間的映射關(guān)系，它可以用來實現(xiàn)打分函數(shù)。
　　實驗證明，本論文提出的算法KSABR在時間性能上具有較好的性能，而算法HABR在時間性能和結(jié)果質(zhì)量上都具有較