# Database I, année 2023

# Database 1

- 24 hours, 6 lectures 6 exercises
- Education cycle: Second cycle, Master Program 1st year
- Main field of study: Computer Science and Engineering, Applied Mathematics

## Lectures objective

At the end of the course, a successful student should be able to master the main techniques and algorithms that allow relational databases to handle efficiently large amount of data. These methods form the bases of systems that handle larger amounts of data. After attending this course the successful student will be able to:

- Understand the theory behind relational algebra, logic, SQL,
- Manipulate a common db-engine (PostgreSQL, SQLite)
- Write queries,

## Evaluations

- One graded homework
- One terminal evaluation on machine (on the last lecture)

## Temporary plan

### Introduction to relational databases (2h)

- General and historical presentations
- Codd’s relational model of data
- Modelisation
- Null and tree value logics /!

- Basic querying with SQL
- Lab 1:
- The algorithmic behind joins

- Lab 2:
- Discovering PostgreSQL and SQLite
- Refreshal in SQL

- Ressources:

### First order logic, relational algebra and finite model theory (4h)

Quick introduction into finite model theory

First order logic over relational structure

Equivalence between Relational algebra and first order logic

Ehrenfeucht–Fraïssé game and inexpressibility results

Inexpressibility of graph Connectivity.

Lab 3:

- Interacting with SQL from Python

Lab 4:

- Large graphs

Ressources:

- Elements of Finite Model Theory of Leonid Libkin (Chapter 1 and Chapter 3)

### Query optimisation (2h)

Behind the scene: datalayout

Joinfree Query cost-model

- data density
- cost models
- Statistical aggregates
- A full scan cost

Joins, Joins, Joins and again Joins!

Lab 5

- Playing with join free query, the cost model and index selectivity

Ressources:

Compiled the: sam. 10 févr. 2024 16:29:27 CET