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.
Transaction Scheduling in a DBMS Transaction scheduling looks like the following inside a DBMS: graph LR so[Stream of Operations] -->|Operations of Transactions| Scheduler -->|"(Conflict) Serialisable Schedule"| b[(Buffers)] Scheduler -->|Execute or Delay Request| Scheduler This needs to be completed live, as transactions come into the system. Using Locks This is a...
The transport layer provides logical communication between application processes running on different hosts. Sender - Breaks the application messages into segments and passes to the network layer. Receiver - Reassembles the segments into messages and passes them to the application layer. There are two transport layer protocols available: TCP UDP...
Convert from $\epsilon$-NFA to NFA: First keep track of the closures (The states that have epsilon transitions): $CL(B)=(B,D)$ $CL(E)=(E,B,C,D)$ Accept states include those that have an accept state in their closure. Then make a table of the transitions including epsilon transitions: 0 1 $A$ $E,B,C,D$ $B,D$ $B$ $\emptyset$ $C$...
Why Are All Distinguishable Pairs Found? This is because we work backwards from the accept states. There are $n^2$ pairs of states for each DFA where $n$ is the number of states. Therefore, the number of pairs of states to be searched is finite. Why Are There No Inconsistencies When...
Finding Indistinguishable States If $q$ is accepting and $q’$ is rejecting, mark $(q,q’)$ as distinguishable: stateDiagram-v2 direction LR [*] --> q(x) q'(x) --> [*] If $(q_1,q_1;)$ are marked, mark $(q_2,q_2’)$ as distinguishable: stateDiagram-v2 direction LR q2(x) --> q1(x):a q2'(x) --> q1'(x):a Unmarked pairs are indistinguishable, merge them into groups. Example...
Proving Minimalism Consider the following minimal DFA for the language $L={w:w\text{ ends in }111}$: stateDiagram-v2 direction LR [*] --> q0 q0 --> q0:0 q0 --> q1:1 q1 --> q2:1 q2 --> q3:1 q3 --> q3:1 q3 --> q0:0 q2 --> q0:0 q1 --> q0:0 Is it possible to do this...
Proving Non-Regularity For all $n$ there exists $z$ longer than $n$, such that for all ways of writing $z=uvw$ where: $\vert uv\vert\leq n$ $\vert v\vert\geq 1$ For all $i\geq0$, the string $uv^iw$ is not in $L$. This is a Ehrenfeucht-Fraïssé game between two players: Adam (for all) Eve (exists) Round...
Non-Regular Language Example Consider the following language: \[L_0=\{0^n1^n\vert n\geq0\}\] This is the language of any number of zeros followed by an equal number of ones. To show that this is non-regular we reason by contradiction: Suppose we manage to construct a DFA $M$ for $L_0$ with $n$ states. We argue...
This tutorial relates to the questions here. Question 1 The short hand notation would be: \[S_a: r_1(X);w_1(X);c_1;r_2(X);w_2(X);c_2;\] The schedule is a serial schedule as the transactions are run one after the other. The following ACID properties are broken: No ACID properties are broken as there are no writes to the...
This tutorial covered the use cases of an online hotel booking system: ID UC1 Name Password Reset Description Allows the user to reset their password. Pre-condition System is in operation. Includes UC3(UserLogin) Event Flow User enters new password twice to confirm and submits password. Post-condition Password is updated. Extensions Send...