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.

0. Who is the amazing father of relational database.

1. Recall the acronyme ACID and its meaning.

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

3. Quickly sketch a proof that inner joins are associatives

4. Show with an example that outer joins are not associatives

5. 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.

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

2. 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.

3. Perform a complexity analysis of the problem

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

5. Propose a SQLite Schema to host two binary relations

6. Propose a script to populate the schema

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

Compiled the: mar. 19 mars 2024 16:13:04 CET