DATABASE SYSTEMS The Complete Book
Chapter 1: The Worlds of Database Systems
Introduction:
Databases are essential for businesses, scientific investigations, and web services like Google and Amazon. They manage large amounts of data efficiently through specialized software known as Database Management Systems (DBMS).
DBMS are powerful tools designed to create, manage, and store large volumes of data securely and durably over long periods. This chapter explores the basics of DBMS and their evolution.
1.1 The Evolution of Database Systems
What is a Database?
A database is essentially a collection of information managed by a DBMS, which allows it to persist over many years.
A DBMS must:
Allow users to create databases and specify their schema (data structure).
Enable users to query and modify data using a query language.
Support the storage of vast amounts of data (terabytes and more).
Provide durability (recovery after system failures).
Control access for multiple users, ensuring isolation and atomicity.
1.1.1 Early Database Management Systems
Early systems (late 1960s) evolved from file systems that stored data but did not guarantee durability or efficient data retrieval.
They lacked query languages and schema support, requiring users to write complex programs for basic data retrieval tasks.
Examples of early DBMS applications included:
Banking systems: Tracking accounts and ensuring data security.
Airline reservation systems: Managing reservations and ensuring system reliability.
Corporate record-keeping: Managing employee, inventory, and financial records.
1.1.2 Relational Database Systems
A significant shift occurred in 1970 with Ted Codd's proposal to organize data into tables (relations), simplifying database management.
Relational systems allowed users to query data without worrying about storage structures, increasing the productivity of database programmers.
SQL (Structured Query Language) became the dominant query language for relational databases.
1.1.3 Smaller and Smaller Systems
Originally, DBMS were large and required big machines to store gigabytes of data. As technology advanced, it became feasible to run a DBMS on personal computers, making database tools more widely available.
The rise of XML (Extensible Markup Language) led to the use of databases for managing large collections of documents, particularly in web-based applications.
1.1.4 Bigger and Bigger Systems
The storage of petabytes (1,000 terabytes) of data became common with large web services like Google and YouTube. Examples include:
Google’s storage of web data for search engine purposes.
Flickr: Millions of images stored in searchable databases.
YouTube: Large video repositories requiring sophisticated DBMS for efficient retrieval.
Peer-to-peer file sharing: Distributed storage across conventional machines, resulting in massive collective databases.
1.1.5 Information Integration
Information integration became crucial as organizations with multiple divisions (often using different DBMS and terminologies) needed to unify their data.
Solutions include data warehouses (centralized copies of data from various sources) and middleware (software that facilitates communication between different databases).
1.2 Overview of a Database Management System
A DBMS is comprised of several core components. These include:
Data-Definition Language (DDL) Processor: For handling schema-altering commands from a Database Administrator (DBA).
Query Processor: Responsible for parsing and optimizing queries into executable plans.
Storage Manager: Handles the storage of data on disk and its movement to main memory via buffers.
Transaction Processor: Ensures transactions are executed with atomicity and durability.
1.2.1 Data-Definition Language Commands
The DDL allows a DBA to define the structure of a database (schemas), which is critical for organizing how data is stored and manipulated.
1.2.2 Overview of Query Processing
Queries are processed through parsing, optimization, and execution, ensuring that the DBMS efficiently retrieves or modifies the requested data.
1.2.3 Storage and Buffer Management
Data is stored in secondary storage (typically magnetic disks), and the buffer manager ensures data is available in main memory when needed.
1.2.4 Transaction Processing
A transaction is a sequence of actions that must be executed atomically and isolated from other transactions.
The transaction manager ensures that transactions are processed correctly, even in cases of system failures.
1.2.5 The Query Processor
The query processor optimizes query performance through components like:
Query compiler: Translates queries into efficient internal forms.
Execution engine: Executes the chosen query plan.
1.3 Outline of Database-System Studies
The study of databases is divided into five parts:
Relational Database Modeling: Introduction to relational models, functional dependencies, normalization, and design tools (e.g., Entity-Relationship model).
Relational Database Programming: Focuses on query languages (primarily SQL), constraint specifications, and the integration of databases with host languages (e.g., JDBC).
Semistructured Data Modeling: Deals with XML and related standards, as well as querying languages like XPath and XQuery.
Database System Implementation: Covers storage management, query processing, transaction processing, and scheduling algorithms.
Modern Database Issues: Explores challenges related to search engines, information integration, data mining, and distributed data management.
1.4 References for Chapter 1
Includes foundational papers on relational databases, database research reports, and key sources on the theoretical foundations of database systems.
These notes summarize the key points from Chapter 1 and provide a foundational understanding of database systems and their evolution
Chapter 2: The Relational Model of Data
This chapter introduces the relational model, which is the most important data model in database systems. It presents key concepts such as relations (tables), attributes, tuples (rows), and various relational operations. The chapter also introduces SQL (Structured Query Language) and relational algebra.
2.1 Overview of Data Models
Data Model: A data model provides a structured way to describe data, including the structure, operations, and constraints.
Structure of Data: Data is represented in a structured form, commonly as relations (tables).
Operations on Data: These operations involve queries (retrieving data) and modifications (changing data).
Constraints on Data: Limits are placed on data, such as ensuring a value for an attribute falls within a specific range.
Types of Data Models:
Relational Model: The most widely used model where data is stored in tables (relations).
Semistructured Data Model: Commonly used for XML and graph-like structures.
2.2 Basics of the Relational Model
The relational model organizes data into relations (tables), which consist of rows (tuples) and columns (attributes).
Attributes: The named columns in a relation that describe the meaning of the data. Each attribute has an associated domain or data type (e.g.,
title,year,length,genre).Schema: A relation schema defines the structure of a table. For example, a movie table can be represented as:
Tuples: A tuple is a single row in the table, consisting of one value for each attribute. For example, a tuple in the
Moviestable might look like:Keys: A key is a set of attributes that uniquely identify tuples within a relation. No two tuples can have the same values for the key attributes.
2.3 Defining a Relation Schema in SQL
SQL (Structured Query Language) is the language used to define and manipulate data in relational databases.
CREATE TABLE: The SQL statement to define a table’s schema, specifying attributes and their types, default values, and constraints (e.g., keys).
Altering Schemas: With SQL, you can alter schemas by adding or removing attributes and modifying other properties with commands like
ALTERandDROP.
2.4 Relational Algebra
Relational Algebra: This is a formal language for manipulating relational data using operations such as union, intersection, selection, projection, joins, and others.
Projection: Produces a new relation with only specified columns from the original relation.
Selection: Produces a new relation containing only the tuples that satisfy a specified condition.
Joins: Combines two relations based on a specified condition.
Natural Join: Combines tuples from two relations that have matching values for the common attributes.
Theta-Join: Joins based on a condition involving comparison operators.
2.5 Constraints on Relations
Constraints help ensure the integrity and correctness of data.
Relational Algebra as a Constraint Language: Constraints can be expressed using relational algebra to restrict the data that can be stored in a relation.
Key Constraints: A key constraint ensures that no two tuples in a relation can have the same values for the key attributes.
Referential Integrity Constraints: These ensure that relationships between tables are consistent.
2.6 Summary
The relational model is the dominant model for databases. It uses relations (tables) to represent data.
SQL is the primary language for defining and manipulating data in relational databases.
Relational algebra provides a formal framework for querying and operating on data.
Constraints, such as keys and referential integrity, ensure data accuracy and consistency.
This chapter lays the groundwork for understanding relational databases, their structure, and the languages used to manage them, providing an essential foundation for further study in database systems.
Chapter 3: Design Theory for Relational Databases
This chapter focuses on how to design relational database schemas and improve them by eliminating redundancy and ensuring proper structure using theoretical foundations like functional dependencies (FDs) and normal forms.
3.1 Functional Dependencies
Functional Dependency (FD): A constraint between two sets of attributes in a relation. If two tuples agree on a set of attributes, they must also agree on another set of attributes.
Formal Definition: For attributes ( A_1, A_2, \dots, A_n ), if ( A_1 A_2 \dots A_n ) determines ( B_1 B_2 \dots B_m ), this means if two tuples have the same values for ( A_1, A_2, \dots, A_n ), they must also have the same values for ( B_1, B_2, \dots, B_m ).
Keys of Relations: A key is a minimal set of attributes that uniquely identifies a tuple in a relation.
3.2 Rules About Functional Dependencies
Reasoning about FDs: Involves determining if certain FDs logically follow from a set of given dependencies.
Splitting/Combining Rule: A complex FD can be split into simpler ones or vice versa.
Closure of Attributes: The set of all attributes functionally determined by a given set of attributes.
Trivial FDs: FDs where the right-hand side is a subset of the left-hand side are trivial.
Computing the Closure of Attributes: An algorithm is provided to compute the closure of a set of attributes under a set of FDs.
3.3 Design of Relational Database Schemas
Poor schema design can lead to redundancy and anomalies.
Anomalies:
Redundancy: Repetition of information (e.g., movie length repeated for each star in the movie).
Update Anomalies: Updating one occurrence of information but not another.
Deletion Anomalies: Deleting some information might lead to the unintentional loss of other information.
Decomposition of Relations: Break down relations into smaller, non-redundant relations.
Example: Decomposing the relation ( \text{Movies1} ) into ( \text{Movies2} ) and ( \text{Movies3} ) to avoid redundancy and anomalies.
3.4 Boyce-Codd Normal Form (BCNF)
BCNF: A relation is in BCNF if whenever a non-trivial FD ( A_1 A_2 \dots A_n \to B_1 B_2 \dots B_m ) holds, ( A_1 A_2 \dots A_n ) is a superkey.
Decomposition into BCNF: Decomposing a relation ensures it satisfies BCNF, eliminating redundancy.
3.5 Third Normal Form (3NF)
3NF: A relaxed form of BCNF, allowing a functional dependency ( X \to A ) even if ( X ) is not a superkey, as long as ( A ) is a member of some key.
Synthesis Algorithm for 3NF: This algorithm produces a decomposition that preserves dependencies and eliminates redundancy, ensuring a relation is in 3NF.
3.6 Multivalued Dependencies (MVDs)
Multivalued Dependencies (MVDs): When certain sets of attributes are independent of others within a relation.
Fourth Normal Form (4NF): A relation is in 4NF if it contains no non-trivial MVDs unless the left side of the MVD is a superkey.
Decomposition into 4NF: A relation can be decomposed into 4NF to remove redundancy due to MVDs.
3.7 The Chase Algorithm
Chase Test: A method to check if a decomposition has the lossless-join property (i.e., the original relation can be recovered from the decomposed relations).
The chase process involves applying FDs to infer new tuples and check if a decomposition is valid.
3.8 Summary
Functional Dependencies: Define relationships between attributes and help identify keys.
Boyce-Codd Normal Form (BCNF): Eliminates redundancy by ensuring non-trivial FDs are satisfied by superkeys.
Third Normal Form (3NF): A less restrictive normal form than BCNF, useful when preserving dependencies is critical.
Multivalued Dependencies and Fourth Normal Form (4NF): Address redundancy due to MVDs and ensure proper decomposition without information loss.
This chapter provides the foundation for designing efficient and reliable relational database schemas using normalization techniques. It emphasizes the need to decompose relations to avoid redundancy and anomalies, ensuring that databases are both optimized and maintainable .
Chapter 4: High-Level Database Models
This chapter introduces several high-level data modeling approaches used to design databases. These models simplify the preliminary design phase, which focuses on determining what data to store, how it is related, and what constraints (e.g., keys) apply. These high-level models are then converted into a relational schema for database implementation.
4.1 The Entity/Relationship (E/R) Model
The Entity-Relationship (E/R) model is one of the oldest and most widely used high-level data models. It provides a graphical way to represent the structure of data.
Entity Sets: An entity is an object or concept, and a collection of similar entities forms an entity set. In a movie database example,
Movies,Stars, andStudiosare entity sets.Attributes: Each entity has attributes, which describe the properties of that entity. For example, a
Moviesentity set may have attributes liketitle,year,length, andgenre.Relationships: These represent associations between entity sets. For example,
Stars-inis a relationship that connects movies with their stars, whileOwnsconnects movies to the studios that own them.
4.1.5 Instances of an E/R Diagram
An E/R diagram describes the structure of a database schema, but it does not represent the actual data itself. Each entity set in the diagram corresponds to a set of entities in the actual database. Similarly, a relationship in the E/R diagram corresponds to a set of related entities, called a relationship set.
4.1.6 Keys and Multiplicity
Keys: Every entity set must have a key — a unique identifier that distinguishes entities. In a
Moviesentity set, thetitleandyearattributes together might serve as a key.Multiplicity: Defines the number of entities that can participate in a relationship. Relationships can be one-to-one, one-to-many, or many-to-many.
4.2 Design Principles
Good database design principles help avoid redundancy and ensure the efficient management of data.
Avoid Redundancy: Redundant information leads to wasted space and can cause data inconsistency. For example, storing a movie’s length with each star of that movie creates unnecessary duplication.
Use of Relationships: Proper use of relationships between entity sets reduces redundancy. Instead of storing all details in one table, separating data into related entities (e.g., movies, stars, studios) improves the design.
4.6 The Unified Modeling Language (UML)
UML was originally developed for object-oriented software but is also used to design database schemas. It is similar to the E/R model but provides additional features, such as methods for entities and support for object hierarchies.
Classes: In UML, classes represent entity sets.
Associations: Relationships between classes are represented as associations, which may be many-to-one, many-to-many, or one-to-one.
Aggregation: Represents a "whole-part" relationship, where one class contains other classes.
4.9 Object Definition Language (ODL)
ODL is another high-level language used to model databases. It was created for object-oriented database systems and defines the structure of databases in terms of classes, attributes, methods, and relationships.
Keys in ODL: Keys are optional, and ODL uses object IDs (which are not visible to users) to uniquely identify objects, even if all attributes of two objects are identical.
Converting ODL to Relations: When converting an ODL class into a relational schema, special attention must be paid to attributes of complex types, which may result in an unnormalized relation that requires decomposition.
Summary of Chapter 4
Entity-Relationship Model: E/R diagrams use rectangles, diamonds, and ovals to represent entity sets, relationships, and attributes, respectively. Multiplicity and keys play a crucial role in relationships.
UML: UML is a graphical language used to design databases and software, extending the E/R model with support for object-oriented concepts like inheritance.
ODL: This language models object-oriented databases and allows relationships to be defined between objects. It can be converted to relational schemas.
This chapter provides foundational knowledge for database design using high-level models before converting them into relational models【19:0†source】【19:1†source】【19:3†source】【19:7†source】.
Chapter 5: Algebraic and Logical Query Languages
This chapter dives into query languages for relational databases. It extends the relational algebra discussed earlier and introduces a logic-based language called Datalog. The focus is on operations used in relational databases and how they are modeled mathematically and logically.
5.1 Relational Operations on Bags
Bags vs. Sets: Commercial DBMS typically handle bags (multisets), which allow duplicate tuples, rather than sets. This distinction alters how relational operations are defined.
Why Bags?: Operations on bags can be more efficient because duplicates do not need to be eliminated. For example:
Union: In bags, simply copy tuples without checking for duplicates.
Projection: No need to compare projected tuples to ensure uniqueness.
Operations on Bags:
Union, Intersection, and Difference: These basic operations can be extended to handle bags, with some algebraic laws (like the associative property) failing to hold.
Projection: Duplicate tuples are retained.
Join: Bags introduce complexity when joining relations, but joins are defined similarly to sets.
5.2 Extended Operators of Relational Algebra
In addition to basic operations, modern databases require extended operators to perform more complex queries, particularly in SQL. These extensions include:
Extended Projection: Allows computations and renaming of columns. You can project not only existing attributes but also new computed values.
Example: Compute an attribute like
salary + bonusand project it as a new attributetotal_compensation.
Grouping and Aggregation: Operators like
SUM,AVG,COUNT, etc., are essential for summarizing data. Grouping organizes data by one or more attributes before applying aggregation.Example: Grouping movies by genre and counting the number of movies in each genre.
Outer Joins: Outer joins return all tuples from one or both of the relations being joined, even if they don’t match. This is useful when you want to retain "dangling tuples" (i.e., tuples with no match in the other relation) by padding them with
NULLvalues.
5.3 A Logic for Relations (Datalog)
Datalog: A logical query language that expresses queries declaratively, unlike algebraic approaches, which specify how to compute the result. Datalog uses if-then rules to infer relationships between data.
Predicates and Atoms: A predicate represents a relation, and an atom is a predicate applied to arguments (e.g.,
R(x, y)whereRis a predicate andx,yare variables).Datalog Rules: A Datalog rule has a head (the result) and a body (conditions that must be true for the rule to apply). For example:
P(x, y) <- Q(x, z) AND R(z, y)means that if there are tuples(x, z)in relationQand(z, y)in relationR, then there must be a tuple(x, y)in relationP.
Recursive Queries: Datalog supports recursion, enabling complex queries like finding the transitive closure of a graph (e.g., determining all reachable nodes from a starting node).
5.4 Relational Algebra and Datalog
Equivalence: Core relational algebra can express all queries that are possible in non-recursive Datalog. Conversely, all relational algebra queries can be written as Datalog rules.
Recursive Queries in Datalog: Unlike relational algebra, Datalog supports recursion, enabling queries that require repetitive computations (like finding paths in a graph).
5.5 Summary of Chapter 5
Relations as Bags: DBMS often use bags, which allow duplicates. Bag operations differ from set operations but are more efficient for many practical queries.
Extended Relational Operators: Modern databases use extended operators such as aggregation, grouping, and outer joins, which go beyond the classical relational algebra.
Datalog: This logic-based language is more expressive for certain types of queries, especially recursive ones. It complements relational algebra, which is non-recursive.
This chapter presents an expanded set of tools for querying relational databases, building on the foundations of relational algebra and logic-based queries. The introduction of bags, extended operators, and the Datalog language provides the theoretical underpinnings for modern SQL operations【19:0†source】【19:4†source】【19:10†source】【19:16†source】.
Chapter 6: Simple Queries in SQL
This chapter introduces SQL and its capabilities to query and manipulate databases. The focus is on basic SQL operations, especially the SELECT-FROM-WHERE structure for retrieving and filtering data.
6.1 Simple Queries in SQL
Basic Query Structure: A query in SQL is typically made up of three main components:
SELECT: Specifies the attributes to retrieve.
FROM: Specifies the relation (table) from which to retrieve data.
WHERE: Specifies the condition to filter which tuples (rows) are retrieved.
Example Query: To retrieve all movies produced by Disney Studios in 1990:
Components Explained:
FROM clause: Specifies the relation, in this case,
Movies.WHERE clause: Filters tuples, here selecting only movies where
studioName = 'Disney'andyear = 1990.SELECT clause: Retrieves the entire tuple (
*means all attributes). The result is a relation of all tuples that match the condition.
6.1.1 Projection in SQL
The
SELECTclause allows projection by specifying which columns to return. For example:This query retrieves only the
titleandlengthof Disney movies from 1990.
6.1.2 Selection in SQL
Selection: The
WHEREclause allows complex conditions using comparison operators such as=,<>,<,>,<=,>=.Example: To find movies by MGM Studios produced after 1970 or shorter than 90 minutes:
6.1.3 String Comparisons
String Comparisons: SQL allows comparison of strings in the
WHEREclause. For instance, you can match movies with specific titles or studio names using=.
6.1.4 Pattern Matching in SQL
LIKE Operator: SQL provides pattern matching using the
LIKEoperator.%matches any sequence of characters._matches a single character.
Example: Find movies with "Star" in the title:
6.1.6 Null Values
Handling NULL Values: SQL treats NULL as a special value representing "unknown" or "missing" data. Comparisons with
NULLare neither true nor false, but instead returnUNKNOWN.
6.1.8 Ordering the Output
ORDER BY Clause: SQL allows ordering the results using the
ORDER BYclause.Example: Retrieve all movies ordered by their title in descending order:
6.2 Queries Involving More Than One Relation
SQL supports combining multiple relations through products and joins. Relations listed in the
FROMclause can be coupled, and theWHEREclause can specify conditions across those relations.
6.2.1 Products and Joins in SQL
Joins: SQL can join tables by listing them in the
FROMclause and specifying the relationship in theWHEREclause.Example: Find the name of the producer of Star Wars:
6.2.5 Union, Intersection, and Difference
SQL provides set operations like UNION, INTERSECT, and EXCEPT to combine results from multiple queries.
Example of Intersection: Find female movie stars who are also movie executives with a net worth over $10,000,000:
6.3 Subqueries
Subqueries: SQL supports queries within queries. A subquery can return a scalar value, a relation, or be used as a condition.
Example: Use a subquery to find movies produced by the same producer as Star Wars:
6.4 Full-Relation Operations
SQL supports operations that work on full relations, such as eliminating duplicates with DISTINCT, performing aggregations, and grouping data.
6.7 Summary of Chapter 6
SQL: The principal language for querying relational databases.
Basic Queries: Use the select-from-where structure for querying single or multiple tables.
Subqueries: Subqueries allow more complex querying, and SQL provides set operations and joins for combining results from different queries.
Chapter 6 provides an in-depth introduction to SQL querying, focusing on simple and multi-relation queries, subqueries, and operations on full relations. The chapter sets the stage for advanced SQL features like transactions, constraints, and optimization in later chapters【27:0†source】【27:9†source】【27:16†source】【27:13†source】.
Chapter 7: Constraints and Triggers
This chapter focuses on enforcing data integrity and automating actions within a database using constraints and triggers. It discusses how to ensure data correctness and trigger actions automatically in response to certain database events.
7.1 Keys and Foreign Keys
Keys: SQL allows the declaration of PRIMARY KEY or UNIQUE constraints to ensure that an attribute or combination of attributes uniquely identifies tuples.
Foreign Keys: These constraints enforce referential integrity by requiring that an attribute in one relation corresponds to a PRIMARY KEY or UNIQUE attribute in another relation.
Example: A Movie's producer certificate number (producerC#) must also exist in the MovieExec relation.
Foreign key constraints require:
The referenced attribute must be unique or a primary key.
The value in the foreign key must match a value in the referenced attribute of another relation.
7.2 Constraints on Attributes and Tuples
Not-Null Constraint: Ensures that a specific attribute cannot have
NULLvalues.Example: The
presC#(president certificate number) of aStudiomust not beNULL.
CHECK Constraints: SQL supports conditions that must be satisfied for an attribute or tuple to be valid. These conditions can involve comparisons, logical operations, and even subqueries.
Attribute-Based CHECK: Applies to individual attributes.
Tuple-Based CHECK: Applies to tuples as a whole.
7.3 Modification of Constraints
Naming Constraints: To modify or delete a constraint, it must have a name, specified using the CONSTRAINT keyword.
ALTER Constraints: SQL allows you to add or remove constraints from a table at any time using the
ALTER TABLEstatement. Constraints can be added, modified, or deleted as long as the existing data complies with the new rules.Example: Adding a primary key constraint:
7.4 Assertions
Assertions: These are database-wide constraints, more general than tuple or attribute constraints. An assertion is a boolean condition that must always hold true.
Example: A PC manufacturer must also make laptops with equal or greater processor speed.
Assertions are powerful but are difficult to implement efficiently because they must be checked every time any related table is modified.
7.5 Triggers
Triggers: Triggers are procedures that automatically execute in response to specific events (e.g., insertion, deletion, or update). A trigger can check a condition and take actions such as modifying data or preventing an operation.
Trigger Structure:
Event: The operation that activates the trigger (e.g.,
INSERT,UPDATE,DELETE).Condition: A condition to be checked (optional).
Action: The SQL statements to execute if the condition is true.
Types of Triggers:
Row-Level Trigger: Executes once for each row affected by the event.
Statement-Level Trigger: Executes once for the entire event, regardless of how many rows are affected.
Example: Prevent lowering the net worth of a movie executive:
7.6 Summary of Chapter 7
Referential Integrity Constraints: Ensures relationships between tables are maintained (e.g., foreign keys).
Attribute-Based and Tuple-Based Constraints: Used to enforce data correctness at the attribute or tuple level (e.g.,
CHECKconstraints).Assertions: Enforces general conditions across multiple tables.
Triggers: Automates responses to database events, such as insertion or update, allowing conditions to be checked and actions executed automatically.
This chapter explains how to maintain data integrity and consistency using SQL constraints and triggers, enhancing the reliability and security of a database【31:0†source】【31:5†source】【31:12†source】.
Chapter 8: Views and Indexes
This chapter covers two important features of SQL: views and indexes. Both play crucial roles in enhancing data retrieval and managing how data is represented and accessed.
8.1 Virtual Views
Virtual Views: A view is a virtual relation defined by a query. It is not stored physically in the database but is treated as if it were a table.
Example: A view of movies made by Paramount Studios can be defined as:
Querying Views: You can query views just like base tables. When a query references a view, the DBMS replaces the view with its definition and executes the query.
Renaming Attributes: Views can rename attributes during creation for better clarity. This is done by listing new names after the view name.
8.2 Modifying Views
Updatable Views: Some views are updatable, meaning you can perform
INSERT,UPDATE, andDELETEoperations on them. However, SQL restricts the circumstances under which views are updatable.Example: A view that selects attributes from a single base table is updatable. But if the view involves joins, aggregation, or certain subqueries, it is not.
Instead-Of Triggers: When direct updates to a view are not possible, Instead-Of triggers can be used. These triggers convert modifications on the view into modifications on the base tables.
8.3 Indexes in SQL
Indexes: An index is a data structure that improves the efficiency of data retrieval operations. It helps the DBMS locate tuples more quickly, especially when searching by key attributes.
Example: An index on the
yearattribute of theMoviesrelation can be created as:
Multi-Attribute Indexes: Indexes can be created on multiple attributes. The order of attributes in a multi-attribute index matters and should reflect how queries will use the index.
Example: An index on
titleandyearforMovies:
8.4 Selection of Indexes
Cost of Indexes: While indexes improve query performance, they add overhead to data modification operations (inserts, updates, deletes) because the index must also be updated.
Index Selection: Choosing which indexes to create is a trade-off. A good strategy is to focus on attributes frequently used in queries.
Automatic Index Selection: Some DBMS offer tools that analyze typical queries and suggest the best indexes.
8.5 Materialized Views
Materialized Views: Unlike virtual views, materialized views are stored physically. They are useful when a view is frequently queried, as storing the view's result improves query performance.
Maintaining Materialized Views: When the base tables of a materialized view are updated, the view must also be updated. This can be done incrementally to avoid recomputing the entire view.
Rewriting Queries Using Materialized Views: The query optimizer can rewrite queries to use materialized views when appropriate, improving performance.
8.6 Summary of Chapter 8
Virtual Views: Defined by queries, not stored physically but queried like base tables.
Updatable Views: Simple views may allow data modifications; otherwise, Instead-Of triggers can handle changes.
Indexes: Essential for efficient query performance, but choosing the right index requires balancing speed and update cost.
Materialized Views: Stored like tables to improve query performance, but they require careful maintenance to stay in sync with base tables.
This chapter provides essential knowledge on how to use views and indexes in SQL to improve data management and retrieval efficiency(ullman_the_complete_book)(ullman_the_complete_book)(ullman_the_complete_book).
Chapter 9: SQL in a Server Environment
This chapter explores how SQL fits into large-scale server environments and how it interacts with programming languages. It focuses on the three-tier architecture, the SQL environment, and techniques for embedding SQL in host languages like C and Java.
9.1 The Three-Tier Architecture
Three-tier architecture is the most common setup for large databases:
Web Servers: Manage client interactions (e.g., browsers accessing databases over the Internet).
Application Servers: Handle business logic, processing user requests and making decisions on what actions to take.
Database Servers: Execute database queries, store data, and serve data to the application servers.
Example: In a system like Amazon.com:
The web server processes user requests for a book.
The application server retrieves the book's data (title, author, price) from the database and formats it.
The database server handles SQL queries to fetch the required information.
9.2 The SQL Environment
SQL environments organize databases and their operations. This section outlines how elements like schemas, catalogs, and clusters are managed:
Schemas: Collections of database objects like tables, views, and triggers.
Catalogs: Group related schemas together.
Clusters: Larger collections of catalogs, determining the scope of queries a user can execute.
Connections and Sessions: A SQL connection links a client to a server, creating a session where multiple queries can be executed. SQL commands like
CONNECT,SET CONNECTION, andDISCONNECTmanage these interactions.
9.3 The SQL/Host-Language Interface
SQL is often embedded in programs written in general-purpose languages like C or Java to integrate database operations with application logic.
Impedance Mismatch: SQL is set-oriented, while most host languages are procedural. Bridging this gap requires mechanisms for handling results like relations, which are not naturally supported by conventional languages.
Shared Variables: These are used to move data between SQL and the host language. For example, variables in a C program can store values retrieved by an SQL query.
Cursors: A cursor is a SQL variable that lets a program fetch one row of a result set at a time. Cursors are important for handling large sets of data efficiently in host programs.
9.4 Stored Procedures and Persistent Stored Modules (PSM)
Stored Procedures: SQL allows users to create reusable, named sets of SQL commands stored in the database, which can be executed as needed.
Persistent Stored Modules (PSM): PSM is SQL’s version of stored procedures, adding control structures (e.g., loops, conditions) to SQL. PSM procedures can include SQL queries and logic.
9.5 Call-Level Interface (CLI)
The SQL/CLI (Call-Level Interface) is a library that allows C programs to interact with databases. CLI provides a set of functions to manage database connections, execute queries, and retrieve results.
JDBC (Java Database Connectivity) provides similar functionality for Java programs.
Example of establishing a JDBC connection in Java:
9.6 Java Database Connectivity (JDBC)
JDBC allows Java programs to access SQL databases using objects like Connection, Statement, and ResultSet. Methods like createStatement() and executeQuery() are used to manage SQL queries from Java applications.
9.7 PHP for Database Access
PHP is commonly used for embedding database access in HTML pages for web applications. PHP functions like query() and fetchRow() simplify interactions with SQL databases.
9.8 Summary of Chapter 9
Three-Tier Architectures: Databases often operate in a three-tier structure, consisting of web servers, application servers, and database servers.
SQL Client-Server Model: SQL clients connect to servers through sessions, allowing programs to perform queries and updates.
Embedded SQL: SQL can be embedded in host languages like C or Java using shared variables and cursors.
Call-Level Interfaces (CLI, JDBC): These allow programs to execute SQL queries and retrieve results using specialized libraries.
Stored Procedures and PHP: SQL supports stored procedures for reusability and allows integration with web-based languages like PHP.
This chapter outlines the various ways SQL integrates with server environments and programming languages to provide flexible and scalable data management(ullman_the_complete_book)(ullman_the_complete_book)(ullman_the_complete_book).
Chapter 10: Advanced Topics in Relational Databases
This chapter covers advanced relational database topics, including security, recursion in SQL, object-relational databases, OLAP, and more. It expands on SQL features and database structures critical for complex, large-scale database systems.
10.1 Security and User Authorization in SQL
Privileges in SQL: SQL provides several privileges for database elements, such as
SELECT,INSERT,DELETE,UPDATE,REFERENCES,TRIGGER, andEXECUTE. These privileges allow users to control access to different parts of the database, ensuring security.Example: A user with
SELECTprivilege can retrieve data, while a user withUPDATEprivilege can modify data.
Granting Privileges: Privileges can be granted to users or the special user
PUBLIC. When granted with theGRANT OPTION, recipients can pass on privileges to other users.Revoking Privileges: Privileges can be revoked, removing users' access rights. Grant Diagrams can be used to track who holds privileges and from whom they were granted.
10.2 Recursion in SQL
Recursive SQL Queries: SQL allows recursive definitions, making it possible to express queries that require recursion. Recursion is useful for tasks such as querying hierarchical data (e.g., organizational structures or networks).
Example: A recursive query to find all employees under a manager:
Monotonicity in Recursive Queries: Recursive queries in SQL must be monotone—adding new tuples should not result in tuples being deleted. Non-monotonic operations like
NOT EXISTSorCOUNTcannot be used in recursion.
10.3 The Object-Relational Model
Object-Relational Extensions: The object-relational model combines aspects of the relational model with object-oriented principles, enabling SQL to handle more complex data types.
Nested Relations: Attributes can be relations themselves, allowing for multi-level data structures.
References: Tuples in one relation can reference tuples in another, similar to pointers in object-oriented systems.
User-Defined Types (UDTs): SQL allows users to define custom types with attributes and methods. These types can be used in place of standard SQL types to represent complex data objects.
10.4 User-Defined Types in SQL
Defining UDTs: A User-Defined Type (UDT) is declared with attributes and methods, allowing custom behavior and more complex data structures.
Example: A
MovieTypecould include attributes liketitleandyear, as well as methods to manipulate these attributes.
Methods for UDTs: Methods can be defined within UDTs to allow for specific operations on data. These methods can return or modify attribute values, making UDTs more flexible than standard SQL types.
10.5 Operations on Object-Relational Data
Following References: SQL allows you to follow references between tuples using foreign keys or object-relational references. This is useful when navigating relationships between entities.
Accessing Components of UDTs: SQL supports functions to access and modify UDT attributes, allowing users to interact with complex data types easily.
Generator and Mutator Functions: Generator functions retrieve values from UDTs, while mutator functions modify those values.
10.6 On-Line Analytic Processing (OLAP)
OLAP Overview: OLAP (On-Line Analytical Processing) involves running complex queries over large datasets, often for decision-support applications. These queries typically involve aggregation and are computationally expensive.
Example: A retail company might use OLAP to identify trends in sales across different regions.
Data Warehousing: OLAP often operates on data warehouses, which are separate from the primary database and optimized for large-scale queries. These warehouses are updated periodically, allowing analysts to run queries on static data.
10.7 Data Cubes
Data Cubes: A data cube is a multi-dimensional array of data, where each dimension represents a different aspect of the data (e.g., time, product, location). Data cubes are used in OLAP to enable fast aggregation and analysis along various dimensions.
Cube Operator in SQL: SQL supports a specialized CUBE operator that pre-aggregates data along all possible combinations of dimensions.
Example: A query using the cube operator:
Rollup: The ROLLUP operator is a simplified version of the cube operator, which only aggregates along a hierarchical subset of dimensions.
10.8 Summary of Chapter 10
Security and Privileges: SQL systems manage user access through privileges, which control how users interact with database objects.
Recursion: Recursive queries in SQL allow for querying hierarchical and self-referential data structures, provided monotonicity is maintained.
Object-Relational Extensions: SQL can be extended with object-oriented features, including UDTs, references, and methods, to handle more complex data.
OLAP and Data Cubes: OLAP queries benefit from the data cube structure, which allows for efficient aggregation across multiple dimensions.
This chapter provides essential tools and techniques for managing and analyzing complex data in modern relational databases(ullman_the_complete_book)(ullman_the_complete_book)(ullman_the_complete_book)(ullman_the_complete_book).
Chapter 11: The Semistructured-Data Model
11.1 Semistructured Data
Motivation for the Semistructured-Data Model: Traditional database systems rely on structured data models like the relational model, where the schema is rigidly predefined. However, some data sources do not fit neatly into such structured formats, which motivates the need for a semistructured data model. In this model, data doesn't require a fixed schema and is represented more flexibly.
Semistructured Data Representation: The model uses a graph structure, where nodes represent objects or values, and edges represent relationships or attributes between those objects. This allows the data to represent complex, hierarchical, and flexible relationships.
Information Integration via Semistructured Data: Semistructured data models are useful in scenarios where data needs to be integrated from different sources with varying formats. Since it doesn't require a rigid schema, it facilitates smoother integration of heterogeneous datasets.
11.2 XML (Extensible Markup Language)
XML Overview: XML is a widely used standard for representing semistructured data in a linear format. It organizes data hierarchically using elements, which are delimited by tags.
XML Elements: An XML element starts with an opening tag (
<TagName>) and ends with a closing tag (</TagName>). The content between these tags can either be text or sub-elements.XML Attributes: Elements can also include attributes, which provide additional information about the element. Attributes are included inside the opening tag as key-value pairs (e.g.,
<TagName attribute="value">).Document Type Definitions (DTD): DTDs offer a rudimentary schema for XML documents. They define what elements and attributes an XML document can contain, as well as rules for their organization and frequency. This provides some level of validation for XML documents, ensuring they conform to a certain structure.
11.3 Document Type Definitions (DTD)
DTD Structure: A DTD defines the legal building blocks of an XML document. It consists of element declarations and their valid sub-elements or attributes. The general format is
<!ELEMENT ElementName (SubElements)>.Identifiers and References in DTDs: DTDs can declare attributes as IDs and references to create relationships between different elements, allowing XML to represent more complex structures such as graphs instead of just trees.
11.4 XML Schema
XML Schema Overview: XML Schema is another way to define the structure of XML documents. Unlike DTDs, XML Schemas are written in XML itself and offer more flexibility and detail in defining data types and structure.
Simple and Complex Types: XML Schema allows the definition of simple types (e.g., strings, integers) and complex types, which are composed of other elements or attributes. Complex types can specify how many times an element can appear and in what order.
Keys and Foreign Keys: Similar to relational databases, XML Schema allows defining keys to ensure unique values and foreign keys to represent references between elements. This helps to maintain integrity within XML documents.
11.5 Summary
The semistructured-data model represents data as a graph, enabling flexibility and supporting integration across various data sources.
XML provides a way to represent semistructured data with elements, attributes, and optional schema definitions via DTDs or XML Schema.
XML Schema offers a more flexible and detailed method to define the structure of XML documents compared to DTDs, including support for complex types, keys, and constraints【7:0†source】【7:9†source】【7:10†source】【7:11†source】【7:19†source】.
Chapter 12: Programming Languages for XML
12.1 XPath
XPath Overview: XPath is a simple language designed for querying and navigating XML data. It allows users to specify paths through the XML document's hierarchy, starting from the root and traversing through elements, attributes, and other nodes.
XPath Data Model: XPath operates on sequences of items, which can either be primitive values (such as strings or numbers) or elements (opening tags, content, and closing tags).
Axes in XPath: XPath supports different navigation "axes" beyond just child elements. These include accessing any descendants, parents, and siblings, giving more flexibility in querying.
XPath Conditions: XPath allows conditions (boolean expressions) to filter results. These conditions appear in square brackets (
[]) and can be applied at any point in the path.
12.2 XQuery
XQuery Overview: XQuery is a more advanced query language for XML documents, building on the same data model as XPath but adding more powerful querying capabilities. It’s functional in nature, akin to SQL for XML.
FLWR Expressions: Many XQuery queries follow the FLWR (For, Let, Where, Return) format.
For iterates over a sequence.
Let binds variables to values.
Where adds conditions.
Return specifies the output of the query.
Comparison Operators: XQuery uses comparison operators (
=,<, etc.), but when applied to sequences of items, they carry a "there exists" interpretation. Operators likelt(less than) ensure single-item comparisons.Other XQuery Features: XQuery supports operations similar to SQL, including quantification (
everyandsome), aggregation, duplicate elimination, and result sorting.
12.3 Extensible Stylesheet Language Transformations (XSLT)
XSLT Overview: XSLT is primarily used to transform XML documents into other formats (like HTML or other XML structures). It is itself an XML-based language, with programs structured as XML documents.
Templates in XSLT: The core of XSLT is the template, which defines rules for matching specific XML elements. Matched elements are transformed into new structures defined within the template. Templates can call other templates, enabling recursive transformations.
Programming Constructs in XSLT: XSLT includes constructs like loops (
for-each) and conditionals (if,choose) to add logic to transformations. These make XSLT functionally similar to imperative programming languages, allowing for complex transformations of XML data.
12.4 Summary
XPath: Allows navigating and querying XML documents through paths that can access elements and attributes, following different axes, and applying conditions to refine results.
XQuery: A more powerful XML query language, based on the same data model as XPath, with capabilities for iteration, conditionals, sorting, and result manipulation.
XSLT: A transformation language for XML documents, capable of converting XML into different formats, with powerful templating, looping, and conditional logic【7:0†source】【7:3†source】【7:5†source】【7:11†source】.
Chapter 13: Secondary Storage Management
13.1 The Memory Hierarchy
Memory Hierarchy Levels: The computer system consists of multiple memory levels, each with different capacities, access speeds, and costs. These include:
Cache: Extremely fast but small memory, located on or near the processor.
Main Memory: Larger than cache but slower; used for actively processed data.
Secondary Storage (Disks): Magnetic disks provide vast storage but are much slower than cache or main memory. Data is transferred from disks to lower levels of memory for processing.
13.2 Disks
Mechanics of Disks: Data on magnetic disks is stored in tracks, sectors, and cylinders. The disk heads move over the disk surface to read/write data, which requires seek time, rotational latency, and data transfer time.
Disk Access Characteristics: Disk access time is a critical factor influenced by seek time (moving the head to the correct track), rotational latency (waiting for the sector to appear under the head), and transfer time (time to move the data).
Disk Controller: Manages the interaction between the computer and disk, controls disk head movement, and ensures proper scheduling of read/write operations.
13.3 Accelerating Access to Secondary Storage
I/O Model of Computation: This model focuses on minimizing disk accesses to improve computation efficiency.
Organizing Data by Cylinders: Storing related data in the same cylinder or nearby tracks minimizes seek time.
Using Multiple Disks: Data can be spread across multiple disks to allow parallel access (striping) or mirrored for redundancy.
Disk Scheduling and the Elevator Algorithm: Disk requests are queued and handled in an optimal order to reduce head movement and speed up access times.
13.4 Disk Failures
Types of Failures: Disks can experience intermittent failures (recoverable by retrying the operation), permanent failures (irreversible data corruption), and disk crashes (complete loss of readability).
Checksums: Data integrity can be ensured using checksums, which help detect errors.
Stable Storage: Using redundant copies of data helps guard against permanent sector failures.
RAID: Various RAID levels (e.g., RAID 4, RAID 5) provide fault tolerance through parity blocks, enabling data recovery even after disk failures.
13.5 Arranging Data on Disk
Fixed-Length Records: These are easy to manage, but inefficient in storage. They are often packed into blocks, with headers indicating how records are organized.
Variable-Length Data: Special mechanisms are required to manage variable-length records, which can cause fragmentation in storage blocks.
BLOBs: Binary Large Objects (e.g., images, videos) are stored across multiple blocks and may require specialized techniques like striping to handle large data.
13.6 Representing Block and Record Addresses
Logical and Physical Addresses: Data can be accessed using physical addresses (device, cylinder, track, and sector) or logical addresses, which are mapped to physical addresses.
Pointer Swizzling: When disk blocks are brought into memory, disk addresses need to be converted (swizzled) to memory pointers for efficient access.
13.7 Variable-Length Data and Records
Handling Variable-Length Fields: Methods like separating fields or storing pointers to variable fields help manage variable-length data, which adds complexity to storage management.
BLOBs and Column Stores: Column stores are designed to handle large, variable-length objects like images or videos.
13.8 Record Modifications
Insertion, Deletion, and Updates: These operations must be managed carefully to avoid fragmentation. Deletion, in particular, can leave "tombstones" (placeholders for removed records), and updates may involve moving records if their size changes.
13.9 Summary of Chapter 13
This chapter covers the fundamentals of secondary storage, focusing on disk mechanics, access methods, and failure management. Efficient data storage and retrieval techniques, including RAID and pointer swizzling, are essential to managing large-scale database systems effectively【16:0†source】【16:3†source】【16:7†source】【16:11†source】【16:14†source】.
Chapter 14: Index Structures
14.1 Index-Structure Basics
Sequential Files: Sequential files are organized by sorting the data based on a specific key, making searching faster. They typically have an index to speed up searches.
Dense and Sparse Indexes:
Dense Indexes have a key-pointer pair for every record in the data file.
Sparse Indexes store a key-pointer pair for each block of data, reducing the size of the index but slightly increasing search time within a block.
Multilevel Indexes: When an index becomes large, a second index is built on top of the first. This multilevel structure allows efficient searching even for large datasets.
Secondary Indexes: These indexes are built on a non-primary key, allowing quick searches by other fields even when the file is not sorted by that key.
Inverted Indexes: Commonly used in document retrieval, inverted indexes map words to the documents in which they appear.
14.2 B-Trees
B-Tree Structure: B-Trees are a self-balancing tree data structure that maintain sorted data and allow for searches, sequential access, insertions, and deletions in logarithmic time.
Each node in a B-Tree contains multiple keys and pointers to its child nodes.
Keys in the parent nodes separate the ranges of values stored in the child nodes, allowing for efficient searching.
B-Tree Operations:
Insertion into a B-tree may cause a node to split if it exceeds the allowed number of keys.
Deletion may require merging or redistributing keys to maintain the minimum occupancy condition.
Applications: B-Trees are commonly used for databases and file systems due to their efficiency in both read and write operations.
14.3 Hash Tables
Secondary-Storage Hash Tables: Hashing can be used to map search keys to buckets, allowing quick access to records.
Extensible Hashing: This method allows dynamic growth of hash tables. When a bucket overflows, the table grows by doubling the number of buckets, distributing the records across the new table.
Linear Hashing: Instead of doubling the table size when needed, linear hashing increases the number of buckets incrementally, leading to a more gradual growth of the table.
14.4 Multidimensional Indexes
Applications: Multidimensional indexes are used to handle queries with multiple conditions or dimensions, such as in geographic or scientific databases.
Range Queries: These queries find all records within a certain range in each dimension.
Nearest-Neighbor Queries: These queries retrieve the record closest to a given point based on multidimensional distances.
14.5 Hash Structures for Multidimensional Data
Grid Files: Grid files are multidimensional hash structures that divide each dimension into a grid, allowing efficient range queries.
Partitioned Hash Functions: These functions are used to split the data into manageable parts, helping with query performance.
14.6 Tree Structures for Multidimensional Data
kd-Trees: kd-trees partition space based on the value of one dimension at a time, creating a binary tree. Each node represents a partition, and points in the same region are stored in the same subtree.
R-Trees: These are more complex, storing bounding rectangles instead of points. They are used in geographic databases to manage spatial data, allowing for efficient region and range queries.
14.7 Bitmap Indexes
Bitmap Indexes: These indexes use bitmaps to represent the presence or absence of values in records. They are efficient for queries on fields with a small number of distinct values.
Compressed Bitmaps: Compression techniques like run-length encoding can make bitmap indexes more space-efficient, especially for sparse datasets.
14.8 Summary
Index structures are essential for efficient querying and retrieval in large databases.
B-Trees and Hash Tables are effective for single-dimensional indexing.
Multidimensional Indexes like kd-trees and R-trees are used for more complex queries involving multiple attributes.
Bitmap Indexes are efficient for certain types of queries, especially in read-heavy applications where field values are repetitive【16:0†source】【16:15†source】【16:17†source】.
Chapter 15: Query Execution
15.1 Introduction to Physical-Query-Plan Operators
Query Execution: The process where SQL queries and data-modification commands are transformed into a sequence of database operations.
Physical Operators: These are the mechanisms that implement the operations of extended relational algebra (e.g., scanning, sorting, hashing).
15.1.1 Scanning Tables
Table-Scan: Reads each block of a relation to retrieve tuples.
Index-Scan: Uses an index to locate tuples based on a specific attribute.
Sort-Scan: Produces tuples in sorted order, useful for certain types of queries.
15.1.4 Parameters for Measuring Costs
Cost Model: Typically, disk I/O is the primary factor in measuring the cost of executing operations. The model assumes that reading arguments from disk dominates the overall execution time.
15.2 One-Pass Algorithms
One-Pass Algorithms: Used when one argument of a relational operation fits in main memory. These algorithms process the smaller relation entirely in memory while reading the larger relation block-by-block from disk.
Nested-Loop Join: A simple algorithm that repeatedly loads blocks of the smaller relation and compares them to the larger relation, block by block.
15.4 Two-Pass Algorithms Based on Sorting
Two-Phase Multiway Merge-Sort: The relation is divided into sorted sublists that fit in main memory. These sorted lists are then merged to produce the final sorted result.
Sorting-Based Join: Join operations are executed by first sorting both relations and then merging them on the join key.
15.5 Two-Pass Algorithms Based on Hashing
Hash-Based Algorithms: These algorithms use a hash function to partition relations into smaller buckets that can fit into main memory. The operation (e.g., join, aggregation) is then performed on the individual buckets.
Hybrid Hash Join: Combines hash-based and sorting techniques, using memory efficiently by avoiding re-reading data where possible.
15.6 Iterators for Implementation of Physical Operators
Iterators: A mechanism where a query operation is performed using three methods:
open,next, andclose. This allows query operations to be "pipelined," minimizing memory usage by processing one tuple at a time.
15.9 Summary of Chapter 15
Query processing involves compiling queries into logical and physical plans and executing them using various relational operators.
Different algorithms like one-pass, sort-based, and hash-based are used depending on the size of the data and available memory【25:0†source】【25:5†source】【25:7†source】【25:9†source】【25:19†source】.
Chapter 16: The Query Compiler
16.1 Parsing and Preprocessing
Parsing Queries: The query compiler's first task is to parse SQL queries into a format that can be understood by the DBMS. This involves syntax analysis to create a parse tree, which represents the structure of the query.
Preprocessing: This step involves optimizing queries involving views by replacing view references with their definitions and eliminating unnecessary subqueries.
16.2 Algebraic Laws for Query Optimization
Commutative and Associative Laws: These laws allow changing the order of operations in a query. For instance, the order of joins or selections can often be altered without changing the result, but improving performance.
Selection and Projection Pushdown: The optimizer attempts to push selection and projection operations down in the query plan so that less data is handled by expensive operations like joins.
Join Optimization: Joins are expensive, so the optimizer tries to reorder them or use indexes to minimize the cost of processing.
16.3 Logical Query Plans
From Parse Tree to Logical Plan: After parsing, the query is converted into a logical query plan, typically based on relational algebra. The optimizer then tries to apply algebraic transformations to improve the plan.
Handling Subqueries: Subqueries are flattened or transformed into equivalent join or grouping operations, simplifying the execution.
16.4 Estimating the Cost of Operations
Cost Estimation: The optimizer estimates the size of intermediate results and the costs of operations like selections, joins, and projections. This estimation guides the optimizer in choosing the best execution plan.
Joins and Projections: Techniques are used to estimate the size of relations after projections and selections, based on factors like the number of distinct values in columns and the selectivity of conditions.
16.5 Plan Selection
Cost-Based Optimization: The query optimizer evaluates multiple query plans using a cost model and selects the plan with the lowest estimated cost. This cost is usually dominated by disk I/O but also considers CPU and memory usage.
16.6 Choosing Join Orders
Join Trees: A join tree represents the order in which relations are joined. The optimizer explores different tree shapes (e.g., left-deep, bushy) to find the most efficient order.
Dynamic Programming for Join Ordering: Dynamic programming is used to systematically explore different join orders, caching intermediate results to avoid redundant calculations.
16.7 Completing the Physical Query Plan
Physical Operators: Once the logical query plan is optimized, the optimizer selects physical operators (like nested-loop joins, hash joins) based on the available indexes and memory.
Pipelining vs. Materialization: The optimizer decides whether intermediate results should be pipelined between operators (to avoid storing them on disk) or materialized (stored for reuse).
16.8 Summary
The query compiler transforms high-level SQL queries into efficient physical execution plans using algebraic optimization techniques, cost estimation, and dynamic programming to choose the optimal join orders and physical operators【29:0†source】【29:9†source】【29:15†source】.
Chapter 17: Coping With System Failures
17.1 Issues and Models for Resilient Operation
System Failures: A database must be resilient to system failures (e.g., crashes) to protect data integrity. Failures occur in different forms, such as hardware faults or power losses, which lead to data being lost or corrupted.
Transactions: Transactions must either be completed entirely or not at all (atomicity). They are designed to move the database from one consistent state to another.
17.2 Undo Logging
Undo Logging Basics: The primary concept behind undo logging is to record every change made by a transaction, so that if a failure occurs, the changes can be undone. Each change is written to the log before it is applied to the database. This ensures that the system can restore the database to its original state after an error.
Log Records:
: Marks the beginning of transaction T.
: Indicates that T has completed successfully, and its changes should persist.
: Indicates that T has failed, and all changes made by it must be undone.
Checkpointing: Used to prevent the log from growing too large, checkpoints allow the system to save its state and discard old log entries.
17.3 Redo Logging
Redo Logging: Unlike undo logging, redo logging writes only the new value of a data item. Changes are applied after the transaction has committed, ensuring that only completed transactions are replayed in case of a failure.
17.4 Undo/Redo Logging
Combining Undo and Redo: In this approach, both old and new values are logged. This hybrid model provides greater flexibility, allowing both committed changes to be redone and uncommitted ones to be undone during recovery.
17.5 Protecting Against Media Failures
Archiving: Media failures, such as disk crashes, can result in data loss. Archiving is the process of creating backups (full or incremental dumps) to reconstruct the database from the most recent saved state.
Recovery Using Archive and Log: If a media failure occurs, the system restores the database using the archive and then applies any changes from the log that occurred after the archive was created.
17.6 Summary
Transaction Management: Focuses on two tasks—ensuring recoverability via logging and maintaining correct concurrent behavior through the scheduler.
Logging Types: The three logging methods (undo, redo, and undo/redo) each have specific rules for handling database changes.
Recovery: The recovery process uses logs to bring the database back to a consistent state after a failure【29:0†source】【29:1†source】【29:7†source】【29:9†source】【29:19†source】.
Chapter 18: Concurrency Control
18.1 Serial and Serializable Schedules
Serial Schedules: Transactions execute one at a time, fully completing before another starts. This is a simple but impractical model due to efficiency concerns.
Serializable Schedules: Interleaved transaction execution is allowed, provided the outcome is the same as some serial execution.
18.2 Conflict-Serializability
Conflicts in Actions: Two actions conflict if they access the same data item, and at least one is a write. If conflicts can be reordered to produce a serial schedule, the schedule is conflict-serializable.
Precedence Graph: This graph represents transactions as nodes and conflicting actions as directed edges. If the graph has no cycles, the schedule is conflict-serializable.
18.3 Enforcing Serializability by Locks
Locks: Transactions lock database elements to ensure no other transactions access them concurrently, ensuring serializability.
Two-Phase Locking (2PL):
Growing Phase: Transactions acquire locks.
Shrinking Phase: Transactions release locks. This ensures conflict-serializability by preventing cycles in the precedence graph.
18.4 Locking Systems With Several Lock Modes
Shared and Exclusive Locks: Shared locks allow reading of data by multiple transactions, while exclusive locks prevent any other transaction from accessing the data.
Increment Locks: Used for operations that modify data by a small amount without fully locking the element, improving concurrency for certain use cases.
18.6 Hierarchies of Database Elements
Granularity of Locks: Locks can be applied at various granularities (e.g., rows, blocks, or entire tables). Using larger-granularity locks reduces the complexity but lowers concurrency, while smaller-granularity locks increase concurrency but add overhead.
18.7 Tree Protocol for Concurrency Control
Tree Protocol: Used for data structures like B-trees. Transactions must lock nodes starting from the root and can release locks on parent nodes once child nodes are locked, ensuring serializability without using two-phase locking.
18.8 Concurrency Control by Timestamps
Timestamps: Each transaction is assigned a unique timestamp. Transactions are ordered by these timestamps, and conflicts are resolved by rolling back transactions with later timestamps if necessary.
Multiversion Concurrency Control: Multiple versions of a data item are kept, allowing read-only transactions to access older versions without causing conflicts.
18.9 Concurrency Control by Validation
Optimistic Concurrency Control: Transactions execute without locks. Before committing, they are validated to ensure no conflicts. If a conflict is found, the transaction is rolled back.
18.10 Summary of Chapter 18
Various techniques like two-phase locking, timestamp-based scheduling, and validation ensure that concurrently running transactions do not lead to inconsistent database states.
These techniques balance the need for serializability with the need to maximize concurrency【16:0†source】【16:7†source】【16:8†source】【16:9†source】.
Chapter 19: More About Transaction Management
19.1 Serializability and Recoverability
Dirty Data Problem: Data written by a transaction that hasn’t committed yet is considered "dirty." If the transaction aborts, this dirty data may be invalid, causing issues if other transactions have used it.
Cascading Rollbacks: If a transaction reads dirty data from an uncommitted transaction that later aborts, it may need to be rolled back, causing a series of cascading rollbacks.
Recoverable Schedules: A schedule is recoverable if transactions commit only after ensuring they won’t need to roll back due to reading dirty data.
Schedules That Avoid Cascading Rollbacks: These schedules ensure that a transaction only reads committed data, thereby avoiding cascading rollbacks.
Group Commit: A technique that batches multiple commit operations together, improving performance by reducing the number of disk writes.
19.2 Deadlocks
Deadlock Detection by Timeout: A timeout mechanism helps detect deadlocks by assuming that if a transaction is waiting too long, it might be involved in a deadlock.
Waits-For Graph: Transactions are represented as nodes in a graph, with edges showing which transaction is waiting for a resource held by another. Deadlocks are detected when cycles exist in this graph.
Deadlock Prevention by Ordering: Resources are ordered, and transactions must acquire them in a predefined order to prevent deadlocks.
Timestamp-Based Deadlock Detection: Transactions are assigned timestamps, and older transactions are allowed to wait while newer ones are aborted to avoid deadlocks.
19.3 Long-Duration Transactions
Sagas: A saga is a sequence of multiple actions that form a long-duration transaction. Each action has a compensating transaction that undoes its effects if the saga needs to be aborted.
Compensating Transactions: These transactions are used to undo the effects of previously committed actions in case a long-duration transaction (saga) fails.
19.4 Summary of Chapter 19
Dirty Data: Data written by uncommitted transactions poses risks.
Deadlocks: Managed using wait-for graphs, timeouts, and timestamp-based methods.
Long-Duration Transactions (Sagas): Compensating transactions are key to managing sagas, ensuring that even partial failures leave the database in a consistent state【16:0†source】【16:9†source】【16:10†source】【16:15†source】.
Chapter 20: Parallel and Distributed Databases
20.1 Parallel Algorithms on Relations
Parallel Architectures:
Shared-Memory Machines: All processors can access a global memory space. Though they have local caches, processors can access memory from other processors if needed.
Shared-Disk Machines: Each processor has its own local memory, but all processors can access a shared set of disks.
Shared-Nothing Machines: Each processor has its own memory and disks. This architecture is most commonly used for parallel databases due to its cost-effectiveness.
Tuple-at-a-Time Operations:
Operations like selection can be performed efficiently in parallel by distributing data across processors. Each processor works independently on its subset of data.
Full-Relation Operations:
Hashing for Distribution: To perform operations like join, union, or intersection, tuples are hashed to processors based on join attributes. Each processor performs the operation locally.
Parallel Aggregation: Grouping and aggregation operations are distributed by hashing tuples based on grouping attributes.
20.2 The Map-Reduce Framework
Storage Model:
The map-reduce model is designed for shared-nothing, massively parallel architectures. Data is stored in large files, and processors work independently on chunks of data.
Map and Reduce Functions:
The map function processes individual chunks of data and produces intermediate key-value pairs.
The reduce function collects all pairs associated with the same key and combines them into a final result.
Example:
Inverted Index Construction: Each map task outputs pairs (word, document) for every word in a document. Reduce tasks aggregate these pairs to produce a list of documents for each word.
20.3 Distributed Databases
Distribution of Data:
Organizations with multiple locations may distribute data across various sites. This can involve:
Horizontal Partitioning: Dividing rows of a relation across sites (e.g., each branch of a bank stores account data locally).
Vertical Partitioning: Dividing columns of a relation across sites, necessitating joins to retrieve complete data.
Distributed Transactions:
Transactions may involve multiple sites, making atomicity and serializability challenging.
Two-Phase Commit ensures that all sites involved in a transaction either commit or abort together.
Data Replication:
Data can be replicated across multiple sites to increase fault tolerance and improve query performance.
Challenges include keeping replicas consistent and deciding where and how many copies to maintain.
20.4 Distributed Query Processing
Semijoins for Distributed Joins:
To reduce communication costs, semijoins are used to minimize the amount of data sent across sites during a join.
Acyclic Hypergraphs:
The join of multiple relations can be represented as a hypergraph. Acyclic hypergraphs allow for efficient join processing using full reducers, which eliminate dangling tuples through semijoins.
20.5 Distributed Commit
Two-Phase Commit Protocol:
In the first phase, all sites vote on whether to commit or abort a transaction.
In the second phase, the coordinator instructs all sites to either commit or abort, ensuring atomicity even in the presence of failures.
20.6 Distributed Locking
Global Locks:
When elements are replicated across multiple sites, acquiring global locks requires coordination among replicas.
Majority Locking: A read or write lock is obtained on the majority of replicas to enforce consistency.
20.7 Peer-to-Peer Networks and Distributed Hashing
Distributed Hash Tables (DHTs):
DHTs are used in peer-to-peer networks to store key-value pairs across many independent nodes, ensuring efficient lookup without relying on a single node.
Chord Circles:
A distributed hashing algorithm that maps both node IDs and keys to a circular address space, ensuring efficient key lookup in logarithmic time using finger tables.
20.8 Summary of Chapter 20
Parallel Machines: Shared-nothing is the most cost-effective architecture for parallel database systems.
Map-Reduce: A powerful framework for parallel processing on large datasets, especially useful for tasks like indexing and aggregation.
Distributed Databases: Offer scalability and resilience but require complex protocols for transaction management, query processing, and locking.
This chapter focuses on the design and implementation of parallel and distributed databases, exploring how large-scale computations and database operations can be efficiently distributed across multiple processors or sites.
Chapter 21: Information Integration
21.1 Introduction to Information Integration
Why Information Integration?
Information integration is essential when combining data from multiple heterogeneous sources to provide a unified view for analysis or applications.
Problems arise due to differences in data formats, query languages, and schemas across various data sources.
The Heterogeneity Problem:
Data sources may differ in their structure (e.g., relational vs. XML databases), syntax, and semantics. Integration must overcome these differences.
21.2 Modes of Information Integration
Federated Database Systems:
A federated database system provides an integrated view of multiple databases while preserving their autonomy. Each database operates independently and provides interfaces for integration.
Data Warehouses:
Data from different sources is extracted, transformed, and loaded (ETL) into a centralized repository. Data warehouses support complex queries but operate on periodically updated snapshots of the data.
Mediators:
Mediators provide a virtual integration approach by translating queries from the global schema into queries against local data sources. They don’t store data but facilitate real-time query translation and result aggregation.
21.3 Wrappers in Mediator-Based Systems
Query Templates:
Wrappers translate queries to the specific language or API of a local source. Templates are used to define common query patterns that the mediator can transform for execution.
Wrapper Generators:
Automated tools that simplify the creation of wrappers for different data sources by generating the necessary query translations and communication protocols.
21.4 Capability-Based Optimization
Source Capabilities:
Some data sources have limitations, such as supporting only certain types of queries. Mediators need to be aware of these capabilities and optimize queries accordingly.
Capability-Based Query-Plan Selection:
The mediator selects the best execution plan for a query based on the capabilities of the data sources involved, ensuring efficient execution.
21.5 Optimizing Mediator Queries
The Chain Algorithm:
This algorithm optimizes mediator queries by ordering subgoals and evaluating them incrementally to reduce the overall cost of query execution.
Incorporating Union Views:
Mediators can handle queries that span across multiple views, using union operations to combine results from different data sources.
21.6 Local-as-View Mediators
Local-as-View (LAV) Approach:
In LAV mediators, each data source is described as a view of the global schema. The mediator reformulates user queries to match the available views and data sources.
Containment of Conjunctive Queries:
Query containment is used to determine if one query can be rewritten to match another, which helps the mediator in answering queries by finding suitable data sources.
21.7 Entity Resolution
Problem:
Identifying records that refer to the same real-world entity, despite variations in their representation (e.g., different spellings of names or addresses).
ICAR Similarity and Merge Functions:
Functions that are idempotent, commutative, associative, and representable help efficiently resolve entities. The R-Swoosh Algorithm is an efficient method to group and merge similar records.
21.8 Summary
Information Integration:
Involves combining data from heterogeneous sources, with different methods like federated databases, data warehouses, and mediators offering various solutions.
Optimization Techniques:
Query optimization techniques, including capability-based query planning and entity resolution, are essential for efficient and accurate data integration .
Chapter 22: Data Mining
22.1 Frequent-Itemset Mining
Market-Basket Model:
Market Basket Data: In this model, data consists of baskets (e.g., customers’ purchases at a store). Each basket contains a subset of items from a large set.
Frequent Itemsets: An important task is identifying sets of items that often appear together in many baskets. For example, knowing that customers frequently buy hot dogs and mustard together can help with product placement.
Association Rules: Once frequent itemsets are found, association rules can be derived, indicating that if one item or set of items is bought, another is likely to be bought as well.
A-Priori Algorithm:
Basic Idea: This algorithm identifies frequent itemsets by using the fact that if an itemset is frequent, all its subsets must also be frequent.
Candidate Generation and Pruning: Itemsets are generated in passes. In each pass, the algorithm generates candidate itemsets (based on frequent itemsets from the previous pass) and counts their occurrences to identify which are frequent.
22.2 Algorithms for Finding Frequent Itemsets
PCY Algorithm:
Improves on A-Priori by reducing the memory needed to store candidates. It uses a hash-based approach to reduce the number of item pairs that need to be counted on the second pass.
Multistage Algorithm:
This extends PCY by using multiple passes, each time hashing pairs with different hash functions, thus eliminating more non-frequent pairs with each pass.
22.3 Finding Similar Items
Jaccard Similarity:
Used to measure how similar two sets are by computing the ratio of the intersection to the union of the sets. This is useful for finding similar items, such as books bought by the same customers.
Minhashing:
This technique compresses sets into small signatures that approximate their similarity. It provides an efficient way to estimate Jaccard similarity between sets without directly comparing all elements.
Locality-Sensitive Hashing (LSH):
LSH is a technique to reduce the number of pairwise comparisons needed to find similar items. It works by hashing sets in a way that ensures similar sets are likely to hash to the same bucket.
22.5 Clustering
Agglomerative Clustering:
A hierarchical method where each point starts as its own cluster, and clusters are merged based on proximity.
BFR Algorithm:
A version of k-means designed for very large datasets that don't fit in memory. It compresses data points into clusters represented by summary statistics (e.g., centroid, sum of squared distances) and processes one memory-full of data at a time.
22.6 Summary
Frequent-Itemset Mining:
Finding sets of items that frequently appear together in data is crucial for market-basket analysis and many other applications.
Similarity and Clustering:
Techniques like Jaccard similarity, minhashing, and clustering are useful for identifying similar items or groups in large datasets.
This chapter focuses on data mining techniques, particularly for large datasets, including market-basket analysis, similarity search, and clustering【68:0†source】【68:3†source】【68:5†source】【68:7†source】.
Chapter 23: Database Systems and the Internet
23.1 The Architecture of a Search Engine
Key Components: Search engines must perform two major functions:
Web Crawling: Copying many web pages and bringing them to the search engine for processing.
Query Answering: Taking user queries and finding relevant web pages through ranking.
Crawler: A crawler visits pages on the web, collecting data and storing it in a repository. The crawler continues following links found on each page to gather more data.
Inverted Index: A core structure in search engines, which associates each word with the list of pages that contain it. This allows efficient query processing.
23.2 PageRank for Identifying Important Pages
PageRank: A ranking algorithm that measures the importance of web pages based on the number of incoming links. Pages with many inbound links from other important pages receive higher ranks.
Transition Matrix: Represents the web as a matrix where each page links to others. PageRank can be calculated by repeatedly multiplying the current ranking vector by the transition matrix.
Spider Traps and Dead Ends: Challenges in calculating PageRank, where pages without out-links (dead ends) and clusters of interlinked pages (spider traps) can distort rankings. Solutions include introducing taxation and distributing the "lost" PageRank across the web.
23.3 Topic-Specific PageRank
Teleport Set: Used to focus the PageRank calculation on a particular subset of trusted or topic-specific pages. Pages in this set receive higher importance for queries related to their topic.
Combating Link Spam: Spam pages are created to manipulate PageRank. A search engine can mitigate this by using a teleport set composed of trusted pages or by calculating a page's "spam mass"—the proportion of PageRank derived from dubious links.
23.4 Data Streams
Data Streams Overview: Unlike traditional databases, data streams continuously receive tuples at high rates. Applications include clickstreams from websites, network packet analysis, sensor data, satellite data, and financial transaction streams.
Stream Management: Data-stream-management systems (DSMS) handle high-rate, continuous data. They support standing queries that run continuously and respond in real-time, and ad-hoc queries on stored data within a time window.
Sliding Windows: In streams, queries focus on a "sliding window" of the most recent data. These windows can be time-based or tuple-based, allowing real-time insights from a continually changing dataset.
23.5 Data Mining of Streams
Challenges in Stream Processing: Processing streams requires techniques to compress or summarize data to manage the vast amount of information. Full data storage is impractical, so algorithms aim to provide approximate answers within a fixed error bound.
Counting 1s in a Stream: A key problem is counting the number of "1"s in a window of a bitstream, which is solved by partitioning the window into buckets that represent increasing numbers of "1"s.
Counting Distinct Elements: In many streaming applications, it is useful to count the number of distinct elements in a window. This can be done approximately using hashing techniques to estimate the number of distinct elements without storing all the data.
23.6 Summary
Search engines rely on crawlers, inverted indexes, and ranking algorithms like PageRank to provide fast and relevant query responses.
Data streams are becoming increasingly important for applications requiring real-time data analysis, such as sensor networks, financial markets, and web traffic monitoring. Handling such streams requires new techniques to efficiently manage and query the incoming data【72:0†source】【72:3†source】【72:13†source】【72:15†source】【72:19†source】.
Last updated