标签约束图上的k步可达性查询

标签约束图上的k步可达性查询问题,回答了在一个标签约束图上两点之间是否存在一条长度不大于k的路径并且这条路径上的标签都在用户给定的标签集中的问题。标签约束图上的k步可达性查询问题在现实中有着广泛的应用,然而现有算法无法直接回答这个问题。因此,首先提出LK2H算法。LK2H算法主要包括构建索引和查询两个步骤。第一步是给图上的所有顶点构建一组包含k和标签信息的2-Hop索引,第二步是基于构建好的索引进行查询。在查询时,为了尽可能地为用户返回更多的信息,LK2H算法优化了一类不可达查询的返回结果：当用户无法明确所有的标签类型,不能给出完整的标签约束,进而导致查询结果为不可达时,将完整的标签集返回给用户。其次,提出优化算法LK2H+。LK2H+算法通过构建部分顶点的2-Hop索引进一步缩减索引大小和索引的构建时间,并基于构建好的索引进行查询。查询时,需要对顶点按照是否构建了索引进行分类讨论。最后,基于15个真实数据集进行测试。实验结果表明,LK2H算法和LK2H+算法都可以高效地解决标签约束图上的k步可达性查询问题。     

低冗余计算的可达性查询保持图压缩策略

针对可达性查询保持图压缩（QPGC）算法存在冗余计算的问题,提出了一种高性能压缩策略。在求解顶点的祖先后代集阶段,针对普通图数据,提出一种基于拓扑排序的求解算法TSB,首先将图数据顶点拓扑排序,然后沿拓扑序列顺序（逆序）求解顶点的祖先（后代）集,避免了求解顺序不明确导致的冗余计算;针对最长路径较短的图数据,提出一种基于图聚合运算的求解算法AGGB,可在确定次数的聚合运算内完成顶点的祖先和后代集的求解。在求解可达性等价类阶段,提出一种分段统计剪枝算法PSP,先对祖先后代集分段统计,再比较统计值以实现粗匹配,剪除了部分不必要的精细匹配。实验结果表明,与QPGC算法相比：在祖先后代集求解阶段,TSB和AGGB在不同数据集上的性能平均提升94.22%和90.00%;在求解可达性等价类阶段,PSP算法在大部分数据集上性能提升超过70%;随着数据集的增大,TSB和AGGB配合PSP算法,性能提升了近28倍。理论分析和模拟实验表明,该策略与QPGC算法相比冗余计算更少、压缩速度更快。     

传递闭包算法的探讨

传递闭包是一种重要的关系运算,它在计算机系统中有着广泛的应用。本文探讨了传递闭包的计算。分析warshall算法在有向图中的意义．并给出了一个简便的有向图传递闭包算法。     

RIAIL:大规模图上的可达性查询索引方法

图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.     

一类递归查询问题的快速求解算法

提出一个求解一类扩充递归Ｄａｔａｌｏｇ逻辑程序的算法,论证其正确性,并讨论了算法的复杂性。该算法结合了自底向上和自顶向下的逻辑程序求解算法的优点,但比魔集算法简单,易于实现。利用宁可以解决工程数据管理中常遇到的产品零部件装配关系的递归查询问题。     

在关系DBMS上扩充传递闭包功能的方法和实现技术

现有的关系ＤＢＭＳ一般还不支持传递闭包计算功能。为了扩充这个重要功能，作者在ＯＲＡＣＬＥＤＢＭＳ上增加了一个传递闭包处理层ＳＥＴＣＳ。ＳＥＴＣＳ提供了一个ＳＱＬ的扩充版本ＳＱＬ。ＳＱＬ比ＳＱＬ增加了传递闭包的定义和查询语句。ＳＱＬ中有关传递闭包的语句由预处理接口处理，传递闭包用半质朴算法计算。为了应用的需要，除计算传递闭包外，还提供传递闭包的深度和路径等参数。作为应用的例子，ＳＥＴＣＳ已试用于民航     

求模糊相似矩阵的传递闭包的简捷算法

模糊相似矩阵传递闭包的计算在模糊聚类及语法分析等领域应用广泛.从最大树出发论述并实现了一种求模糊相似矩阵传递闭包的简捷算法.与经典的求模糊相似矩阵传递闭包的算法—平方法比较,该算法简捷,运算量小。     

在RDBMS上扩充传递闭包功能的方法和算法

目前的ＲＤＢＭＳ一般不支持传递闭包计算功能。为扩充此功能，作者提出了在原ＲＤＢＭＳ上增加传递闭包处理层ＳＥＴＣＳ，以及扩充传递闭包定义与查询语句的ＳＱＬ＊。该方案已在ＯＲＡＣＬＥ上实现并投入应用。     

关于传递闭包和函数依赖完备公理系统存在的问题研究

数据依赖在数据库设计中起着十分重要的作用，自Ｃｏｄｄ提出函数依赖，Ｆａｇｉｎ引入多值依赖后，近几年来人们又根据设计中的需要引入多种新的依赖，如在工程数据库设计中所引进的传递闭包依赖等，对这些依赖一般是按其是否具有完备的公理系统而划分为两大类，因为完备性公理系统往往具有有效的判定算法为先决条件。本对ＣＤＳ和ＦＤＳ的ｋ元完备公理系统存在问题进行了研究，证明了ＣＤＳ和ＦＤＳ不具有共同的Ｋ元完备公理系统     

