1、子圖匹配(Basic Subgraph Pattern Matching)是RDF圖數(shù)據(jù)管理中的一種基本查詢類型，又稱子圖同構(gòu)(Subgraph Isomorphism)，是一個(gè)NP-Complete問題。隨著語義網(wǎng)的發(fā)展和開放鏈接數(shù)據(jù)運(yùn)動(dòng)的發(fā)展，越來越多的數(shù)據(jù)通過RDF格式發(fā)布出來。高時(shí)間復(fù)雜度和巨大的數(shù)據(jù)規(guī)模給RDF圖數(shù)據(jù)的管理帶來了巨大挑戰(zhàn)。目前的單機(jī)查詢算法由于受限與子圖匹配問題的特性，往往會(huì)引入大量的連接操作，效率較低;基于M

2、apReduce的分布式查詢方案受限于MapReduce的迭代機(jī)制，查詢效率很難提升。因此，如何高效地在大規(guī)模的RDF圖數(shù)據(jù)上解決子圖匹配問題，成為一個(gè)具有挑戰(zhàn)性的工作。
　　本文提出了集中式和分布式兩種RDF圖數(shù)據(jù)查詢方案。在集中式查詢方案中，數(shù)據(jù)圖根據(jù)頂點(diǎn)度數(shù)的大小拆分成星狀的小規(guī)模子圖，并將這每個(gè)子圖編碼成一個(gè)二進(jìn)制串。將子圖匹配的部分操作轉(zhuǎn)換成二進(jìn)制位的“與”和“或”操作。使用該二進(jìn)制串來過濾出可能的子結(jié)果。然后將子結(jié)果拼

3、接成完整的查詢結(jié)果。該方案避免了大多數(shù)的連接操作，使得每次訪問索引獲得一條三元組信息優(yōu)化到每次訪問索引獲得一組三元組信息。這種查詢方案提高了每次查詢獲得的信息量，大大減少了連接操作數(shù)量。在分布式查詢方案中，將RDF圖中的每個(gè)頂點(diǎn)都視為可執(zhí)行計(jì)算的單元，將整個(gè)圖映射成可互相傳遞消息的頂點(diǎn)集。這種模型基于BSP計(jì)算模型設(shè)計(jì)，充分利用了圖的特點(diǎn)，使用消息傳遞的方式逐步完善查詢圖，逐一減少變量數(shù)量，最終得到查詢結(jié)果，避免了迭代的MapReduc

4、e計(jì)算模型在解決圖計(jì)算問題時(shí)存在的很多限制，查詢效率明顯提高。本文設(shè)計(jì)的實(shí)驗(yàn)從索引的空間代價(jià)和查詢響應(yīng)時(shí)間等方面對(duì)上述兩種方法做了評(píng)價(jià)，集中式查詢方案在查詢響應(yīng)時(shí)間上優(yōu)于目前性能最好的通用RDF集中式查詢引擎RDF-3X和gStore，分布式查詢方案也較MapReduce框架下實(shí)現(xiàn)的查詢方案有較大的性能提升。
　　綜上所述，本文針對(duì)RDF圖數(shù)據(jù)上的子圖匹配問題提出了單機(jī)集中式查詢和集群分布式查詢兩種查詢方案，在索引結(jié)構(gòu)、數(shù)據(jù)編碼、