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.
V & V is a whole-life cycle process. it must be applied at each stage in the software process. Verification This is whether the software confirms to its specification: This may involve checking that it meets its functional and non-functional requirements. Validation This is whether the software does what the...
Often problems involving large datasets can be divided into many small problems that can be solved in parallel and then have their results combined. MapReduce is a programming framework that allows us to implement two methods: Map - The computation on the smaller chunks of data. Reduce - How the...
If we don’t have all the information we need for a query at a node, we need to request information from other sites: This is very slow. Joins are the most expensive operation. Joins We can often send less than the whole table over the network when completing joins. Semijoins...
Concurrency Control CC in DDBMS Using Locks Locks for concurrency control can be used in many different ways: No Backups Backups One Authority One computer does all the locks. There are backups if the primary fails. Many Authorities Database items can have different computers in charge of their locks....
This lecture covers transparency: Things that the DDBMS keeps hidden from people accessing the database. Fragmentation and replication are examples of the things that are handled transparently. Fragmentation This is where the database is split into different fragments that can then be stored at different nodes. Horizontal Fragmentation (Sharding) Fragment...
We want to have databases at several sites, which only hold data that is primarily relevant to them. Distributed Databases They are a: Collection of multiple logically interrelated databases. Distributed over a computer network. graph LR A ---|network link| B --- C["C (node/site)"] --- A The databases are connected by...
Consider that we want to make a TM that accepts the following language: \[L=\{w\#w:w\in\{a,b\}^*\}\] We can write the following program, that instructs the head: Until you reach $\#$ Read and remember entry ($x\underline bbaa\#xbbaa$) Write $x$ ($x\underline xbaa\#xbbaa$) Move right past $\#$ and past all $x$s ($xxbaa\#x\underline bbaa$) If this...
What is a Computer A computer is a machine that manipulates data according to a list of instructions: graph LR program --> computer input --> computer computer --> output It is impossible for computer to predict what any computer program will do. Turing Machines graph control -->|head| a subgraph tape...
This method has two keys: Public key: Known to all. Used for encryption. Private key: Only known to the receiver. Used for description. graph LR Alice -->|m| ea[Encryption Algorithm] bp[Bob's Public Key] -->|KB+| ea ea -->|"KB+(m)"| da[Decryption Algorithm] bpr[Bob's Private Key] -->|KB-| da da -->|"m"| Bob The following notation is...
In symmetric key cryptography both parties share the same key: graph LR Alice -->|plaintext| ea[Encryption Algorithm] ka[Shared Encryption Key] -->|KS| ea ea -->|"ciphertext (KS(m))"| da[Decryption Algorithm] kb[Shared Decryption Key] -->|KS| da da -->|plaintext| Bob Symmetric Ciphers The following are examples of symmetric ciphers: Caesar Cipher (ROT13) All letters in the...