Association mining techniques search for groups of frequently co-occurring items in a market-basket type of data and turn these groups into business-oriented rules. Previous research has focused predominantly on how to obtain exhaustive lists of such associations. However, users often prefer a quick response to targeted queries. For instance, they may want to learn about the buying habits of customers that frequently purchase cereals and fruits. To expedite the processing of such queries, we propose an approach that converts the market-basket database into an itemset tree. Experiments indicate that the targeted queries are answered in a time that is roughly linear in the number of market baskets, N. Also, the construction of the itemset tree has O(N) space and time requirements. Some useful theoretical properties are proven.

The problem of choosing a storage model for a nested relation (i.e., a relation containing relations) is considered. A technique is introduced that uses the workload information of the database system under consideration to obtain a better storage model (i.e., one with a lower query cost) for a given nested relation. The nested relation scheme is first represented as a tree called the scheme tree. By using the workload information and by performing a series of merges in the nodes of the scheme tree, a near-optimum scheme tree is produced, and file organization types are assigned to each node (file) in the scheme tree. The authors' methodology is applied by using a specific nested relational algebra and three file organization types, namely, sequential, heap, and dense index files. The proposed methodology locates the optimum storage model and the optimum file organization techniques for the external and internal relations of the nested relations tested.>