一种改进XML模式树查询最小化算法

对XML模式树查询进行最小化查询优化,是左右XML数据查询处理性能的关键因素。对模式树查询最小化技术进行了研究,结合XML结构索引提出了一种改进的XML模式树查询最小化算法。该算法有效地解决了普遍意义上的语法层次优化中不能有效删除冗余节点的缺陷,从而提高了查询效率。实验结果表明该算法是正确的和有效的。     

DTD约束下的XML树模式查询最小化

目前大部分XML查询语言都使用树模式来匹配待查询的XML文档树以得到所需要的、与模式树相吻合的查询结果,此效率在很大程度上取决于XML模式树的大小,那么尽可能快速地查找并删除查询模式树中的冗余节点就变得十分重要。重点讨论DTD约束下树模式的最小化问题,将DTD兄弟约束SC拓展成扩展兄弟约束ESC,使其能够表达DTD约束中的祖先-后代关系;并指出只包含{ESC,/,//,[],*}的查询树模式的最小化问题的复杂度是指数级的,且当模式树是分支受限的时候,其最小化问题的复杂度是多项式时间的;最后给出了一个多项式时间的受限分支的模式树最小化算法。     

演绎数据库中语义查询的动态优化算法

演绎数据库的语义查询优化是利用数据库中的完整性约束，将用户提交的查询转换为与原查询等价且执行效率更高的查询规则。该文提出的动态语义优化算法在查询计算过程中动态约去存在的空展开式，使得查询时间开销的节省可用所除去的空展开式规模大小衡量，较适用于含有大量空展开式的演绎数据库。     

演绎数据库中语义查询的动态优化算法

演绎数据库的语义查询优化是利用数据库中的完整性约束，将用户提交的查询转换为与原查询等价且执行效率更高的查询规则。该文提出的动态语义优化算法在查询计算过程中动态约去存在的空展开式，使得查询时间开销的节省可用所除去的空展开式规模大小衡量，较适用于含有大量空展开式的演绎数据库。     

一种基于结构特征的XML数据查询方法

针对XML数据特有的树型结构模式，提出了一种将树型结构的XML数据和查询语句转化为特定格式的字符串，基于串匹配原理对结构复杂的XML数据进行查询的方法，避免了传统的基于路径的查询方式所必需的路径之间的连接（join）操作，从而提高查询效率。利用本文提出的编码方式，可以建立关于XML数据结构和数据内容舍为一体的索引。实验显示，本文使用的针对XML数据查询的方法比传统的基于连接操作的数据查询方式高效，且本方法具有良好的扩展性。     

一种可扩展的XPath查询最小化算法框架

XPath是XML的基本查询语言,XPath查询最小化对于提高XML数据库的查询性能具有重要意义.但是,由于XPath查询最小化是一个coNP完备问题,大部分已有的算法局限于处理简单的XPath片段.本文从一个新的角度入手,综合考虑完备性和高效性,提出了一个新的查询最小化框架,与已有算法"面向结点",即逐个删除冗余结点的解决思路不同,本文提出"面向树模式"的方式,即通过计算树模式的自同态映射,寻找目标结点集最小的自同态映射,进而求解最小等价查询树的方法.该方法具有较高的效率,而且在--Z..情况下是完备的,尤其是可以进一步扩展到更复杂的XPath片段.本文以此框架为基础,给出一个可以计算复杂查询模式的算法.     

基于本体的半结构化数据的柔性查询

半结构化数据库没有固定的库模式，用户对其结构难以产生清晰的认识，从而无法有效地查询所需的内容．提出了一种基于本体的柔性查询，用户通过了解数据库本体语义信息而发出的查询不必遵循严格的数据库模式也能得出结果．由于在半结构化数据库上直接查找效率很低，故在其上生成描述结构模式的概念本体库．查询模块先在本体库上评估能否得出查询结果，再在数据库上执行查询．然而由于本体库可能是图的形式，其查询代价仍然很高，本质上是NP问题，进一步研究了将图转化为树的方法，并给出了相应的算法．     

一种自底向上的静态语义查询优化算法

演绎数据库语义查询优化是运用数据库中的语义知识，即完整性约束条件，将用户提交的一种查询转换为能有效执行，并与原查询等价的查询的一种优化方法．至今在这一领域已有了许多的算法，但大多是基于自顶向下的查询计算模式．而本文提出的静态语义查询优化算法及其改进算法是在优化“并”和“连接”操作的过程中进行自底向上的查询计算，因此相对自顶向下的计算方式更有效地提高了查询执行效率．     

基于空值修复的数据库一致性查询方法*

完整性约束常用来定义数据库的数据语义,违反约束的数据库实例为不一致数据库,返回含有不一致结果的查询称为不一致查询。一致性查询目的在于不修改数据库实例而从不一致数据库获取满足约束的查询结果,已有方法因其支持的约束类型有限或计算复杂度高而影响其应用范围。提出了一种基于空值修复的数据库一致性查询方法,首先将原始完整性约束转换为与查询相关的统一约束,然后根据统一约束对原SQL查询进行查询重写,重写后的查询将不一致属性值当做空值来处理以获得满足完整性约束的结果。系统实现与实验证明,该方法在多种完整性约束类型与SQL     

外包XML数据库查询验证技术

外包XML数据库的查询验证目标是保证XML数据和结构的可信性.为此,设计一种基于RMH树的数据结构,改进现有查询验证算法,对XML数据和结构进行真实性、完整性和最新性的验证,并且使数据的完整性验证具有隐私保护功能.理论分析和实验结果表明,该方案在查询验证效率、存储成本、安全性等方面均优于现有验证方案.     

DTD约束下的树模式查询的一致性判断

树模式查询被广泛地应用XML数据查询中。树模式查询的一致性判断可以避免不必要的计算,节省查询时间,从而提高查询效率。给出了查询一致性的定义,基于子路径的概念,提出文档类型定义(DTD)约束下的树模式查询的一致性判断算法,并对算法的时间复杂度进行了分析。通过分析比较,该算法是有效的。     

Tree pattern query minimization

Tree patterns form a natural basis to query tree-structured data such as XML and LDAP. To improve the efficiency of tree pattern matching, it is essential to quickly identify and eliminate redundant nodes in the pattern. In this paper, we study tree pattern minimization both in the absence and in the presence of integrity constraints (ICs) on the underlying tree-structured database. In the absence of ICs, we develop a polynomial-time query minimization algorithm called CIM, whose efficiency stems from two key properties: (i) a node cannot be redundant unless its children are; and (ii) the order of elimination of redundant nodes is immaterial. When ICs are considered for minimization, we develop a technique for query minimization based on three fundamental operations: augmentation (an adaptation of the well-known chase procedure), minimization (based on homomorphism techniques), and reduction. We show the surprising result that the algorithm, referred to as ACIM, obtained by first augmenting the tree pattern using ICs, and then applying CIM, always finds the unique minimal equivalent query. While ACIM is polynomial time, it can be expensive in practice because of its inherent non-locality. We then present a fast algorithm, CDM, that identifies and eliminates local redundancies due to ICs, based on propagating "information labels" up the tree pattern. CDM can be applied prior to ACIM for improving the minimization efficiency. We complement our analytical results with an experimental study that shows the effectiveness of our tree pattern minimization techniques.     

Containment of partially specified tree-pattern queries in the presence of dimension graphs

Nowadays, huge volumes of data are organized or exported in tree-structured form. Querying capabilities are provided through tree-pattern queries. The need for querying tree-structured data sources when their structure is not fully known, and the need to integrate multiple data sources with different tree structures have driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In this paper, we consider a query language that allows the partial specification of a tree pattern. Queries in this language range from structureless keyword-based queries to completely specified tree patterns. To support the evaluation of partially specified queries, we use semantically rich constructs, called dimension graphs, which abstract structural information of the tree-structured data. We address the problem of query containment in the presence of dimension graphs and we provide necessary and sufficient conditions for query containment. As checking query containment can be expensive, we suggest two heuristic approaches for query containment in the presence of dimension graphs. Our approaches are based on extracting structural information from the dimension graph that can be added to the queries while preserving equivalence with respect to the dimension graph. We considered both cases: extracting and storing different types of structural information in advance, and extracting information on-the-fly (at query time). Both approaches are implemented, validated, and compared through experimental evaluation.     

Answering why-not questions on KNN queries

Being decades of study, the usability of database systems have received more attention in recent years. Now it is especially able to explain missing objects in a query result, which is called “why-not” questions, and is the focus of concern. This paper studies the problem of answering whynot questions on KNN queries. In our real life, many users would like to use KNN queries to investigate the surrounding circumstances. Nevertheless, they often feel disappointed when finding the result not including their expected objects. In this paper, we use the query refinement approach to resolve the problem. Given the original KNN query and a set of missing objects as input, our algorithm offer a refined KNN query that includes the missing objects to the user. The experimental results demonstrate the efficiency of our proposed optimizations and algorithms.     

道路网络中的多类型K最近邻查询

空间数据库的多类型最近邻查询逐渐受到人们的关注,关于K最近邻查询的研究也较多,但多类型K最近邻查询的研究还存在空白。针对道路网络中的多类型K-最近邻（MT-KNN）问题,结合多类型最近邻查询及K最近邻查询的理论,提出了多类型K最近邻查询算法。通过对分层编码视图进行扩展,建立了多路径分层编码视图,并利用逐步扩展局部路径的方法,实现了多类型K最近邻查询,实验结果分析表明算法具有较好的性能。     

移动对象的动态反向k最近邻研究

反向最近邻查询是空间数据库中最重要的算法之一。传统的反向最近邻查询方法主要是针对静态对象的查询,随着无线通讯和定位技术的快速发展,移动对象发出的查询请求成为新的研究热点。该文将TPR-tree作为算法的索引结构,并提出了基于矩形框的对角线的修剪策略,将半平面修剪策略进行改进,给出了移动对象的动态反向k最近邻的查询方案。     

面向移动对象的高效预测范围聚集查询方法

预测范围聚集查询是移动对象数据库中重要的查询类型之一.提出了一种PRA树高效预测范围聚集查询索引,对速度域进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶中,针对每个速度桶,提出了一种聚集TPR树索引,通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价.PRA树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性.提出了一种增强预测范围聚集查询EPRA算法,采用更精确的剪枝搜索准则,减少了查询所需要访问的节点代价.实验结果与分析表明,基于PRA树索引的EPRA查询算法具有良好的查询性能,优于通用的TPR*树索引.     

Hypothetical Temporal Reasoning in Databases

In this paper we integrate a history–encoding based methodology for checking dynamic database integrity constraints into a situation-calculus based specification of relational database updates. By doing this, we are able to: (1) Answer queries about a whole hypothetical evolution of a database, without having to update the entire database and keep all the information associated to the generated states, (2) State and prove dynamic integrity constraints as static integrity constraints, (3). Transform history dependent preconditions for updates into local preconditions.The methodology presented here is based on the introduction of operators of predicate past temporal logic as macros into the specifications, written in the situation calculus, of the dynamics of a database. Temporal subformulas of a query are treated as auxiliary views with the corresponding specification of their dynamics. An implementation of hypothetical temporal query answering is presented.     

Database Repairs and Analytic Tableaux

In this article, we characterize in terms of analytic tableaux the repairs of inconsistent relational databases, that is databases that do not satisfy a given set of integrity constraints. For this purpose we provide closing and opening criteria for branches in tableaux that are built for database instances and their integrity constraints. We use the tableaux based characterization as a basis for consistent query answering, that is for retrieving from the database answers to queries that are consistent with respect to the integrity constraints.     

结合哈希过滤的一种改进多连接查询优化算法

多连接查询优化是提高数据库性能的关键问题之一。Chiang Lee提出了一种启发式多连接查询优化算法MVP，分析发现该算法并没有考虑减小执行计划的计算代价。该文结合哈希过滤的特点提出一种改进的多连接查询优化算法，与MVP算法相比该算法降低了执行计划的计算代从，从而使查询响应时间更短。