An efficient bill-of-materials algorithm
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.
PublisherUniversitetet i Tromsø
University of Tromsø
SeriesTekniske rapporter / Institutt for informatikk 31(1997)
The following license file are associated with this item: