Broadcast program generation for unordered queries with data replication

We study in this paper the problem of broadcasting dependent data for unordered queries. However, most prior studies on dependent data broadcasting are limited to the premise of no data replication. Different from other prior studies, we investigate the effect of data replication in this paper. Specifically, we first derive several theoretical properties for the average access time by analyzing the model of dependent data broadcasting. On the basis of the theoretical results, we develop a genetic algorithm to generate broadcast programs with replication. In order to compare the performance of the proposed algorithm and the prior studies, several experiments are conducted. Our experimental results show that with the analytical results derived, the theoretical results derived are able to guide the search of the genetic algorithm very effectively, and lead to solution broadcast programs of higher quality than those of the prior studies.