Temporal databases introduce the concept of time into underlying data, and provide built-in facilities that allow users to store and retrieve time-varying data. The aggregation in temporal databases, that is, temporal aggregation is an extension of conventional aggregation on the domain and range of aggregates to include time concept. Temporal aggregation is important for various applications, but is very expensive. In this paper, we propose a new tree structure for temporal aggregation, called PA-tree, and aggregate processing method based on the PA-tree. We show that the time complexity of the proposed method is better than those of the existing methods. The time complexity of the proposed method is shown to be indeed the lower bound of the problem. We perform comparative experiments and show the performance advantage of our proposed method in practice.