CONJUNCTIVE QUERY PROCESSING WITH COMPARISONS AND UPDATES

PhD Thesis Proposal Defence


Title: "CONJUNCTIVE QUERY PROCESSING WITH COMPARISONS AND UPDATES"

by

Mr. Qichen WANG


Abstract:

Conjunctive queries form the backbone of SQL queries, and have been extensively 
studied in the literature. In this proposal, we consider two important 
extensions of a basic conjunctive query.  First, we study how to evaluate 
conjunctive queries with predicates in the form of comparisons that span 
multiple relations.  Such predicates have regained interest, due to their 
relevance in OLAP systems, spatiotemporal databases, and machine learning over 
relational data. We design a new algorithm for evaluating conjunctive queries 
with comparisons and identify an acyclic condition under which linear query 
processing time can be achieved.  We also extend our acyclic query algorithm to 
more general queries, resulting in polynomial-factor improvements over previous 
best results for many cyclic queries.

Secondly, we study the problem of incrementally maintaining the results of a 
conjunctive query under updates. Prior work has shown that this problem is 
inherently hard in the worst case. To provide an instance-specific analysis of 
the update cost, we introduce a new measure of complexity of the update 
sequence, which we call the enclosureness, which is a small constant for many 
realistic update sequences, such as  first-in-first-out (FIFO) sequence. We 
present an algorithm to maintain the query results of any acyclic foreign-key 
join query in time linear in the enclosureness. We are currently working on 
extending this algorithm to non-key joins.

All newly proposed algorithms are efficient not only in theory but also in 
practice. We have implemented them on Spark and Flink, and our experimental 
results demonstrate order-of-magnitude speedups against the previous 
state-of-the-art results.


Date:			Friday, 18 February 2022

Time:                  	2:00pm - 4:00pm

Zoom Meeting:
https://hkust.zoom.us/j/95281613710?pwd=ZUJBcENNUUh3SnU4akpRRDUxU24rQT09

Committee Members:	Prof. Ke Yi (Supervisor)
  			Prof. Lei Chen (Chairperson)
 			Prof. Qiong Luo
 			Prof. Xiaofang Zhou


**** ALL are Welcome ****