Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Yangjun Chen (University of Winnipeg, Canada)

Copyright: © 2009
|Pages: 12

DOI: 10.4018/978-1-60566-026-4.ch267

Chapter Preview

TopA composite object can be generally represented as a directed graph (digraph for short). For example, in a CAD database, a composite object corresponds to a complex design, which is composed of several subdesigns. Often, subdesigns are shared by more than one higher-level design, and a set of design hierarchies thus forms a directed acyclic graph (DAG). As another example, the citation index of scientific literature, recording reference relationships between authors, constructs a directed cyclic graph. As a third example, we consider the traditional organization of a company, with a variable number of manager-subordinate levels, which can be represented as a tree hierarchy.

In a relational system, composite objects must be fragmented across many relations, requiring joins to gather all the parts. A typical approach to improving join efficiency is to equip relations with hidden pointer fields for coupling the tuples to be joined. The so-called *join index* is another auxiliary access path to mitigate this difficulty. Also, several advanced join algorithms have been suggested, based on hashing and a large main memory. In addition, a different kind of attempts to attain a compromise solution is to extend relational databases with new features, such as *clustering* of composite objects, by which the concatenated foreign keys of ancestor paths are stored in a primary key. Another extension to relational system is *nested relations* (or NF^{2} relations). Although it can be used to represent composite objects without sacrificing the relational theory, it suffers from the problem that subrelations cannot be shared. Moreover, recursive relationships cannot be represented by simple nesting because the depth is not fixed. Finally, *deductive database*s and *object-relational databases* can be considered as two quite different extensions to handle this problem (Chen, 2003; Ramakrishnan & Ullman, 1995).

In the past decade, another kind of research has been done to avoid *join* operation based on *graph encoding.* In this article, we provide an overview on most important techniques in this area and discuss a new encoding approach to pack “ancestor paths” in a relational environment (Chen, 2004; Chen & Cooke, 2006). It needs only O(*e*⋅*b*) time and O(*n*⋅*b*) space, where *b* is the number of the leaf nodes of the graph’s branching. This computational complexity is better than any existing method for this problem, including the graph-based algorithms (Bender, Farach-Colton, Pemmasani, Skiena, & Sumazin, 2004; Schmitz, 1983), the graph encoding (Abdeddaim, 1997; Bommel & Beck, 2000; Zibin & Gil, 2001), and the matrix-based algorithms (La Poutre & Leeuwen, 1988).

Cyclic Graph: A cyclic graph is a directed graph that contains at least one cycle.

Tree: A tree is a graph with a root, in which the indegree of each node is equal to 1.

Topological Order: A sequence S of nodes of a DAG G = ( V , E ): v 1 ,…, v n such that ( v i , v j ) ? E implies that v j appears before v i in S .

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved