基于模型检测的半结构化数据查询及其应用

《基于模型检测的半结构化数据查询及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、兰州大学硕士学位论文基于模型检测的半结构化数据查询及其应用姓名：刘林霞申请学位级别：硕士专业：计算机科学与技术、计算机软件与理论指导教师：吴尽昭20090501摘要Intemet的迅猛发展导致Web上的半结构化数据急剧膨胀，因此，对这类数据的查询日益成为信息技术领域一个重要的研究发展方向。现有的半结构化数据查询语言在查询方式以及查询效率上存在着不足。本文针对这些问题提出了将模型检测技术应用于半结构化数据查询的方法，并给出了该方法在现有半结构化数据查询语言上的应用过程。本文首先介绍了半结构化数据及其数据模型与查询语言。对现有的半结构化数据查询语言的查询方式及数据模型进

2、行分析，得知半结构化数据的数据模型通常表示为有向标记图，因此，对半结构化数据的查询操作就对应为从标记图中抽出信息，即查询过程也就是对半结构化数据库实例图查找满足查询条件的子图的过程。该过程涉及到图的等价问题，目前已有的两种等价关系为图同构和图双模拟。但是，对图同构问题并没有具体的多项式算法用于解决子图的同构问题也不能解决图的同构问题。判断两个图的双模拟等价过程可以在多项式时间内完成，但是会涉及到搜索实例图中匹配查询条件的子图过程，而该过程是NP完全的。针对以上问题，本文提出将模型检测技术应用到半结构化数据查询，也即是将时序逻辑公式y与图查询联系起来，且将数据库实例解

3、释为Kripke变迁系统。这样，查找数据库实例图中与查询相匹配的子图问题就简化为了对KTS查找满足时序逻辑公式缈的状态问题。这是模型检测问题的一个实例，众所周知，如果公式可是Cn公式，S是KTS系统，那么对缈的ar蜞型检测算法可以在关于KTS和公式大小的线性组合复杂度内完成。最后，本文将该技术应用于现有的半结构化数据查询语言LDrel和UnQL，具体解决了查询到时序逻辑公式的转换以及将数据库模型表示为KTS的过程。同时，给出了详尽的案例分析，使本文提出的方法更清晰、明确。关键字：半结构化数据，模型检测，CTL，OEM模型，Lorel，UnQLABSTRACTTher

4、apiddevelopmentofIntemetmustbeinvolvedinanextremeexpansionofsemi-structureddata,therefore，queryingonsuchdataisincreasinglybecominganimportantresearchfieldofinformationandtechnology．Existingsemi-structureddataquerylanguageshavedisadvantagesinquerymodelandqueryefficiency．Inthispaper,anew

5、methodisproposedtoimprovetheseproblems，namely,usingthemodelcheckingtechnologytosolvethequeriesofsemi-structureddata，thenaprocessofapplyingthismethodonexistingsemi—structureddataquerylanguageisprovided．Firstly,thisthesishasintroducedthesemi-structureddataanditsdatamodelandquerylanguages

6、．Undertheanalysisofthequerymodelanddatamodelofexistingquerylanguages，concludedthatitisacommonapproachtorepresentsemi-structureddatabyusingdirectedlabeledgraphs，thenaqueryonsemi—structureddatabaseisbecomestogetinformationstoredindirectedlabeledgraphs，i．e．queryissubstitutedforfmdingsubgr

7、aphswhichsatisfytherequirementsofthequeryfromdatabaseinstancegraph．However,thequerywouldinvolvegraphequivalence，therearetwokindsofpopulargraphequivalencerelations：graphisomorphismandgraphbisimulation，butnonerepresentsgoodperformance．Forexample，thegraphisomorphismexpressesneitherpolyn