An efficient bill-of-materials algorithm
Permanent lenke
https://hdl.handle.net/10037/368Dato
1997-04Type
Research reportForskningsrapport
Sammendrag
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.
Forlag
Universitetet i TromsøUniversity of Tromsø
Serie
Tekniske rapporter / Institutt for informatikk 31(1997)Metadata
Vis full innførselSamlinger
Følgende lisensfil er knyttet til denne innførselen: