Title: Theory / Important / CS / Algo / Database / Database System Concept 6 - McGraw Hill+27{ / 4 Transaction
Tags: récupéré hasSeenConjDef computer_to_instruction FromInstruction complexity hasNotNewEffectReturnsMeaning seen_description

Name: A transaction
Definition: A unit of program execution that accesses and possibly updates various data items
Page: 627
Chapter: 14
Section: 1
Context: database

Instruction: begin transaction
foo
end transaction
Page: 627
Effect: Introduce a sequence foo of queries as a transaction
Language: sql
Chapter: 14
Section: 1

Question: In case of failure during the transaction
Answer: the whole transaction should be aborted.
Page: 627
Chapter: 14
Section: 1

Name: Atomicity
Definition: Either all operations of the transaction are reflected properly in the database, or none are.
Page: 628
Chapter: 14
Section: 1

Name: Isolation
Definition: Even though multiple transactions may execute concurrently, the system guarantees that, for every pair of transactions T i and T j , it appears to T i that either T j finished execution before T i started or T j started execution after T i finished. Thus, each transaction is unaware of other transactions executing concurrently in the system.
Page: 628
Chapter: 14
Section: 1
Context: Transaction

Name: Durability
Definition: After a transaction completes successfully, the changes it has made to the database persist, even if there are system failures.
Page: 628
Chapter: 14
Section: 1
Context: Transaction

Name: Consistency
Definition: the fact that the execution of a transaction (assuming an execution is treated in isolation) preserves the data integrity
Page: 628
Chapter: 14
Section: 1
Context: Transaction database

Name: ACID properties
Definition: Atomicity
Page: 629
Chapter: 14
Section: 1
Context: Transaction
Definition2: Consistency
Conjdef: all of
Definition3: Isolation
Definition4: Durability

Name: A failed transaction
Definition: A transaction after the discovery that normal execution can no longer proceed.
Page: 633
Chapter: 14
Section: 4
Context: Transaction

Name: An aborted transaction
Definition: A transaction which did not complete its execution successfully
Page: 633
Chapter: 14
Section: 4
Context: Transaction

Name: A rolled back database
Definition: A database in a state after some aborted transaction is undone
Page: 633
Chapter: 14
Section: 4
Context: Transaction

Name: A log
Definition: Identifier of the transaction performing the modification
Page: 633
Chapter: 14
Section: 4
Definition2: the identifier of the data item being modified,
Conjdef: A file, such that for each transaction, it contains
Definition3: both the old value (prior to modification) and the new value (after modification) of the data item.

Name: A committed transaction
Definition: A transaction that completes its execution successfully
Page: 633

Name: A compensating transaction for \(t\)
Definition: A compensation which cancel the effect of \(d\)
Page: 633
Variables: \(t\) a transaction
Example: is removing 20$
Applied to: adding 20$

Name: The state of a transaction
Definition: active
Page: 633
Variables: \(t\) a transaction
Definition2: partially committed
Conjdef: Either
Definition3: failed
Definition4: aborted
Definition5: committed

Name: An active transaction
Definition: A transaction before the end of its execution
Page: 633
Context: Database transaction

Name: A partially committed transaction
Definition: The state of the transaction after the final statement has been executed
Page: 633

Name: A failed transaction
Definition: The state of the transaction after the discovery that normal execution can no longer proceed.
Page: 633

Name: Aborted transaction
Definition: A transaction, after it has been rolled back and the database has been restored to its state prior to the start of the transaction.
Page: 633

Name: Committed transaction
Definition: A transaction after successful completion.
Page: 633

Question: An active transaction can become
Answer: partially committed or failed
Page: 634
Chapter: 14
Section: 4

Question: A partially committed transaction can become
Answer: committed or failed
Page: 634
Chapter: 14
Section: 4

Question: A committed transaction can become
Answer: nothing
Page: 634
Chapter: 14
Section: 4

Question: A failed transaction can become
Answer: aborted
Page: 634
Chapter: 14
Section: 4

Question: A aborted transaction can
Answer: be restarted or killed
Page: 634
Chapter: 14
Section: 4

Name: A terminated transaction
Definition: A transaction either aborted or committed.
Page: 634

Name: Restarting the transaction \(t\)
Definition: Creating a new transaction, identic to \(t\)
Page: 634
Variables: \(t\) a transaction
Intuition: Transaction is aborted because of hard or software error

Name: Killing the transaction \(t\)
Definition: Chosing not to do the transaction \(t\) at all.
Page: 634
Variables: \(t\) a transaction

Name: Observable external write
Definition: A write done outside of the system.
Page: 634
Example: Sending email, writting to screen

Question: What is the problem with observable external write
Answer: it can not be cancelled.
Page: 634
Chapter: 14
Section: 4

Question: How to use observable external write
Answer: the database system to store any value associated with such external writes temporarily in a special relation in the database, and to perform the actual writes only after the transaction enters the committed state.
Page: 635
Chapter: 14
Section: 4
Answer2: Use a compensating transaction if the transaction was killed
Example: Assume the bank confirmed to the machine to give bill. Machine went done and did not give them.
Cancel by telling it to the bank, instead of giving bills hours later.

Question: Difference between failed and aborted transaction ?
Answer: Aborted follows fails. Aborted cancel what was done prior to failure
Page: 660
Chapter: 14
Section: 4

Name: An exclusive lock
Definition: A lock allowing its owner to read and write a ressource
Page: 661
Chapter: 15
Section: 1.1
Context: Database
Representation: X

Name: A shared lock
Definition: A lock allowing its owner to read a ressource but not to write it
Page: 661
Chapter: 15
Section: 1.1
Context: Database

Question: When two transactions have a lock on the same ressource
Answer: the lock must be a shared lock (i.e. no one can write)
Page: 662
Chapter: 15
Section: 1.1
Context: Database

Name: Requesting a lock
Definition: A transaction state to the concurrency-control manager that it wants a lock on some ressource
Page: 662
Chapter: 15
Section: 1.1
Context: Database

Name: Granting a lock
Definition: concurrency-control manager state to a request that it has the lock it did request
Page: 662
Chapter: 15
Section: 1.1
Context: Database

Name: Compatibility function
Definition: A function taking two kinds of lock (possibly the same), and stating whether they are compatible
Page: 662
Chapter: 15
Section: 1.1
Context: Database locks

Name: A and B are compatible
Definition: Two transactions may have locks of type A and B on a same ressource
Page: 662
Chapter: 15
Section: 1.1
Variables: A, B locks
Context: Database locks

Question: What happens if a transaction request a lock which is not compatible with another current lock ?
Answer: It must wait until the lock is removed
Page: 662
Chapter: 15
Section: 1.1
Context: Database locks

Name: deadlock
Definition: When each transaction wait for some resource (all locked by other transactions) and none will free any ressource until they have those resource.
Page: 662
Chapter: 15
Section: 1.1
Context: Database locks

Name: Locking protocol
Definition: A protocol indicating when a transaction may lock and unlock each of the data items
Page: 666
Chapter: 15
Section: 1.1
Context: Database locks
Intuition: restrict the number of possible schedules.

Name: \(T_i\) precedes \(T_j\) in \(S\)
Definition: there exists a data item \(Q\) such that \(T_i\) has held lock mode \(A\) on \(Q\), and \(T_j\) has held lock mode \(B\) on \(Q\) later, and \(\mathrm{comp}(A,B)=false\).
Page: 666
Chapter: 15
Section: 1.1
Variables: \(\{T_0,\dots,T_n\}\) a set of transaction
\(S\) a schedule
Context: Database locks
Notation: \(T_i\rightarrow T_j\)

Name: A legal schedule under \(P\)
Definition: A scheude which is possible for a set of transactions that follows the rules of the locking protocol
Page: 666
Chapter: 15
Section: 1.1
Variables: \(A_1,\dots,A_n\) a set of kind of locks
\(P\) a protocol
Context: Database locks

Name: A locking protocol ensuring conflict serializability
Definition: A locking protocol such that all legal schedules are conflict serializable.
Page: 666
Chapter: 15
Section: 1.1
Variables: \(A_1,\dots,A_n\) a set of kind of locks
Context: Database locks
Definition2: For all legal schedules the associated \(\rightarrow\) relation is acyclic

Name: Running transactions serially
Definition: Running transactions one after the other, waiting for a first to end before starting a next one
Page: 635
Chapter: 14
Section: 5

Name: The throughput of a system
Definition: the number of transactions executed in a given amount of time.
Page: 636
Chapter: 14
Section: 5
Context: Database

Name: Utilization of the resource
Definition: The inverse of the time this resource idle/does not perform useful work
Page: 636
Chapter: 14
Section: 5
Context: Database

Name: average response time
Definition: The average time between a transaction is requested and it is executed
Page: 636
Chapter: 14
Section: 5
Context: Database

Question: Why we should not restrict ourself to serial execution of transactions
Answer: Transaction use IO and processor. They can be parallelized. While one use IO, another can be processed
Page: 636
Chapter: 14
Section: 5
Context: Database
Answer2: It would increase average time, since request should wait before being executed
Answer3: Multiple processor may be available

Name: A schedule for \(\mathcal T\)
Definition: A chronological order in which instructions of each \(T_i\) are executed in the system
Page: 639
Chapter: 14
Section: 5
Variables: \(\mathcal T=\{T_1,\dots,T_n\}\) a set of transactions
Context: Database

Name: A serial schedule
Definition: A schedule executing each instruction of a transaction before doing the instruction of another transaction
Page: 639
Chapter: 14
Section: 5
Variables: \(\mathcal T=\{T_1,\dots,T_n\}\) a set of transactions
Context: Database

Name: concurrency-control component of the database system
Definition: Part of the DB system ensuring that any schedule that is executed will leave the database in a consistent state
Page: 639
Chapter: 14
Section: 5
Context: Database

Name: A serializable schedule
Definition: A schedule whose effect is equivalent to a serial schedule
Page: 640
Chapter: 14
Section: 5
Context: Database

Name: I and J conflicts
Definition: Both I and J consider the same data, at least one is a write
Page: 642
Chapter: 14
Section: 5
Variables: I and J operations (read or write)
Context: Database transaction

Smaller0: I and J conflicts
Greater0: I and J can be swapped, while preserving equivalence of the total schedule
Page: 643
Chapter: 14
Section: 5
Variables: S a scheduleI and J operations of S (read or write)
Smaller to greater: xor
Context: Database transaction

Name: \(S\) and \(S'\) are conflict equivalent
Definition: \(S'\) can be obtained from \(S\) by swapping a sequence of operations which are not conflict
Page: 643
Chapter: 14
Section: 5
Variables: \(\{T_1,\dots,T_n\}\) a set of transactions
\(S,S'\) schedules for the \(T_i\)'s

Name: A conflict serializable schedule
Definition: A schedule conflict equivalent to a serial schedule
Page: 643
Chapter: 14
Section: 5
Variables: \(\{T_1,\dots,T_n\}\) a set of transactions

Name: A precedence graph from \(S\)
Definition: vertices are the transactions participating in the schedule
Page: 643
Chapter: 14
Section: 5
Variables: \(\{T_1,\dots,T_n\}\) a set of transactions
\(S\) a schedule for those transactions
Definition2: edges consists of all edges \(T_i\to T_j\) for which either \(T_i\) and \(T_j\) executes operations \(I_i,I_j\), in conflict and in this order
Conjdef: A graph with

Name: A serializability order for \(S\)
Definition: A topological sorting of the precedence graph of \(S\)
Page: 643
Chapter: 14
Section: 5
Variables: \(\{T_1,\dots,T_n\}\) a set of transactions
\(S\) a schedule for those transactions

Page: 643
Section: 5
Chapter: 14
Name: View serializability
Time complexity: NP-complete
Variables: \(\{T_1,\dots,T_n\}\) a set of transactions
\(S\) a schedule for those transactions
Language: sql