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.
This lecture covers model based specifications. We use models to specify the behaviour of a system. Abstract State Machine Language (ASML) An ASML model is an abstract model that only encodes the aspects of the systems structure that affect the behaviour being modelled. The goal is the use the minimum...
Formal specification is part of a more general collection of techniques that are know as formal methods. Formal methods are all base on the mathematical representation and analysis of software. Formal methods include: Formal Specification Specification Analysis & Proof Transformational Development Program Verification Formal methods aren’t really used as they...
Converting Schedules to Precedence Graphs The precedence graph for a schedule $S$ is defined as follows: It is a directed graph. Its nodes are the transactions that occur in $S$. it has an edge from transaction $T_i$ to transaction $T_j$ if there is a conflicting pair of operations $op_1$ and...
This is how we calculate quickly how much concurrency we can allow while satisfying isolation and consistency. Conflict-Serialisability This is a stronger from of serialisability that is used by most commercial DBMS. It is base on the notion of conflict: A conflict in a schedule is a pair of operations,...
Types of Schedules So far we have seen two extremes of scheduling: Serial Schedules Execute correctly. Maintain consistency of the database. Inefficient in multi-user environments (because transactions have to wait until others are finished). Concurrent Schedules May not execute correctly. May not guarantee consistency of the database or isolation. Efficient...
This lecture will precisely cover the four ACID properties. A - Atomicity A transaction is an atomic unit of processing: An indivisible unit of execution. Executed in its entirety or not at all. Deals with failure: User aborts a transaction (cancel button). System aborts a transaction (deadlock). Transaction aborts itself...
Concurrency Example Consider the concurrency example that was shown before. The specific ordering of the statements made it such that a seat was double-booked. There are a few issues with how the transactions interacted with eachother: The two transactions are not isolated from each-other. Additionally, the outcome in not consistent...
Translating SQL into Low-Level Operations In our example table with the following schema: Emplyees(e_id, first_name, last_name, birth_day, salary) From this we could run the following two statements: SELECT salary FROM Employees WHERE e_id = 1234; UPDATE Employees SET salary = salary * 1.1 WHERE e_id = 1234; These statement could...
These are a sequence of SQL statements one after the other. There may be issues if transactions are running in parallel or if a single transaction fails. Concurrency If multiple people are interacting with a database then you may run into bugs like the following: sequenceDiagram User 1-)Database:Which seats on...
Language Classes A language class is a set of languages. So far we have seen one language class which is the regular languages. Language classes have two important properties: Decision Properties Closure Properties. Decision Properties A decision property for a class of languages is an algorithm that takes a formal...