데이터 스트림 윈도우 질의를 위한 다중의 연속 MJoin 연산자 공유 처리 : Sharing Multiple Continuous MJoins for Window Queries over Data Streams
- 발행기관 서강대학교 대학원
- 지도교수 박석
- 발행년도 2007
- 학위수여년월 200702
- 학위명 석사
- 학과 및 전공 컴퓨터학
- 식별자(기타) 000000103760
- 본문언어 한국어
초록/요약
인터넷 서비스, 네트워크 인프라의 확장은 데이터 흐름의 변화를 가져다 주었다. 즉, 기존의 정적인 데이터에서 빠르고 무한하게 발생하는 데이터로의 변화가 진행되고 있는데, 이러한 정보들은 데이터 스트림으로 정의된다. 데이터 스트림 관리 시스템에서 조인 연산자는 질의가 내포하는 여러 연산자들 가운데 상대적인 계산 비용이 높은 연산자로, 센서 네트워크와 같이 한정적 정보들이 개별적으로 입력되는 환경에서는 필연적으로 요구된다. 하나의 시스템에는 여러 질의가 등록되어 처리되는데, 이러한 질의는 조인 연산자를 내포할 수 있다. 이미 오랜 기간 데이터베이스 시스템 연구분야에서 다중 조인 질의에 대한 여러 최적화 기법이 제시되었으나 데이터 스트림 연구 패러다임에서는 질의와 데이터에 대한 기본적인 가정이 유효하지 않아 그대로 적용하기에는 무리가 있다. 데이터 스트림은 잠재적으로 무한한 크기를 가지므로 조인 연산자는 슬라이딩 윈도우 제약사항을 가져 불필요한 2차 보조기억장치의 I/O를 방지하는 것이 합리적이다. 또한, 보다 종합적인 결과를 얻기 위해서는 조인 연산자가 여러 입력을 취할 수 있어야 한다. 이를 가능하게 하는 것이 바로 슬라이딩 윈도우를 가지는 MJoin 연산자이다. 본 논문에서는 이러한 복수개의 MJoin 연산자가 시스템에 등록되어 있는 데이터 스트림 환경을 가정하며, 슬라이딩 윈도우 제약사항과 MJoin의 특성을 반영하여 전역적으로 공유된 질의 실행 계획 수립 및 처리에 관한 문제를 다룬다. 이러한 다중 MJoin에 대한 전역 공유 질의 실행 계획 수립 문제가 NP-Hard임을 증명하고, 근사화 접근 방법을 제안한다. 또한 전역적으로 공유된 질의 실행 계획을 올바르게 수행할 수 있는 처리 기법을 제안한다. 마지막으로 본 논문에서는 제안하는 기법과 여러 MJoin을 독립적으로 수행하는 경우에 대해 처리 성능과 저장 공간 사용량 측정기준에서 비교한 결과를 제공한다. 이러한 연구의 노력은 데이터 스트림 환경에서 효율적인 다중 질의 최적화 및 처리기법의 기초 연구로 활용될 수 있다.
more초록/요약
The extension of internet services and network infrastructures impacts on flow of data. The data stream is the information which is generated very fast and has potentially infinite size unlike traditional static data. In Data Stream Management System, join queries, one of the queries having heavy cost, are used for an environment such as sensor-network where plural short information generates. When multiple queries are registered in a system, theses queries may involve join queries. For many years, optimization techniques of multiple join queries are studied in database literature. Unfortunately, theses can''t be applied to data stream environment because the old assumption for queries and data is not valid any more in data stream paradigm. It''s reasonable that each join operator has sliding-window constraint for preventing DISK I/O because the data stream represents the infinite size of data. Besides, the join operators should be able to take multiple inputs for overall results. To this end, we focus on the MJoin operator with sliding-windows. In this thesis, we focus on the data stream environment where multiple MJoin operators are registered. Then, we study issues of building and processing a globally shared query execution plan considering sliding-windows and characteristics of MJoin operator. We also show that the problem of optimally establishing global shared query plan for multiple MJoins is NP-Hard, and propose an approximation algorithm. And we propose a technique processing precisely the global shared plan. Finally, we compare proposed techniques with existing MJoin under various experiments. Our study can be utilized as fundamental study of some techniques of processing shared plan over data stream for efficient multi-query optimizations.
more