This website houses notes from my studies at the University of Liverpool. If you see any errors or issues, please do open an issue on this site's GitHub.
The initial query plan, generated from a query, may not be the optimal one. We can complete the following to make it run faster. How to Optimise Queries are evaluated from the bottom up therefore: Efficiency depends on the size of intermediate results. We should rewrite the initial query plan...
Deleting Values To delete a value/pointer pair: Find the leaf that should contain the value. If not there then we are done. Remove the value/pointer pair. Let the current node $C$. Let $x$ be: \[x= \begin{cases} 2 & \text{if } C\text{ is root}\\ \lceil\frac{n+1}2\rceil & \text{if } C \text{ id...
There is a visualisation tool for B+ trees available at https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html. Single vs Multi-Level Indexes Single Level Index - Stores in a single list. Multi-Level Index - Distributes across different layers. B+ Tree Leaves (Idea) $a_1$ $a_2$ $\ldots$ $a_n$ Points to tuples with value $a_1$. Points to tuples with...
Selection can be performed faster if we know where to find the rows that are being selected. One way of doing this is by using indexes. Index Given the values for one or more attributes of a relation $R$, provides quick access to the tuples with these values. Consider that...
This part is not required for the exam. We can perform faster joins provided that the tables are sorted or indexed. In order to sort the data quickly we can do this inside of memory, instead of on the disk. Merge Sort Divide input in two parts P1, P2 Sort...
Equijoins An equijoin: \[R\bowtie_{A=B}\] is defined as: \[\sigma_{A=B}(R\times S)\] $A,B$ are the join attributes. You can see an example on the following tables: Stores code city 12345 1 67910 2 Employees name depart Oscar 12345 Janice 67910 David 67910 $\text{Stores}\bowtie_\text{code=depart}\text{Employees}$ code city name depart 1235 1 Oscar 12345 67910 2...
Executing Query Plans A query plan tells us exactly how to computer the result to a query. On a particular tree we should proceed from bottom to top: graph sig[σ department=worksAt] --> times["⨉"] times --> pid[π department] & piw[π worksAt,name] pid --> Stores piw --> Emplyees Compute an intermediate result...
The query compiler and execution engine are responsible for: Transforming SQL queries into sequences of database operation. Executing these operations. Query Processing Query processing is completed in the following order: graph a[ ] -->|SQL Query| pqp[Parse Query & Pre-process] -->|"Logical Query Plan (relational algebra)"| olqp[Optimise Logical Query Plan] -->|Optimised Logical...
For additional examples of PDAs see this lecture video. Pushdown automata are a computation version (like NFA/DFA) of context free grammars. They are equivalent to CFGs. Pushdown automata are similar to NFAs but they have an infinite stack: As the PDA is reading the input, it can push/pop symbols from...
A PCFG is a probabilistic version of a CFG where each production has a probability. Probabilities of all productions rewriting a given non-terminal must add up to 1, defining a distribution for each non-terminal. String generation is now probabilistic where production probabilities are used to nondeterministically select a production for...