triceratops

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

TriCollege Digital Repository

Title: An Explication of "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" by Yangjun Chen
Author: Miller, Anne
Department: Haverford College. Dept. of Computer Science
Type: Thesis (B.A.)
Issue Date: 2008
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.
Subject: Chen, Yangjun. New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases
Subject: Computer algorithms
Terms of Use: http://creativecommons.org/licenses/by-nc/3.0/us/
Permanent URL: http://hdl.handle.net/10066/3754

Files in this item

Files Description Size Format
Haverford_departmental_permission.pdf **Archive Staff Only** 30.60Kb PDF
2008MillerA.pdf Thesis (Haverford users only) 184.4Kb PDF

Citation

Miller, Anne. "An Explication of "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" by Yangjun Chen". 2008. Available electronically from http://hdl.handle.net/10066/3754.

This item appears in the following Collection(s)

http://creativecommons.org/licenses/by-nc/3.0/us/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc/3.0/us/

Search


Advanced Search

Browse

My Account