Distributed Databases

Question 1

Distributed Databases

Answer 1

Distributed DBMS provide access to data at all sites.
Lets say we have one store in Liverpool. This store might eventually spread to Manchester or London etc.

The concrete definition of a distributed database if a collection of multiple logically interrelated databases which is distributed over a computer network.

Question 2

Advantages of distributed databases

Answer 2

• help provide us access to these different data sites
• we don’t have to specify where the data is from and we can just grab it from wherever
• can gives many users access to large datasets
• answer to queries faster by distributing tasks over the nodes
• easier to scale (just add new node)

Question 3

Fragmentation

Answer 3

Split database in different parts which we can store at different nodes.

Question 4

Horizontal Fragmentation

Answer 4

Fragmenting the database from top to bottom (rows).
Data is stored as tuples.

Question 5

Vertical Fragmentation

Answer 5

Fragmenting the database based upon columns.
Data is stored as columns in other databases.

Question 6

Fragmentation Transparency

Answer 6

The user does not see this fragmentation, just the full relations.

Question 7

Entire Relation

Answer 7

Union of the fragments.

Question 8

Fragmentation Advantage

Answer 8

Using these fragmentations can help resilience; if there is a failure in one store, there are other stores which hold the fragments of the database.

Question 9

Types of replication

Answer 9

• full replication
• no replication
• partial replication

Question 10

Full Replication

Answer 10

Each fragment is stored at every sight.

Question 11

No Replication

Answer 11

Each fragment is stored at a unique site.

Question 12

Partial Replication

Answer 12

Limit number of copies of each fragment, where we replicate only some fragments.

Question 13

Types of transparency

Answer 13

• fragmentation transparency
• replication transparency
• locations transparency
• naming transparency

Question 14

Fragmentation Transparency

Answer 14

Fragmentation is transparent to others.

Question 15

Replication Transparency

Answer 15

Ability to copy data items at different sites where the replication is transparent to others.

Question 16

Locations Transparency

Answer 16

The location where data is stored is transparent to users.

Question 17

Naming Transparency

Answer 17

A given name has the same meaning everywhere in the system. Like the relation names must be the same everywhere.

Question 18

Concurrency Control in DDBMS

Answer 18

Locks are the main contributor in terms of concurrency.

Question 19

Types of locking distributions for DDBMS

Answer 19

• one computer grants all locks
• one computer grant many locks but with backups
• many computers with different authorities
• many computers with different authorities but with backups

Question 20

One computer grants all locks

Answer 20

If the computer fails, we have to restart everything that is running, since we do not have backups.
There are too many transactions for one computer to handle.

Question 21

One computer grant many locks but with backups

Answer 21

Solves the restarting problem since we have backups, but we need to keep everything synced.

Question 22

Many computers work together to grant keys

Answer 22

It is not sure which computer to ask for which key.

Question 23

Many computers work together to grant keys

Answer 23

The previous problem still remains, but now we also have to sync.

Question 24

Voting

Answer 24

1) Each site with a copy of an item has a local lock that it can grant transactions for that item.
2) If a transaction gets over half the local locks for an item (since sites can hold the same item/lock), it receives a global lock on that item. If it does get this lock, it must tell the sites with a copy that it has the global lock.
3) If the transaction takes too long to receive the global lock, it must stop trying to get it.
4) The only drawback is that it requires a lot more communication.

Question 25

Recovery in DDBMS

Answer 25

Global transactions have faulty ways of working, since node faults could result in the whole system having to be rolled back (which could not happen, breaking atomicity).
Therefore we use distribution commits.

Question 26

Two-phase commits protocol

Answer 26

Contains coordinators that execute at some node and decides if and when local transactions can commit.
Logging is used here to log messages sent to and received from other nodes at each node locally.

Question 27

Phases in TPCP

Answer 27

Phase 1 -> Decide whether we commit or abort.
Phase 2 -> Either commit or abort.

Question 28

Phase 1

Answer 28

After receiving a message from the coordinator, lets say prepare T, the nodes individually have to decide whether they are ready to commit or not:
- if they are all ready, we go into a pre-committed state and send back ready T
- if there is an abort, we send back don’t commit T to the coordinator and abort the local transaction

Question 29

Phase 2

Answer 29

Once phase 1 is successful, the coordinator sends the message commit T to all nodes.
If the coordinator receives at least one don’t commit message, or nothing at all from one node for some time, it sends a message back to all methods saying abort T.

Question 30

Phase 1 Logging

Answer 30

The stages:
- <prepare> to log
- send prepare T as message
The node then can either send don't commit or ready.
- if the node sends don't commit, we first log <don't commit T> and then send message to coordinator, which will eventually instruct the node to abort T.
- if the node is ready, it log <ready>, and sends ready T to the coordinator</ready></prepare>

Question 31

Phase 2 Logging

Answer 31

If some nodes don’t respond, or have responded don’t commit, the coordinator logs <abort> and sends that message to the nodes.
Otherwise, it logs <commit> and sends the message to commit.</commit></abort>

Question 32

Three-phase commit protocol

Answer 32

The issue with two phase is that if the coordinator and some transaction crashes, all the while everyone else is in the pre-committed state.
Depending if we commit or abort, we could break ACID properties. Therefore, we split phase 2 into 2 parts:
- Phase 2(a) -> prepare to commit. Send the decision to all nodes, and nodes go into prepare to commit state.
- Phase 2(b) -> the old phase 2.
Essentially, if the coordinator goes down, then the nodes will receive nothing, and therefore they will know to abort.

Question 33

Query Processing

Answer 33

The issue with query processing is that if we have a distributed database, then the data we want in our query can only be found other databases. Therefore we send a request, resulting in slow queries.
So instead, we use joins to help us, specifically a semi-join.

Question 34

Semi-join

Answer 34

⋉
Used to represent the rows in a specific table that would be joined using join methods.
The specific table depends if we use left or right semi-join.

Question 35

Left semi-join

Answer 35

R ⋉ S
Means that all tables that would have joined in R with some row in S are displayed.

Question 36

Right semi-join

Answer 36

R ⋊ S
Means that all tables that would have joined in S with some row in R are displayed.