Reductive Data Cube Based on Formal Concept Analysis

A comparative examination of data cube lattice and formal concept lattice shows that both of them are based on order-structure; and furthermore, equivalent character groups based on formal concept analysis (FCA) and cover equivalence classes of cells in data cube have the same partitions for data. The theories of FCA and concept lattice are introduced into the research of data cube and aggregate concept lattice(ACL) is firstly brought forward in this paper. The ACL has the same structure with original concept lattice. It can reduce data cube in same ratio with quotient cube and contain all aggregations of cube integrally. But ACL is still complex. So another reductive structure called reductive aggregate concept lattice(RACL) is proposed, which contains only non-object concepts but not all the concepts. The RACL combined with base table is still a fully pre-computed cube and can realize the reduction of data cube in higher ratio. An efficient method of query answering in ACL and RACL is proposed at the same time. Experiments are also presented by using both the synthetic and real-world data sets. The theoretic and experimental results show that the space saving in RACL is more efficient than previous ones and query is efficient too.