【摘 要】
：
检验查询可满足性是XML文档查询的一个重要问题。Active XML(AXML)文档在XML文档中引入嵌入式Web服务,增强了文档的动态性和灵活性,同时也为现有文档查询可满足性问题的解决方法提出了新的要求和挑战。研究了模式约束下的AXML文档查询可满足性问题,给出了AXML查询可满足性问题的形式化定义,基于树自动机理论,针对XPath树模式查询片段{"/,//,[]"},提出了一种多项式时间的AX
【机 构】
：
哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001 哈尔滨工业大学计算机科学与技术学院 哈尔
【出 处】
：
第二十五届中国数据库学术会议(NDBC2008)
论文部分内容阅读
检验查询可满足性是XML文档查询的一个重要问题。Active XML(AXML)文档在XML文档中引入嵌入式Web服务,增强了文档的动态性和灵活性,同时也为现有文档查询可满足性问题的解决方法提出了新的要求和挑战。研究了模式约束下的AXML文档查询可满足性问题,给出了AXML查询可满足性问题的形式化定义,基于树自动机理论,针对XPath树模式查询片段{"/,//,[]"},提出了一种多项式时间的AXML文档查询可满足性检验算法。实验数据表明,提出的算法在查询过程中以较小的代价显著地节省查询处理时间.
其他文献
互联网上的信息与日俱增,随着信息检索技术的发展,用户已经能够通过Google,Yahoo,Baidu等搜索引擎提供和查询接口查询互联网中大量的文本数据库而得到一部分用户所需要得到的信息.然而,互联网上的更多信息是包含在网页后台的关系数据库中的,访问这些数据库需要用户了解数据库的数据模式,并且熟悉结构化查询语言,这对于普通用户来说太困难了.因此,提出了一种新的查询算法,并且在查询算法中加入短语的识别
基于马尔可夫链描述软件系统控制转移的动态特性,研究了基于马尔可夫分析方法的可信软件的可靠性建模问题。针对模块化的软件系统,综合模块自身的可靠性和模块间的转移调用对其在系统中的重要程度两个方面,分别定义了模块的可靠性函数和模块在系统中重要程度的函数,最后给出了系统可靠性的建模方法和相关函数.
正确发现流程实际运作情况对工作流管理有着重要意义。流程挖掘抽取系统日志信息,挖掘流程真实的运作模型.给出一种可学习循环结构的流程挖掘方法。首先根据工作流实例中任务间的执行顺序,把日志数据划分成不同聚类,缩减挖掘过程中的搜索空间.然后,通过扫描日志识别出处于模型最外层循环结构的记录,采用迭代方法来挖掘循环结构模型,并将该循环结构模型添加进原工作流模型中.最后,基于该算法实现了工作流模型挖掘原型,实验
在度量空间,像数字图像、文档和DNA序列这样的对象通常用高维特征向量点和距离函数表达语义。如何高效的在度量空间中处理高维数据的相似查询是对等网络数据管理的基本问题。以往在这方面的工作有许多局限性,例如不能适应高度动态的网络;数据倾斜时,查询效率下降等。设计了一个高效的算法——Dragon——来处理度量空间中的相似查询.Dragon通过以下设计高效地处理查询:1)Dragon是建立在之前设计的对等系
工作流性能分析是对工作流进行评价和优化的基础,时间性能则是衡量工作流性能的一个重要指标。利用概率论中关于服从指数分布的随机变量的分布函数、密度函数及数学期望的基本性质,详细地讨论了组成SPN模型的串行、并行、选择和循环4种基本结构的平均延迟时间,得出了通用的SPN模型平均延迟时间公式.通过对复杂SPN模型的等效化简,实现对工作流时间性能的分析.最后,通过实例说明了该方法的可行性和有效性。
在时间序列数据流中过滤预先定义的一些模式,可以实现对特定应用事件的监控.基于楔形区的时间序列过滤查询算法和以往的算法相比,明显地减小了执行代价.为了提高基于楔形区的过滤查询算法的精度,提出了一种针对时间序列数据流过滤的双向封装思想,不仅对楔形区进行封装,而且还对流动的时间序列进行封装.在此基础上,定义了时间序列与模式的下限函数,并设计了时间序列流双向封装过滤查询算法。由于对数据流的封装,减小了时间
随着计算机应用的不断发展和深入,高维数据的应用也越来越广泛.而传统的数据库索引技术如B+-Tree并不能提供高效的多维数据的存取.提出一种高效的多维点访问方法RP-Tree,该方法基于R-Tree结构,通过在插入算法中引入新的节点重构技术有效减少R-Tree中节点间的重叠区域.通过大量实验,证明该方法在经过测试的所有不同分布的高维点数据的存取中,无论是点查询还是区域查询,都要优于R*-Tree和K
MLCA是判断XML非完全结构查询结果是否有意义的重要方法之一,但目前MLCA求解方法是基于树模型的方法,且对任意一对节点的MLCA求解效率低。采用XML图模型下的基于区间编码的XML存储结构和基于前驱索引集合(SSPI)的引用关系存储结构,结合存储结构提出一种高效的任意节点对的MLCA求解方法。实验表明,与Timber的MLCA算法相比,该方法的运行时间平均降低95％.
研究了树型文档的结构相似性度量,提出了一种二维的树型文档结构相似性度量方法。该方法首先计算文档树的结构摘要以对树型文档进行约简.然后,提出了两个特征集,它们分别从不同的角度反映了摘要树中的结构特征,而且相互补充.与这两个特征集相对应,提出了一种二维的结构相似性度量,其中包含两个相似度:纵向结构相似度和横向结构相似度,将它们结合起来,可以得到比较准确的最终的相似度.在实际数据集和合成数据集上的实验结
关键字查询方法为用户提供了友好便捷的查询方式,如何定义有效的查询语义是XML关键字查询要解决的基本问题。重点研究了XML关键字查询的语义,以实体作为基本语义单元,提出了最低公共实体祖先LCEA的概念,一个LCEA结点是描述现实世界完整信息单元的实体对象.在LCEA的基础上,提出了有意义的最低公共实体祖先MLCEA,在为用户提供简单易用查询方式的同时,避免了漏解和返回无意义结果的现象.提出了计算LC