Abstract: Data warehouses store a large amount of summarized data in form of materialized views defined over some source relations to support querying and decision making When data sources change, these views need to be updated in time These impose a significant overhead on the warehouse, so it is a very important problem to incrementally maintain materialized views efficiently A BinPartition algorithm is proposed to construct an optimal delta propagation tree according to which the cost of view maintenance is minimal The correctness and time complexity of the algorithm are also given