Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

Graph Encoding and Transitive Closure Representation

Graph Encoding and Transitive Closure Representation
View Sample PDF
Author(s): Yangjun Chen (University of Winnipeg, Canada)
Copyright: 2009
Pages: 12
Source title: Encyclopedia of Information Science and Technology, Second Edition
Source Author(s)/Editor(s): Mehdi Khosrow-Pour, D.B.A. (Information Resources Management Association, USA)
DOI: 10.4018/978-1-60566-026-4.ch267


View Graph Encoding and Transitive Closure Representation on the publisher's website for pricing and purchasing information.


Composite objects represented as directed graphs are an important data structure that require efficient support Web and document databases (Abiteboul, Cluet, Christophides, Milo, Moerkotte, & Simon, 1997; Chen & Aberer, 1998, 1999; Mendelzon, Mihaila, & Milo, 1997; Zhang, Naughton, Dewitt, Luo, & Lohman, 2001), CAD/ CAM, CASE, office systems, and software management. It is cumbersome to handle such objects in relational database systems when they involve ancestor-descendant relations (or say, reachability relations). In this article, we present a new graph encoding based on a tree labeling method and the concept of branchings that are used in the graph theory for finding the shortest connection networks. A branching is a subgraph of a given digraph that is in fact a forest, but covers all the nodes of the graph. Concretely, for a DAG G (directed acyclic graph) of n nodes, the space needed for storing its transitive closure can be reduced to O(b·n), where b is the number of the leaf nodes of G’s branching. Such a compression is, however, at the expense of querying time. Theoretically, it takes O(logb) time to check whether a node is reachable from another. The method can also be extended to digraphs containing cycles.

Related Content

Christine Kosmopoulos. © 2022. 22 pages.
Melkamu Beyene, Solomon Mekonnen Tekle, Daniel Gelaw Alemneh. © 2022. 21 pages.
Rajkumari Sofia Devi, Ch. Ibohal Singh. © 2022. 21 pages.
Ida Fajar Priyanto. © 2022. 16 pages.
Murtala Ismail Adakawa. © 2022. 27 pages.
Shimelis Getu Assefa. © 2022. 17 pages.
Angela Y. Ford, Daniel Gelaw Alemneh. © 2022. 22 pages.
Body Bottom