One Computer Science MSc thesis to be presented on 15 August

Thursday, 15 August there will be a master thesis presentation in Computer Science at Lund University, Faculty of Engineering.

The presentation will take place in E:2116.

Note to potential opponents: Register as an opponent to the presentation of your choice by sending an email to the examiner for that presentation (firstname.lastname@cs.lth.se). Do not forget to specify the presentation you register for! Note that the number of opponents may be limited (often to two), so you might be forced to choose another presentation if you register too late. Registrations are individual, just as the oppositions are! More instructions are found on this page.

10:15-11:00 in E:2116

Presenters: Sebastian Malmström, Katia Svennarp
Title: Optimising Query Execution: Minimising Re-Computations through Structural Analysis and Partial Updates
Examiner: Niklas Fors
Supervisor: Christoph Reichenbach (LTH)

In a world where the volume of collected data increases daily, larger and larger amounts of computations are needed to deliver data to the end-user. This leads to a need for more efficient data handling as well as identifying opportunities for avoiding unnecessary computation.

This thesis examines a view maintenance architecture, which involves pre-computing the results of common queries and storing them in a separate data structure. It will analyse how the structure of a query can influence its execution time and explore whether computation can be optimised through partial updates. Two methods have been implemented. The first method updates only the parts affected by new changes. However, determining whether a query needs to be executed can sometimes take longer than running the query itself. To address this, the second method updates the affected parts and executes groups of queries with short execution times.

We evaluated these methods through three distinct experiments. The first two experiments focused on the static analysis of queries, aiming to identify appropriate operations to classify as complex as well as finding thresholds for classifying groups of queries based on individual results. The final experiment addressed the issue of partial updates in the context of view maintenance.

The key findings are that predicting computational complexity is feasible but heavily dependent on the specifics of the database. Implementing logic for deciding which queries to run instead of running them all can save significant time and computations.

Link to popular science summary: https://fileadmin.cs.lth.se/cs/Education/Examensarbete/Popsci/240815_10MalmstromSvennarp.pdf