객체지향 데이타베이스에서의 비용기반 버퍼 교체 알고리즘 = A Cost-Based Buffer Replacement Algorithm in Object-Oriented Database Systems

국문 초록 (Abstract)

많은 객체지향 데이타베이스 시스템들은 객체에 대한 빠른 액세스를 제공하기 위하여 객체버퍼를 관리한다. 기존의 고정 길이의 페이지를 단위로 하는 교체 알고리즘들은 고정 크기의 페이지의 교체 비용이 일정하므로 버퍼에서 발생하는 비용이 단순히 버퍼 폴트 횟수에 비례한다고 가정하고 있다. 그러나, 객체 버퍼에서는 객체들의 크기와 교체 비용이 객체마다 다르므로 이러한 가정은 더이상 성립하지 않는다.
본 논문에서는 객체버퍼를 위한 비용기반 교체 알고리즘을 제안한다. 제안된 알고리즘은 객체들의 크기와 교체 비용을 포함하도록 기존의 페이지 기반 모델을 확장한 비용 모델을 기반으로 단위 시간 및 단위 공간당 비용이 최소가 되도록 하는 객체를 교체한다. 성능 평가 결과에 따르면 이 알고리즘은 기존의 LRU-2에 비해 거의 항상 우수하며 경우에 따라 2배 이상의 성능을 보인다. 비용기반 알고리즘은 기존의 방법들이 적용된 어떤 응용에도 쉽게 적용될 수 있으며, 특히 교체 비용이 일정하지 않은 객체지향 데이타베이스 시스템에서 효율적으로 활용될 수 있다.

다국어 초록 (Multilingual Abstract)

Many object-oriented database systems manage object buffers to provide fast access to objects. Traditional buffer replacement algorithms based on fixed-length pages simply assume that the cost incurred by operating a buffer is proportional to the number of buffer faults. However, this assumption no longer holds in an object buffer where objects are of variable-length and the cost of replacing an object varies for each object.
In this paper, we propose a cost-based replacement algorithm for object buffers. The proposed algorithm replaces the objects that have minimum costs per unit time and unit space. The cost model extends the previous page-based one to include the replacement costs and the sizes of objects. The performance tests show that the proposed algorithm is almost always superior to the LRU-2 algorithm and in some cases is more than twice as fast. The idea of cost-based replacement can be applied to any buffer management architectures that adopt earlier algorithms. It is especially useful in object-oriented database systems where there is significant variation in replacement costs.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 기존의 교체 알고리즘들
• 3. 비용기반 객체 버퍼 교체 알고리즘
• 4. 성능평가
• 5. 결론 및 향후 연구
• 참고문헌
• 부록
• 저자소개