基于求传递闭包的Warshall算法的改进

围绕传递闭包分析比较了著名的Warshall算法,给出了一个三角形算法。当关系矩阵是稀疏矩阵时,该算法比Warshall快。     

Exponential space complexity for OBDD-based reachability analysis

Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Nevertheless, many basic graph problems are known to be PSPACE-hard if their input graphs are represented by OBDDs. Computing the set of nodes that are reachable from some source s∈V in a digraph G=(V,E) is an important problem in computer-aided design, hardware verification, and model checking. Until now only exponential lower bounds on the space complexity of a restricted class of OBDD-based algorithms for the reachability problem have been known. Here, the result is extended by presenting an exponential lower bound for the general reachability problem. As a by-product a general exponential lower bound is obtained for the computation of OBDDs representing all connected node pairs in a graph, the transitive closure.     

Efficient processing of label-constraint reachability queries in large graphs

In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries. Specifically, given a label set S and two vertices u₁ and u₂ in a large directed graph G, we check the existence of a directed path from u₁ to u₂, where edge labels along the path are a subset of S. We propose the path-label transitive closure method to answer LCR queries. Specifically, we t4ransform an edge-labeled directed graph into an augmented DAG by replacing the maximal strongly connected components as bipartite graphs. We also propose a Dijkstra-like algorithm to compute path-label transitive closure by re-defining the “distance” of a path. Comparing with the existing solutions, we prove that our method is optimal in terms of the search space. Furthermore, we propose a simple yet effective partition-based framework (local path-label transitive closure+online traversal) to answer LCR queries in large graphs. We prove that finding the optimal graph partition to minimize query processing cost is a NP-hard problem. Therefore, we propose a sampling-based solution to find the sub-optimal partition. Moreover, we address the index maintenance issues to answer LCR queries over the dynamic graphs. Extensive experiments confirm the superiority of our method.     

Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n ²) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Ω(n ²) entries of this matrix, no better bounds are possible for this class of algorithms. This work has been partially supported by the Sixth Framework Programme of the EU under contract number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”), and number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”), and by the Italian Ministry of University and Research (Project “ALGO-NEXT: Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). Portions of this paper have been presented at the 41st Annual Symp. on Foundations of Computer Science, 2000.     

一种在网格中信任评估机制

在一个面向服务的网格结构中,服务之间的信任关系很难建立,这是因为一方面要支持单次登录机制(SSO);另一方面还要支持大量的动态临时服务信任的交互,源端和目的端不可能提前建立信任关系,这样源端无法提前评估对目的的信任,因此应该研究评估S对T信任的解决方法。本文基于委托图的传递闭包特点来评估参与者的信任。     

Efficient maintenance of explicit transitive closures with set-oriented update propagation and parallel processing

Explicitly storing the transitive closure of a relation appears to be a solution providing fast access to recursivelu defined data. However, two problems are to be solved: (i) update propagations have to be efficiently processed and (ii) efficient access and limited storage space have to be reconciled. This paper focuses on the minimization of the cost of the propagation of the updates from the base relation to the deduced one. Only a part of the transitive closure relation is influenced by the base modification and has to be recomputed. Algorithms for instance-oriented propagations of insertion and deletion are proposed. Then, we take into account a set of deleted and/or inserted tuples in a single manipulation. The proposed method maintains an arbitrary set-oriented update in no more than 2 passes over the transitive closure. The execution times are decreased by the intensive use of parallelism; the explicit transitive closure is divided horizontally into several fragments, clustered on a set of disks, and then, processed by several processors. A shared-nothing implementation is investigated.     

Algorithms for transitive closure

Let σ′(n) denote the number of all strongly connected graphs on the n-element set. We prove that σ′(n)?2ⁿ²·(1−n(n−1)/2ⁿ⁻¹). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n²), under the assumption of uniform distribution of input graphs. Furthermore, we present a new algorithm constructing the transitive closure of an acyclic graph.     

A logic of reachable patterns in linked data-structures

We define a new decidable logic for expressing and checking invariants of programs that manipulate dynamically-allocated objects via pointers and destructive pointer updates. The main feature of this logic is the ability to limit the neighborhood of a node that is reachable via a regular expression from a designated node. The logic is closed under boolean operations (entailment, negation) and has a finite model property. The key technical result is the proof of decidability.We show how to express preconditions, postconditions, and loop invariants for some interesting programs. It is also possible to express properties such as disjointness of data-structures, and low-level heap mutations. Moreover, our logic can express properties of arbitrary data-structures and of an arbitrary number of pointer fields. The latter provides a way to naturally specify postconditions that relate the fields on the entry of a procedure to the field on the exit of a procedure. Therefore, it is possible to use the logic to automatically prove partial correctness of programs performing low-level heap mutations.     

Incremental recomputation in local languages

We study the problem of maintaining recursively defined views, such as the transitive closure of a relation, in traditional relational languages that do not have recursion mechanisms. The main results of this paper are negative ones: we show that a certain property of query languages implies impossibility of such incremental maintenance. The property we use is locality of queries, which is known to hold for relational calculus and various extensions, including those with grouping and aggregate constructs (essentially, plain SQL).