Efficient bill-of-materials algorithms

Abstract

It has been shown that every linearly recursive database query can be expressed as a transitive closure possibly preceded and followed by relational algebraic operations. A large class of such queries computes the bill-of-materials of database relations. This paper presents efficient sequential and distributed algorithms that compute the bill-of-materials of a database relation. These algorithms use 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. Moreover, the distributed algorithms are very efficient in terms of their communication complexity. The number of tuples exchanged is neither dependent on the size of the argument relation nor on the size of its transitive closure. That number is simply equal to the number of different parts in the argument relation. For the distributed setting we develop both a synchronous and an asynchronous algorithms. We verify their correctness and analyze their behavior, time complexity, and communication cost. Based on that analysis, some improvements of both algorithms are suggested. We conclude that some partially synchronous algorithms seem to be superior to both of them.