Databases, Query Processing, and Data Management Theory
Data Systems as Computational Engines
Advanced View
Databases are not merely storage systems; they are optimized query engines with consistency, indexing, and transactional semantics. Research spans query complexity, optimizer correctness, concurrency control, distributed transactions, and probabilistic data structures for large-scale analytics.
Core Database Concepts
Common Indexing Ideas
B-tree family
- Good for ordered data and range queries
- Widely used in disk-backed systems
Hash index
- Fast equality lookup
- Poor for range queries
Optimization Principle
Query planning is a search problem under uncertainty: a theoretically equivalent plan may differ dramatically in real cost because of data distribution and hardware behavior.
Which property is primarily associated with transaction isolation?
Isolation governs the visibility and interaction of concurrent transactional operations.
Correct answer: Controlling how concurrent transactions interact
What is one reason query optimization is hard?
The optimizer must reason about combinatorial plan spaces and uncertain statistics.
Correct answer: Because many execution plans are equivalent logically but have very different runtime costs
Data Complexity and Lower Bounds
Fine-grained lower bounds help explain why certain joins, reachability queries, and dynamic problems resist sublinear or near-constant time solutions. This area connects database theory with computational complexity and communication lower bounds.
Which index type is generally best suited for ordered range queries?
B-trees maintain order and support efficient range scans.
Correct answer: B-tree
Expand ACID.
These are the classic correctness properties of transactions.
Correct answer: Atomicity, Consistency, Isolation, Durability