Recently, the efficient processing of multiple continuous queries (MCQ) is being importantly discussed in the research of data streams. Generally, MCQ on data streams have their own window sizes and periodic execution intervals unlike ad-hoc queries used in stored data set. Thus, there can be overlapped windows and a repeated execution cycle among MCQ. Also, according to the size of overlapped windows among MCQ with common sub-expressions (join-fragments), their intermediate results can be partially or wholly shared. When MCQ build execution plans, they need to determine whether they reuse the whole or partial intermediate results or not on every execution.
Our problem is to find a global plan for MCQ. Since it is NP-hard, we discuss a novel greedy-style approach to solve it. Our idea is first to decide an execution cycle among MCQ and find the maximal set(s) of related execution points. Then, we construct our global plan for MCQ by sharing common join-fragments with the high benefit in each set. We first suggest that the best plan of the same CQ may be different due to the size of overlapped windows. We also propose the method to consider reusing not only the whole but partial intermediate results unlike previous work. Finally, we show the validation of our idea by experiment.
최근에, 데이터 스트림 연구 분야에서 다중 연속 질의의 효율적인 처리 기법이 중요하게 논의되어 왔다. 일반적으로, 데이터 스트림에 대한 다중 연속 질의들은 저장된 데이터 집합에서 사용된 애드-혹 질의와는 달리 그들 자신만의 윈도우 크기와 주기적인 실행 간격을 갖는다. 그래서, 다중 연속 질의들 사이에 중첩된 윈도우와 반복된 실행 사이클을 가질 수 있게 된다. 또한, 공통의 하위표현(조인부분)을 갖는 다중 연속 질의들의 중첩된 윈도우 크기에 따라, 그것들의 중간 결과가 부분적으로 혹은 전체적으로 공유될 수 있다. 다중 연속 질의들은 이러한 전체 또는 부분의 중간 결과를 재사용할지 말지를 결정하여 플랜을 세울 필요가 있다.
우리의 문제는 다중 연속 질의들을 위한 전체 플랜을 찾는 것이다. 그 문제가 NP-hard 이므로, 우리는 전체 플랜을 찾기 위한 탐욕 스타일의 기법을 제안한다. 우리의 아이디어는 먼저 다중 연속 질의들 사이의 전체 실행 주기를 결정하고 관련된 실행 시점들의 최대 집합(SRP)를 찾는 것이다. 다음 각 SRP에서 가장 높은 이익을 갖는 공통의 조인 부분들을 공유함으로써 우리의 전체 플랜을 구성한다.
우리는 중첩된 윈도우의 크기에 따라서 동일한 연속 질의라 하더라도 그것의 최상 실행 플랜이 바뀔 수 있다는 점을 최초로 제시한다. 기존 연구와는 달리 전체의 중간 결과 뿐만 아니라 부분의 중간 결과까지도 재사용 할 지 말지를 고려하여 플랜을 세우는 기법을 제안한다. 마지막으로, 실험으로 우리의 아이디어에 대한 유효성을 보인다.
