Database Transaction Concurrency: Failures, Logs, and Schedules
Homework #9
Lauri Burke
CINS 370
4/29/2016
21.1. Concurrent Execution in Multiuser Systems
A multiuser system is a system which can be used by more than one user at a time.
Why is Concurrency Control Needed?
Concurrency control is used to prohibit transaction conflicts. Here are some examples of problems that can occur without it:
- The Lost Update Problem: Two or more transactions try to read and update the same data concurrently. The last update overwrites previous updates, resulting in lost data.
- Temporary
NP-Complete Problems and Reductions: A Detailed Look
NP-Completeness: Key Concepts
NP (Non-deterministic Polynomial time): Problems where a proposed solution (certificate) can be verified in polynomial time. A ‘guesser’ proposes a solution, and a ‘verifier’ checks it. Both guessing and verifying happen in polynomial time.
Every problem in NP can be reduced to SAT (Satisfiability) – Cook-Levin Theorem.
Problem Definitions
Independent Set (IS)
Given a graph G = (V, E) and an integer K, is there a set I (subset of V) with |I| ≥ K such that for any u, v
Read MoreIntroduction to Operating Systems and Concurrency
Operating System Concepts
Introduction
An operating system (OS) acts as a virtual machine, abstracting the complexities and limitations of hardware from application programmers. It manages various aspects of computation, including job scheduling, resource allocation, and process management.
Jobs and Processing
A job represents a unit of processing. Early operating systems employed batch processing, collecting multiple jobs before execution and printing results afterward. Modern systems often utilize
Read MoreDigital Age Essentials: Computers and Peripherals
What is the Digital Age?
The digital age is the massification of technology in our lives.
What is a Computer?
A computer is an electronic machine capable of solving high-speed operations for the benefit of man.
Computers in Banks and Schools
In banks, computers store information, enable staff to access large databases, and carry out financial transactions at high speed.
In schools, they are used to access the internet, do basic research, give presentations, and write letters.
Hardware vs. Software
Hardware
Read MoreEvolution and Properties of Relational Database Models
Evolution of Relational Database Systems (1980-1990)
- Development of large relational systems – SQL commercial.
- Development of application generators.
- Distributed systems.
- Client/server structure (visual languages).
- Object-oriented relational model.
New Data Representation Models (1980-1990)
- Problems in the relational model: The semantics of complex items are poorly reflected.
- Connection of existing data with information in the DB.
- “Intelligent” unified representation of rules and data, knowledge bases, intelligent
Microprocessor Bus and Memory Types: Essential Functions
What is the Role of the Address Bus?
The address bus is a totally independent channel from the microprocessor to the data bus, which contains the memory address of the data in transit. It consists of a set of power lines needed to establish a directional memory capacity. The addressable memory capacity depends on the number of bits that make up the address bus, with 2n (two raised to the n) representing the maximum bytes of the memory bank that can be addressed using *n* lines.