An Explication of "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" by Yangjun Chen

Date
2008
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Haverford users only
Tripod URL
Identifier
Abstract
In this paper, we discuss the algorithm for computing the transitive closure of a directed, acyclic graph of bounded degree given in Yangjun Chen’s paper, "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" [2]. We point out several errors, one in the correctness of the algorithm and one in the complexity, and modify the algorithm slightly to repair the former. (The error in complexity does not seem to be as easily fixable.) We then prove the correctness of the altered algorithm.
Description
Citation
Collections