# Exam

The exam is in two part. The first part is purely about the lectures contents and should be answer on paper. The second part small lab work to perform on computer.

## Part 1. On paper.

Who is the amazing father of relational database.

Recall the acronyme ACID and its meaning.

Recall the definition of inner and outer joins in the relational algebra. If you don’t remember the syntax, just redefine your own symbols.

Quickly sketch a proof that inner joins are associatives

Show with an example that outer joins are not associatives

In the following, we have a relational arity \(2\) predicate \(R\) that we see as a directed graph.

For the following assertion, gives if possible a first-order logic
formulas describe the property and if not provide a **quickly
sketch** arguments explaining why it is not possible.

- \(R\) is a path
- \(R\) is a complete graph
- \(R\) is without triangles
- \(R\) doesn’t contains cycles

## Part 2. On machine.

In this part, you can reuse all the code that you have written for
the first lab. In particular, you will need the function
`random_relation`

.

Write down a naïve algorithm that perform the left join of two randomly generated binary relations with the equality of the first columns.

Plot the time taken by performing the naive algorithm for left joins between two random relations with the following constraints:

- One plot with the first relations being of size \(n\) and the second of size \(n^2\)
- One plot with the two relations beings of the same size.

Perform a complexity analysis of the problem

Propose an improve algorithm and perform a complexity analysis of the query

Propose a SQLite Schema to host two binary relations

Propose a script to populate the schema

Analysis the performance of your code compared to SQLite. Make some guess on how to improve your implementations.

Compiled the: lun. 07 oct. 2024 15:20:53 CEST