A New Way to Speed Up Recursion in Relational Databases

View Free PDF

Author(s): Yangjun Chen (University of Winnipeg, Canada)
Copyright: 2002
Pages: 5
Source title: Issues & Trends of Information Technology Management in Contemporary Organizations
Source Editor(s): Mehdi Khosrow-Pour, D.B.A. (Information Resources Management Association, USA)
DOI: 10.4018/978-1-930708-39-6.ch120
ISBN13: 9781930708396
EISBN13: 9781466641358

Keywords: Information Science Reference / IT Research & Theory / IT Research and Theory / Library & Information Science

Abstract

Composite object represented as a directed graph is an important data structure which requires efficient support in CAD/CAM, CASE, office systems, software management, web databases and document databases. It is cumbersome to handle such an object in relational database systems when it involves recursion relationships. In this paper, we present a new encoding method to support the efficient computation of recursion. In addition, we devise a linear time algorithm to identify the sequence of spanning trees (forests) w.r.t. a directed acyclic graph (DAG), which covers all the edges of the graph. Together with the new encoding method, this algorithm enable us to compute recursion w.r.t. a DAG in time O(e), where e represent the number of the edges of the DAG. More importantly, this method is especially suitable for a relational environment.

IRMA Offers Over 2,500 Full Text Open Access Research Papers for Free Download Click to Start Searching Free IRM Research!

IRMA Sponsors

Encyclopedia of Information Science and Technology, Fourth Edition