온라인 벌크삽입 지원을 위한 동시성 제어 알고리즘에 대한 연구

소개

온라인 벌크삽입 지원을 위한 동시성 제어 알고리즘에 대한 연구

목차

요 약
1. 서론
2. 관련 연구
3. 벌크삽입 기법을 위한 동시성 제어 알고리즘
4. 제안하는 동시성 제어 알고리즘
5. 결론
참고문헌

본문내용

요 약
이 연구에서는 온라인 벌크삽입을 지원하기 위한 벌크삽입 동시성제어 알고리즘에 대한 연구를 수행한다. 공간 데이터베이스나 이미지 데이터베이스의 활용 예를 보면 데이터베이스가 구축된 이후에 대량의 정적인 데이터를 추가적으로 구축해야 하는 경우가 빈번한 경우가 있다. 이때 색인을 위해서 다차원 색인구조에 구축된 데이터를 반영해야 하는데 이를 하나씩 삽입하지 않고 한번에 구축된 데이터 전부를 삽입하면 훨씬 성능이 좋은 색인구조를 생성할 수 있다. 이를 벌크삽입이라하고 이를 온라인으로 처리하기 위해서는 벌크삽입이 일어나는 상황에서도 탐색연산수행을 가능하게 해야 한다. 이를 위해서는 적절한 동시성 알고리즘이 필요하고 이 연구에서는 벌크삽입을 위한 동시성 제어 알고리즘을 제안하고 설계한다.
1. 서론
벌크 삽입이란 이미 구축된 색인 구조에 대량의 데이터를 한번에 효과적으로 삽입하기 위한 방법이다. 벌크 삽입 역시 삽입 시간의 단축과 검색 성능 향상이 그 목적이다. 하지만 색인을 생성하기 위한 벌크로딩은 오프라인동안 발생하는 반면 벌크 삽입은 온라인동안 수행되어야 하므로 다른 검색 트랜잭션들이 동시에 수행될 수 있도록 하는 동시성 제어 알고리즘이 필수적으로 수반되어야 한다. 기존에 제시된 벌크삽입 알고리즘들로는 STLT(Small Tree Large Tree)와 GBI(Generalized Bulk Insertion)을 들 수 있다. STLT 방법 자체는 고도로 뒤틀린(skewed) 데이터 집합을 위한 알고리즘이다. 이 제약사항을 좀더 완화하기 위한 방법으로 GBI가 제시되었지만 이 방법 역시 기 구축된 색인구조와 벌크 삽입될 데이터와의 관계를 전혀 고려하지 않고 있어 다양한 분포의 데이터 집합에는 부적절하다. 이 연구에서는 이런 문제를 해결하는 벌크삽입 기법을 설계한다. 또한 설계한 벌크삽입 기법이 온라인을 지원할 수 있도록 적절한 동시성제어 기법을 설계한다.
벌크삽입은 온라인 상태에서 발생한다.

참고자료

· [1] Li Chen, Rupesh Choubey, Elke A. Rundensteiner, “ Bulk-Insertions info R-Trees Using the Small-Tree-Large-Tree Approach”, ACM-GIS, 1998, 161-162
· [2] Rupesh Choubey, Li Chen, Elke A. Rundensteiner, “GBI: A Generalized R-Tree Bulk-Insertion Strategy”, SSD. 1999, 91-108
· [3] V. Ng and T. Kamada, "Concurrent Accesses to R-Trees," In Proc. of Symposium on Large Spatial Databases, pages 142-161, 1993.
· [4] M. Kornacker, C. Mohan and J. M. Hellerstein, “Concurrency and Recovery in Generalized Search Trees,” In Proc. ACM SIGMOD Conf., pages 62-72, May 1997.
· [5] M Kornacker and D. Banks, "High-Concurrency Locking in R-Trees," In Proc. 21st Int`l Conference on VLDB, pages 134-145, September 1995.
· [6] C. Mohan, D. Harderle, B. Lindsay, H. Pirahesh, and P. Schwarz, "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write Ahead Logging," ACM TODS, 17(1), pages 94-162, March 1992.
· [7] C. Mohan and F. Levine, "ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging," In Proc. ACM SIGMOD Conf., pages 371-380, June 1992.
· [8] P.L. Lehmann and S.B. Yao, "Efficient Locking for Concurrent Operations on B-Trees," ACM TODS, 6(4), pages 650-670, December 1981.