Podcast
Questions and Answers
What happens when a transaction enters the shrinking phase?
What happens when a transaction enters the shrinking phase?
Which type of Two-Phase Locking (2PL) ensures that exclusive locks are only released after a transaction commits or aborts?
Which type of Two-Phase Locking (2PL) ensures that exclusive locks are only released after a transaction commits or aborts?
What is a characteristic of Conservative 2PL?
What is a characteristic of Conservative 2PL?
In the context of deadlock detection, what is the purpose of the Wait-For-Graph (WFG)?
In the context of deadlock detection, what is the purpose of the Wait-For-Graph (WFG)?
Signup and view all the answers
Which schedule is permissible under Basic 2PL but not under Strict 2PL?
Which schedule is permissible under Basic 2PL but not under Strict 2PL?
Signup and view all the answers
What does the Index file Blocking Factor (BFI) depend on?
What does the Index file Blocking Factor (BFI) depend on?
Signup and view all the answers
Which property ensures that once a transaction is completed, it will remain so even in the event of a crash?
Which property ensures that once a transaction is completed, it will remain so even in the event of a crash?
Signup and view all the answers
How is the number of Data File Blocks calculated?
How is the number of Data File Blocks calculated?
Signup and view all the answers
What is the definition of 'selectivity' in database queries?
What is the definition of 'selectivity' in database queries?
Signup and view all the answers
In a Two-Phase Locking (2PL) protocol, what occurs during the Shrinking Phase?
In a Two-Phase Locking (2PL) protocol, what occurs during the Shrinking Phase?
Signup and view all the answers
What is indicated by the Minimum possible number of levels an index can have?
What is indicated by the Minimum possible number of levels an index can have?
Signup and view all the answers
Which of the following describes the role of internal nodes in a query tree?
Which of the following describes the role of internal nodes in a query tree?
Signup and view all the answers
When optimizing queries through cost-based methods, what is primarily estimated?
When optimizing queries through cost-based methods, what is primarily estimated?
Signup and view all the answers
What anomaly occurs when two transactions read the same value but one overwrites the other's write?
What anomaly occurs when two transactions read the same value but one overwrites the other's write?
Signup and view all the answers
Which of the following describes a Dirty Read?
Which of the following describes a Dirty Read?
Signup and view all the answers
What does an unrepeatable read indicate about a schedule of transactions?
What does an unrepeatable read indicate about a schedule of transactions?
Signup and view all the answers
What type of schedule is defined as being interleaved but equivalent to some serial execution?
What type of schedule is defined as being interleaved but equivalent to some serial execution?
Signup and view all the answers
What does an edge T1 -> T2 represent in a serialization graph?
What does an edge T1 -> T2 represent in a serialization graph?
Signup and view all the answers
Which anomaly involves a transaction reading a temporary incorrect value before a committing transaction rolls back?
Which anomaly involves a transaction reading a temporary incorrect value before a committing transaction rolls back?
Signup and view all the answers
In which scenario can a schedule be considered non-serializable?
In which scenario can a schedule be considered non-serializable?
Signup and view all the answers
Which of the following describes an anomaly that does not allow two readings of the same data item to yield the same result within a transaction?
Which of the following describes an anomaly that does not allow two readings of the same data item to yield the same result within a transaction?
Signup and view all the answers
What is the main disadvantage of using fixed-length records?
What is the main disadvantage of using fixed-length records?
Signup and view all the answers
Which of the following is an advantage of unordered files?
Which of the following is an advantage of unordered files?
Signup and view all the answers
What is a significant drawback of bitmap indexes?
What is a significant drawback of bitmap indexes?
Signup and view all the answers
What does 'internal fragmentation' refer to in the context of record storage?
What does 'internal fragmentation' refer to in the context of record storage?
Signup and view all the answers
How does the performance of searching differ between ordered and unordered files?
How does the performance of searching differ between ordered and unordered files?
Signup and view all the answers
What is the primary benefit of variable-length records over fixed-length records?
What is the primary benefit of variable-length records over fixed-length records?
Signup and view all the answers
In a bitmap index, what does a '1' represent?
In a bitmap index, what does a '1' represent?
Signup and view all the answers
What should be avoided when utilizing bitmap indexes on datasets?
What should be avoided when utilizing bitmap indexes on datasets?
Signup and view all the answers
What is the purpose of the undo action in recovery protocols?
What is the purpose of the undo action in recovery protocols?
Signup and view all the answers
Which recovery protocol option allows a cache page to be flushed before transaction commits?
Which recovery protocol option allows a cache page to be flushed before transaction commits?
Signup and view all the answers
What is the key benefit of using write-ahead logging (WAL) for undo operations?
What is the key benefit of using write-ahead logging (WAL) for undo operations?
Signup and view all the answers
In a nested-loop join, how is the total cost calculated based on relations?
In a nested-loop join, how is the total cost calculated based on relations?
Signup and view all the answers
What strategy is employed in a page-oriented nested loop join?
What strategy is employed in a page-oriented nested loop join?
Signup and view all the answers
What does the block nested loop join do differently compared to a basic nested loop join?
What does the block nested loop join do differently compared to a basic nested loop join?
Signup and view all the answers
Which condition must be met for a single loop join to work effectively?
Which condition must be met for a single loop join to work effectively?
Signup and view all the answers
What happens in the 'no-steal' protocol during a transaction commit?
What happens in the 'no-steal' protocol during a transaction commit?
Signup and view all the answers
Study Notes
Record Organisation
- Record Internal Fragmentation: Wasted space within a record due to fixed record size.
- Block Internal Fragmentation: Wasted space within a block due to fixed record size not fitting "neatly".
-
Fixed Length Records: All records use the same fixed size, even if some fields are empty.
- Pros: Simple to manage, easy to calculate record positions.
- Cons: Can lead to wasted space, inefficient for varying data lengths.
-
Variable Length Records: Record size varies based on data actually stored in the record. They use special symbols and structures to describe stored data.
- Pros: Efficient use of space, adaptable to varying data lengths.
- Cons: More complex to manage, record position calculation might be more complicated.
Ordered and Unordered Files
-
Unordered (Heap) Files: Records are stored in no particular order.
- Pros: Fast insertion.
- Cons: Slow searching, requires full scan (n blocks).
-
Ordered (Sorted) Files: Records are stored in a specific order based on one or more fields.
- Pros: Fast searching.
- Cons: Slow insertion, shifting records on average n/2 blocks.
Bitmap Index
- A data structure using bitmaps, which are bit strings with a 1 for each record matching the attribute and 0 for the rest.
- Pros: High space efficiency, good for queries on multiple keys, suitable for large, static datasets.
- Cons: Not suitable for frequently modified data as updates impact all associated indexes.
Block & Record Calculations
- Average Record Length (R): R fixed + R variable
- Number of Blocks needed for n Records: Total bytes / (block size + pointer to next block)
- Records per Block (RPB) or Blocking Factor: Block Size / Size of each record
- Number of Data File Blocks: Number of records / RPB
- Number of Index Entries: Number of records (for primary index) or tuples of blocks for secondary index.
- Number of Index Blocks: Index entries / (BFI)
- Index File Blocking Factor (BFI): Floor (Block Size / (Field key size + Block Pointer))
- Minimum Number of Levels in an Index: Ceiling (log base index bfr (index records))
ACID Properties
- Atomicity: All actions within a transaction either complete or none are executed.
- Consistency: Data integrity constraints are maintained before and after a transaction.
- Isolation: Concurrent transactions appear to execute sequentially.
- Durability: Committed transactions are permanent even in case of system failures.
Query Trees
- A data structure representing a relational algebra expression.
- Leaf Nodes: Represent input relations.
- Internal Nodes: Represent relational algebra operations.
Algebraic Query Optimisation
- Uses heuristics to optimize query execution.
-
- Selectivity of a condition S=0. # of condition C- Represents the percentage of records in S matching condition C.
Transformation Rules
- Projection (π): Eliminate columns not referred to in the SELECT clause.
- Selection (σ): Filter rows based on a condition in the WHERE clause.
- Cross Product (TABLE1 X TABLE2): Generates a table with all possible combinations of rows from two tables.
- Join (⨝): Combines rows from two tables based on a matching condition.
Two-Phase Locking (2PL)
- Growing Phase: Obtain locks.
- Shrinking Phase: Release locks acquired during the growing phase. No new locks can be acquired in this phase.
- Basic 2PL: Locks are held until the transaction commits or aborts. Can cause deadlocks.
- Strict 2PL: Exclusive or write locks are released only when the transaction completes. Makes recovery simpler.
- Conservative 2PL: All needed locks are obtained before the transaction starts, eliminating the growing phase. Deadlock-free.
Cost-Based Query Optimisation
- Estimates the cost of different execution strategies and chooses the least expensive one.
-
Cost Factors:
- I/O Costs: Reading data from disk.
- CPU Costs: Processing data in memory.
- Network Costs: Data transfer over a network.
2PL Protocols
- Wait-For-Graph (WFG): Uses a lock table to detect deadlocks. One transaction in the deadlock is aborted.
-
Timeout Mechanisms: Used to detect deadlocks.
- Long Timeout: Low risk of aborting non-deadlocked transactions, potentially causing delays in deadlock detection.
- Short Timeout: High risk of aborting non-deadlocked transactions, but quickly handles actual deadlocks.
Schedule S Execution Rules
- W(X): Write to data item X.
- R(Y): Read from data item Y.
- T1: Commit: Permanent commit of T1's changes to the database.
- Shared Locks: Allow multiple transactions to read a data item simultaneously.
- Exclusive Locks: Only one transaction can hold an exclusive lock at a time.
Efficient Equality Search
- Hash Indexes: Efficiently search data based on hash keys.
- B+ Trees: Used to efficiently search and range queries.
- Clustered Indexes: Order the data on disk based on the indexed field for optimized retrieval.
Database Anomalies
- Lost Update: Two transactions read the same value, but updates overwrite each other.
- Dirty Read: One transaction reads a value that another hasn't committed.
- Unrepeatable Read: One transaction reads the same data item and gets different values because of another transaction's changes.
Serializability
- A schedule's interleaved execution is equivalent to a serial execution of the transactions.
Serialization Graphs
- Nodes: Represent individual transactions.
- Edges: Show conflicts between operations of different transactions (T1 -> T2 means T1 precedes and conflicts with T2).
Recovery Protocols
- Undo Actions: Rollback changes made by an uncommitted transaction.
- Redo Actions: Re-apply changes of a committed transaction.
Cache Flushing
- Steal: Cache pages can be flushed even before transaction commits.
- No-Steal: Cache pages cannot be flushed until the transaction commits.
- Force: Cache pages are written to disk when transaction commits.
- No-Force: Cache pages are not written to disk when a transaction commits.
Write-Ahead Logging (WAL)
- Used for recovery (undo/redo) operations.
- Undo: A Before Image File (BIFM) must be written to log before its corresponding After Image File (AFIM) is written to disk.
- Redo: All AFIMs must be written to the log before a transaction commits.
Join Operations
-
Nested-Loop Join:
- Outer relation is scanned once.
- Inner relation scanned once for each record in outer relation.
- Cost: Blocks in outer + Records in outer x Blocks in inner
-
Page-Oriented Nested Loops:
- Compares a block of records from outer with all blocks from the inner relation.
- Cost: Blocks in outer + Blocks in outer * Blocks in inner
-
Block Nested Loop Join:
- Reads as much as possible from outer file at a time.
- One block for buffering, one for inner file, rest are for outer file.
- Cost: Blocks in outer + Blocks in inner x (Blocks in outer / (Number of blocks in memory - 2)).
-
Single Loop Join:
- Utilizes an index for the inner relation to reduce scans.
- Cost: Cost depends on index and outer file, often much faster than nested loop.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Explore the fundamentals of record organisation including internal fragmentation, fixed and variable length records, as well as the differences between ordered and unordered files. Understand the pros and cons associated with each method and how they impact data management.
