Title page for ETD etd-0527104-223456

Document Type thesis

Author Name Silva, Asima

URN etd-0527104-223456

Title Multiple Continuous Query Processing with Relative Window Predicates "Juggler"

Degree MS

Department Computer Science

Advisors
Professor Elke Rundensteiner, Advisor
Professor George T. Heineman, Advisor
Professor David Finkel, Reader

Keywords
reordering predicates
multi-join operator
sliding windows
window predicates
join algorithm
continuous queries

Date of Presentation/Defense 2004-05-03

Availability unrestricted

Abstract
Efficient querying over streaming data is a critical technology which
requires the ability to handle numerous and possibly similar queries
in real time dynamic environments such as the stock market and medical
devices. Existing DBMS technology is not well suited for this domain
since it was developed for static historical data. Queries over streams often
contain relative window predicates such as in the
query: ``Heart rate decreased to fifty-two beats per second within four
seconds after the patient's temperature started rising." Relative
window predicates are a specific type of join between streams that is
based on the tuple's timestamp.

In our operator,
called Juggler, predicates are classified into three types: attribute,
join, and window. Attribute predicates are stream values compared to a constant. Join predicates are stream values
compared to another stream's values. Window predicates are join predicates where the streams' timestamp values are compared.
Juggler's composite operator incorporates the
processing of similar though not identical, query
functionalities as one complex computation process. This execution
strategy handles multi-way joins for multiple selection and join
predicates. It adaptively orders the execution of predicates by their
selectivity to efficiently process multiple continuous queries based
on stream characteristics. In Juggler, all similar predicates are grouped into lists. These indices are represented
by a collection of bits. Every tuple contains the bit structure representation of the predicate lists which encodes tuple predicate evaluation history.
Every query also contains a similar bit structure to encode the predicate's relationship to the registered queries.
The tuple's and query's bit structures are compared to assess if the tuple has satisfied a query.

Juggler is designed and implemented in Java.
Experiments were conducted to verify correctness and to assess the performance of Juggler's three features. Its adaptivity of reordering the evaluation of predicate
types performed as well as the most selective predicate ordering.
Its ability to exploit similar predicates in multiple queries showed reduction in number of comparisons.
Its effectiveness when multiple queries are combined in a single
Juggler operator indicated potential performance improvements after optimization of Juggler's data structures.

Files
asilva.pdf

Browse by Author | Browse by Department | Search all available ETDs

Questions? Email etd-questions@wpi.edu
Maintained by webmaster@wpi.edu

Document Type	thesis
Author Name	Silva, Asima
URN	etd-0527104-223456
Title	Multiple Continuous Query Processing with Relative Window Predicates "Juggler"
Degree	MS
Department	Computer Science
Advisors	Professor Elke Rundensteiner, Advisor Professor George T. Heineman, Advisor Professor David Finkel, Reader
Keywords	reordering predicates multi-join operator sliding windows window predicates join algorithm continuous queries
Date of Presentation/Defense	2004-05-03
Availability	unrestricted
Abstract Efficient querying over streaming data is a critical technology which requires the ability to handle numerous and possibly similar queries in real time dynamic environments such as the stock market and medical devices. Existing DBMS technology is not well suited for this domain since it was developed for static historical data. Queries over streams often contain relative window predicates such as in the query: ``Heart rate decreased to fifty-two beats per second within four seconds after the patient's temperature started rising." Relative window predicates are a specific type of join between streams that is based on the tuple's timestamp. In our operator, called Juggler, predicates are classified into three types: attribute, join, and window. Attribute predicates are stream values compared to a constant. Join predicates are stream values compared to another stream's values. Window predicates are join predicates where the streams' timestamp values are compared. Juggler's composite operator incorporates the processing of similar though not identical, query functionalities as one complex computation process. This execution strategy handles multi-way joins for multiple selection and join predicates. It adaptively orders the execution of predicates by their selectivity to efficiently process multiple continuous queries based on stream characteristics. In Juggler, all similar predicates are grouped into lists. These indices are represented by a collection of bits. Every tuple contains the bit structure representation of the predicate lists which encodes tuple predicate evaluation history. Every query also contains a similar bit structure to encode the predicate's relationship to the registered queries. The tuple's and query's bit structures are compared to assess if the tuple has satisfied a query. Juggler is designed and implemented in Java. Experiments were conducted to verify correctness and to assess the performance of Juggler's three features. Its adaptivity of reordering the evaluation of predicate types performed as well as the most selective predicate ordering. Its ability to exploit similar predicates in multiple queries showed reduction in number of comparisons. Its effectiveness when multiple queries are combined in a single Juggler operator indicated potential performance improvements after optimization of Juggler's data structures.
Files	asilva.pdf