An efficient bill-of-materials algorithm
Abstract
A large class of linear recursive queries compute the bill-of-materials
of database relations.This paper presents a novel algorithm that computes the bill-of-materials of its argument's (database) relation. The algorithm uses a special join operation that accumulates the cost of composite parts, without constructing the transitive closure of the argument relation, thus saving time and space.
We argue that this algorithm outperforms existent algorithms in the order of the diameter of the graph represented in the argument relation. This is made possible by exploiting knowledge of the level each tuple of the argument relation belongs to.
Moreover, this algorithm in contrast to transitive closure based processing, produces data at a very early stage of the processing which renders it suitable for pipelined distributed data processing.
Publisher
Universitetet i TromsøUniversity of Tromsø
Series
Tekniske rapporter / Institutt for informatikk 31(1997)Metadata
Show full item recordCollections
The following license file are associated with this item: