What does a DBMS contain?
Information about a particular enterprise: a collection of interrelated data; a set of programs to access the data; an environment that is both convenient and efficient to use.
On what were database applications built in the early days?
Directly on top of file systems.
File systems: data redundancy and inconsistency vs data isolation.
Redundancy and inconsistency: multiple file formats, duplication of information in different files. Isolation: data scattered in multiple files and formats.
Why is "difficulty in accessing data" a drawback of file systems?
You need to write a new program to carry out each new task.
What are integrity problems in file systems?
Integrity constraints (e.g., account balance > 0) become "buried" in program code rather than being stated explicitly; it is hard to add new constraints or change existing ones.
Atomicity of updates: what is the problem? Give an example.
Failures may leave the database in an inconsistent state with partial updates carried out. Example: a transfer of funds from one account to another should either complete or not happen at all.
Why is concurrent access needed, and what can go wrong?
It is needed for performance; uncontrolled concurrent accesses can lead to inconsistencies (e.g., two people reading a balance of 100 and each withdrawing 50 at the same time).
What is the security problem of file systems?
It is hard to provide user access to some, but not all, data.
Physical, logical and view levels of abstraction.
Physical: how a record is stored. Logical: data stored in the database and the relationships among the data. View: application programs hide details of data types; views can hide information (e.g., salary) for security.
What is a schema, and what is designing one called?
A structural design that defines how data is organized, stored, and related. The process of designing a schema is known as data modeling.
Physical schema vs logical schema.
Physical: how data is physically stored on disk or storage devices (file structures, indices, partitioning, compression). Logical: what data is stored and the overall logical structure — tables, attributes, primary keys, foreign keys, integrity constraints — without worrying about physical storage.
What is the view schema?
The highest level of abstraction: it defines how end-users interact with the database, providing a view of the database as per the user role of application.
What is an instance of a database?
The actual content of the database at a particular point in time — analogous to the value of a variable.
Define data independence.
The ability to modify the database schema at one level of a database system without affecting the schema at the next higher level.
Physical vs logical data independence, with an example of each.
Physical: modify the physical schema without changing the logical schema — e.g., switching from a Hard Disk to an SSD. Logical: modify the conceptual schema without modifying the view/external schema — e.g., adding a new column (attribute) to a table.
What do data models describe?
Data, data relationships, data semantics, data constraints.
List the data models.
Relational; Entity-Relationship (mainly for database design); object-based (object-oriented and object-relational); semistructured (XML); older: network and hierarchical.
How do object-relational data models extend the relational model?
By including object orientation and constructs for added data types; attributes of tuples may have complex types, including non-atomic values such as nested relations; relational foundations (declarative access) are preserved, with upward compatibility with existing relational languages.
Who defined XML, and what was it originally intended for?
The WWW Consortium (W3C); originally intended as a document markup language, not a database language. It became the basis for new generation data interchange formats.
What is DDL, and what does the DDL compiler generate?
Data Definition Language: specification notation for defining the database schema. The DDL compiler generates a set of table templates stored in a data dictionary.
What does the data dictionary contain?
Metadata (data about data): database schema; integrity constraints (e.g., primary key); authorization (who can access what).
What is DML also known as, and what are its two classes of languages?
Query language. Pure (relational algebra, tuple relational calculus, domain relational calculus — for proving computational power and optimization) and commercial (SQL).
Why is SQL usually embedded in a higher-level language?
Because SQL is NOT a Turing machine equivalent language; to compute complex functions it is embedded in some higher-level language.
How do application programs generally access databases?
Through language extensions to allow embedded SQL, or an application program interface (e.g., ODBC/JDBC) which allows SQL queries to be sent to a database.
Logical design vs physical design.
Logical design: deciding on the database schema (a "good" collection of relation schemas; business and computer-science decisions). Physical design: deciding on the physical layout of the database.
What are the two approaches to database design?
Entity Relationship Model (an enterprise as a collection of entities and relationships, drawn as an E-R diagram) and Normalization Theory (formalize what designs are bad, and test for them).
Name the three parts of the database engine.
Storage manager; query processor; transaction manager.
What is the storage manager responsible for?
It is the interface between the low-level data stored in the database and the application programs and queries; responsible for interaction with the OS file manager and efficient storing, retrieving and updating of data.
Database engine: name the steps the query processor goes through.
1. Parsing and translation; 2. Optimization; 3. Evaluation.
On what does estimating the cost of query operations critically depend?
On statistical information about relations which the database must maintain (and estimated statistics for intermediate results).
A transaction is a collection of operations that does what?
Performs a single logical function in a database application.
Transaction-management component vs concurrency-control manager.
Transaction management keeps the database consistent despite system failures (power failures, OS crashes) and transaction failures. Concurrency control controls the interaction among concurrent transactions to ensure consistency.
Which users use query tools, and which write application programs?
Sophisticated users (analysts) use query tools; application programmers write application programs. (Naive users use application interfaces; database administrators use administration tools.)
List the four database architectures.
Centralized; client-server; parallel (multi-processor); distributed.
Give the two reasons a database programmer needs a general-purpose programming language.
Not all queries can be expressed in SQL (it lacks the full expressive power of a general-purpose language); non-declarative actions (printing a report, interacting with a user, sending results to a GUI) cannot be done from within SQL.
Which three calls does an application program make through a database API?
Connect with the database server; send SQL commands to the database server; fetch tuples of result one-by-one into program variables.
ODBC vs JDBC: which languages does each work with?
ODBC works with C, C++, C#, and Visual Basic (ADO.NET sits on top of ODBC). JDBC works with Java.
What does the ODBC standard let an application do?
Communicate with a database server: open a connection with a database, send queries and updates, get back results.
What is JDBC, and what is its model for communicating with the database?
A Java API for communicating with database systems supporting SQL. Model: open a connection; create a "statement" object; execute queries using the Statement object to send queries and fetch results; exception mechanism to handle errors.
What is special about resources opened in "try ( … )" (try with resources)?
They are automatically closed at the end of the try block (Java 7, JDBC 4 onwards).
executeUpdate vs executeQuery.
executeUpdate runs an update such as an insert; executeQuery runs a select and returns a ResultSet, read row by row with rset.next().
How do you detect a null value read from a JDBC ResultSet?
Read the value (e.g., int a = rset.getInt("a");) then call rset.wasNull().
Why must you use a PreparedStatement when adding user input to a query?
Slide 13: always use preparedStatements while reading input from the user; NEVER create a query by concatenating strings — e.g., a name such as "D'Souza" breaks a concatenated query.
ResultSet vs ResultSetMetaData.
ResultSet holds the actual data (rows); ResultSetMetaData provides the structural data (metadata) about those records — structure, types, and properties of the columns.
In DatabaseMetaData calls, what do null, "" and "%" mean?
null: all catalogs/schemas; "": the current catalog/schema; "%": the same meaning as the SQL like clause.
What does KEY_SEQ give in getPrimaryKeys?
The position of the attribute in the primary key — required if a primary key has multiple attributes.
What is JDBC's default transaction behaviour called, and what does it mean?
"Automatic commit": each SQL statement is treated as a separate transaction, executed and committed automatically.
How do you run several statements as one transaction in JDBC?
conn.setAutoCommit(false); execute the statements; then conn.commit() to save or conn.rollback() to discard; setAutoCommit(true) restores the default.
What is embedded SQL?
Including SQL statements directly within a program written in a high-level programming language like C, C++, COBOL, or Java.
In embedded SQL, how are host variables declared and used?
Declared between EXEC SQL BEGIN DECLARE SECTION; and EXEC SQL END DECLARE SECTION;, and used inside SQL with a colon, e.g., VALUES (:employee_id, :name).
Which SQL standard introduced functions and procedures, and which added table functions?
SQL:1999 introduced functions and procedures; SQL:2003 added functions that return a relation as a result.
returns vs return in an SQL function.
returns indicates the variable-type that is returned (e.g., integer); return specifies the values that are returned as the result of invoking the function.
What is a stored procedure, and what does it provide?
Precompiled SQL code that can be saved and reused (with parameters). It provides code reusability, improved performance, and database security.
dept_count_proc(in dept_name, out d_count): how do you run it, and what are the two parameter kinds?
With the call statement (from an SQL procedure or embedded SQL), e.g., call dept_count_proc('Physics', d_count); in = input parameter, out = output parameter.
What is name overloading in SQL:1999?
More than one function/procedure of the same name, as long as the number of arguments differ, or at least the types of the arguments differ.
What does the for loop in SQL procedures permit?
Iteration over all results of a query (e.g., summing the budget of all departments).
Benefits and drawbacks of external language functions/procedures.
Benefits: more efficient for many operations, more expressive power. Drawbacks: code may run in the database system's address space; risk of accidental corruption of database structures; security risk (access to unauthorized data).
Two ways to deal with the security problems of external language routines.
Sandbox techniques (a safe language like Java), or running them in a separate process with no access to the database process' memory. Both have performance overheads.
What is a trigger?
A stored procedure in a database that automatically invokes whenever a special event in the database occurs (e.g., a row is inserted or specific columns are updated).
Three key differences between triggers and stored procedures.
1. Triggers cannot be manually invoked or executed. 2. Triggers cannot receive parameters. 3. A transaction cannot be committed or rolled back inside a trigger.
In trigger syntax, what do [before | after] and [for each row] specify?
before/after: when the trigger will be executed. for each row: a row-level trigger, executed for each affected row.
What is a statement-level trigger and when is it useful?
A single action executed for all rows affected by a transaction (for each statement instead of for each row); more efficient when SQL statements update a large number of rows.
When should you avoid triggers?
1. Performance concerns; 2. cross-database or cross-server operations; 3. infinite loop potential (A updates B and B's trigger updates A).
What is a CTE?
A common table expression — a WITH statement that names a result for later reference.
What two parts does a recursive CTE need?
An initialization (base) query that seeds the recursion, and a WHERE clause in the iterative query that decides when the recursion stops.
What is the transitive closure of the prereq relation?
The view (rec_prereq) of all courses that are a prerequisite, whether directly or indirectly, for a given course.
Why can't a non-recursive, non-iterative query compute transitive closure?
It can perform only a fixed number of joins of a table with itself, giving only a fixed number of levels; a database with more levels can always be built on which the query will not work.
What is the fixed point of a recursive view, and what does "monotonic" mean?
Fixed point: the final result of the iterative process. Monotonic: if tuples are added to prereq, rec_prereq contains all the tuples it had before, plus possibly more.
Is the result of rank() over (order by GPA desc) sorted?
No. An extra order by clause (e.g., order by s_rank) is needed to get the rows in sorted order.
rank vs dense_rank when 3 students share the top GPA.
rank: all three get 1 and the next rank is 4 (gaps). dense_rank: all three get 1 and the next is 2 (no gaps).
What is a window function, and which clause defines the window?
A function that performs calculations across a specified set of rows known as a "window"; the OVER clause defines it (PARTITION BY to partition, ORDER BY to order).
What is OLAP?
Online Analytical Processing: interactive analysis of data, allowing data to be summarized and viewed in different ways; multidimensional analysis on large volumes of data (e.g., in a data warehouse).
Describe a cross-tab (pivot-table).
Values of one dimension attribute form the row headers, values of another form the column headers, other dimension attributes are listed on top, and each cell holds the aggregate (sum) for the values that specify it.
What is a data cube?
A multidimensional generalization of a cross-tab; it can have n dimensions, and cross-tabs can be used as views on it.
When cross-tabs are represented as relations, what represents aggregates?
The value all; the SQL standard actually uses null in place of all, despite confusion with regular null values.
cube over three attributes: count the grouping lists and say where the count comes from.
Eight: the union of GROUP BY on every subset of the three attributes, including the empty grouping ( ).
rollup over (item_name, color, size): which lists are produced, and what rule picks them?
A union on every prefix of the specified attribute list (hierarchical aggregates). Four: (item_name, color, size), (item_name, color), (item_name), ( ).
What is drill down (roll down)?
The reverse of roll up: like zooming-in on the data cube; it navigates from less detailed record to more detailed data.
What is a slice?
A subset of the cube corresponding to a single value for one or more members of the dimension (e.g., temperature = cool), turning a 3-D cube into a 2-D one.
What is the pivot operation?
Also called rotation: a visualization operation that rotates the data axes in view to give an alternative presentation, e.g., swapping the rows and columns.
MOLAP vs ROLAP vs HOLAP.
MOLAP: multidimensional arrays in memory (the earliest). ROLAP: only relational database features. HOLAP: some summaries in memory, base data and other summaries in a relational database.
What does indexing do for database performance?
It speeds up access to desired data by minimizing the number of disc visits required to fulfill a query.
Search key vs pointer in an index entry.
Search key: the attribute(s) used to look up records in a file. Pointer: the address of the disk block where the instance corresponding to the key can be found.
Indices fall into two basic families. Which, and how is each organised?
Ordered indices (sorted) and hash indices (search keys distributed uniformly across "buckets" using a "hash function").
List the five index evaluation metrics.
Access types supported efficiently; access time; insertion time; deletion time; space overhead.
Primary index vs secondary index.
Primary (clustering): its search key specifies the sequential order of the file (usually, not necessarily, the primary key). Secondary (non-clustering): its search key specifies an order different from the sequential order of the file.
What is an index-sequential file?
An ordered sequential file with a primary index.
Dense index vs sparse index.
Dense: an index record for every search-key value in the file. Sparse: index records for only some search-key values (records must be sequentially ordered on the search key).
How do you locate search-key value K with a sparse index?
Find the index record with the largest search-key value < K, then search the file sequentially starting at the record it points to.
What is the "good tradeoff" for sparse indices?
A sparse index with an index entry for every block in the file, corresponding to the least search-key value in the block.
Primary vs secondary index for a sequential scan: which is costly, and why?
Scanning with a secondary index is costly: each record access may fetch a new block from disk; a block fetch requires about 5 to 10 milliseconds versus about 100 nanoseconds for memory access.
What is the cost of having many indices?
Updating indices imposes overhead on database modification: when a file is modified, every index on the file must be updated.
When the primary index is too big for memory, what are the outer and inner index?
Outer index: a sparse index of the primary index. Inner index: the primary index file (kept on disk as a sequential file).
Three strategies for dept_name = "Finance" and salary = 80000 with single-attribute indices.
1. dept_name index, then test salary; 2. salary index, then test dept_name; 3. use both indices and take the intersection of both sets of pointers.
What is lexicographic ordering of composite keys?
(a1, a2) < (b1, b2) if either a1 < b1, or a1 = b1 and a2 < b2.
Which condition can an index on (dept_name, salary) NOT handle efficiently?
dept_name < "Finance" and salary (balance) = 80000 — it may fetch many records that satisfy the first but not the second condition. The order of the attributes matters.
Sparse index deletion: what happens to the entry of the deleted key?
It is replaced with the next search-key value in the file (in search-key order); if that next value already has an index entry, the entry is deleted instead of being replaced.
Sparse index insertion (entry per block): when does the index change?
Only when a new block is created: the first search-key value appearing in the new block is inserted into the index.
Disadvantage of indexed-sequential files vs advantage of B+-trees.
Indexed-sequential: performance degrades as the file grows (overflow blocks) and periodic reorganization of the entire file is required. B+-tree: automatically reorganizes itself with small, local changes.
B+-tree of order m: path lengths, children of internal nodes, values in a leaf, and the root.
All paths from root to leaf are of the same length; each node that is not a root or leaf has between ⌈m/2⌉ and m children; a leaf node has between ⌈m/2⌉ and (m−1) values; a non-leaf root has at least 2 children.
In a B+-tree node, what are K_i and P_i?
K_i are the search-key values (ordered K_1 < K_2 < …). P_i are pointers to children (non-leaf nodes) or to records or buckets of records (leaf nodes).
Where does P_m of a leaf node point?
To the next leaf node in search-key order.
What do the non-leaf nodes of a B+-tree form?
A multi-level sparse index on the leaf nodes.
Maximum B+-tree height for K search-key values, and the 1-million example.
No more than ⌈log_⌈m/2⌉(K)⌉. With 1 million keys and m = 100: at most log_50(1,000,000) = 4 nodes accessed, versus around 20 for a balanced binary tree.
How big is a B+-tree node typically, and what is a typical m?
Generally the same size as a disk block, typically 4 kilobytes; m is typically around 100 (40 bytes per index entry).
Order M = 5: maximum values and children per node, and what happens with a fifth value?
Maximum 5 children and 4 values (M−1). A fifth value overflows the node: it splits and the middle value moves to the parent.
Inserting C N G A then H into an order-5 tree: which value moves up?
G — the node would be (A, C, G, H, N), so the middle data G moves to the parent.
What is hashing, and what is a bucket?
Hashing is a technique to quickly locate a data record irrespective of the size of the database. A bucket is a unit of storage containing one or more records (typically a disk block).
Why must an entire bucket be searched sequentially?
Because records with different search-key values may be mapped to the same bucket.
Static hashing: what stays constant, and what is H(107) % 5?
The number of buckets remains constant (good for known size). H(107) % 5 = 2.
Worst vs ideal hash function.
Worst: maps all search-key values to the same bucket. Ideal: uniform (each bucket gets the same number of values) and random (same number of records per bucket irrespective of the actual distribution).
What causes bucket overflow?
Insufficient buckets, or skew in the distribution of records (multiple records with the same search-key value; a hash function giving a non-uniform distribution). It can be reduced but not eliminated.
Closed hashing vs open hashing.
Closed hashing: overflow chaining — overflow buckets of a bucket are chained in a linked list. Open hashing: no overflow buckets; not suitable for database applications.
What is a hash index, and is it primary or secondary?
It organizes the search keys, with their associated record pointers, into a hash file structure. Strictly speaking, hash indices are always secondary indices.
Deficiencies of static hashing.
Fixed bucket addresses while databases grow or shrink: too few buckets → too many overflows; space for anticipated growth → wasted space; shrinking → wasted space; periodic re-organization is expensive and disruptive.
What is dynamic hashing, and what are its components?
Also known as extendible hashing: buckets are added and removed on demand; good for databases that grow and shrink frequently. Components: data bucket, flexible hash function, and directories (which store pointers to buckets).
What is the global depth in dynamic hashing?
The number of bits in each directory id; the more records, the more bits.
When is hashing better, and when are ordered indices preferred?
Hashing is generally better at retrieving records having a specified value of the key; if range queries are common, ordered indices are preferred.
Hash indices and B+-trees: which does each system (PostgreSQL, Oracle, SQLServer) support?
PostgreSQL supports hash indices; Oracle supports static hash organization, but not hash indices; SQLServer supports only B+-trees.
Describe a bitmap index on an attribute.
A bitmap for each value of the attribute; each bitmap has as many bits as records; the bit is 1 if the record has that value, otherwise 0.
When are bitmap indices useful, and how are queries answered?
For queries on multiple attributes (not single-attribute queries); answered with bitmap operations: intersection (and), union (or), complementation (not).
What does create unique index do?
It indirectly specifies and enforces the condition that the search key is a candidate key.
Query processing: list the steps in order.
Parsing and translation; query optimization; evaluation.
What does the parser do in the first step?
It checks syntax and semantic, verifies relations, and translates the query into its relational algebra form.
What is query optimization?
The process of choosing a suitable execution strategy for processing a query: amongst all equivalent evaluation plans, choose the one with lowest cost.
What is an evaluation-plan?
An annotated relational algebra expression that specifies a detailed evaluation strategy.
How is query cost measured, and why?
By the number of block transfers from disk — disk access is typically the predominant cost and is relatively easy to estimate.
What is a query block?
The basic unit that can be translated into algebraic operators and optimized: a single SELECT-FROM-WHERE expression, plus GROUP BY and HAVING if part of the block. Nested queries are separate query blocks.
What is external sorting, and which algorithm suits it?
Sorting large files stored on disk that do not fit entirely in main memory; merge sort is a good choice.
Merge sort sorting phase: how many initial runs, and at what cost?
nR = ⌈b/nB⌉ runs (b = file blocks, nB = buffer pages); cost = read b + write b = 2b.
What is the degree of merging dM, and why nB − 1?
dM = min(nB − 1, nR): one buffer block holds a block from each run being merged, and one block is needed for the merged result.
Number of merge passes and total merge-sort cost.
nP = ⌈log_dM(nR)⌉; Cost = 2b + 2b × nP = 2b (⌈log_dM(nR)⌉ + 1).
External merge sort: b = 10,000, nB = 3. Runs, passes and total I/O?
nR = 3334; dM = 2; nP = 12 passes; total I/O = 2 × 10000 × 13 = 260,000.
What do r, R, b and bfr mean in catalog information?
r = # of records in the file; R = record size; b = # of blocks in the file; bfr = blocking factor.
Define selectivity (sl) and selection cardinality (s).
sl = the ratio of the # of records satisfying the condition to the total # of records; s = sl × r = average # of records that satisfy an equality condition on the attribute.
sl and s for a key attribute vs a nonkey attribute.
Key: d = r, sl = 1/r, s = 1. Nonkey (uniform): sl = 1/d, s = r/d.
File scan vs index scan.
File scan: search algorithms that locate and retrieve records fulfilling a selection condition. Index scan: search algorithms that use an index (the condition must be on the index search-key). Cost C = # of disk blocks scanned.
S1 linear search cost: nonkey attribute vs equality on a key.
Nonkey: C = b. Key equality: C = b/2 on average if found, else C = b.
When can S2 binary search be used, and what does it cost?
For an equality comparison on the attribute on which the file is ordered (blocks stored contiguously); C = ⌈log2 b⌉.
S3 cost with a primary index vs a hash index.
Primary index: C = x + 1 (one more block than the # of index levels). Hash index: C = 1 for static or linear hashing, C = 2 for extendable hashing.
S4 and S5 costs.
S4 (primary index on a key, range): average C = x + b/2. S5 (clustered index on nonkey, equality): C = x + ⌈s/bfr⌉.
S9 vs S10.
S9 (conjunctive): intersection of the record-pointer sets from each condition's index. S10 (disjunctive): union of the pointer sets — only if all conditions have indices, otherwise linear scan.
How does S7 handle a conjunctive selection with one index?
Choose the condition and algorithm (S1–S6) with the least cost for σ θi (r), then test the other conditions on each tuple after fetching it into the memory buffer.
What is materialized evaluation?
Evaluating one operation at a time, starting at the lowest level, and storing intermediate results in temporary relations used for the next-level operations.
What is pipelined evaluation, and why is it cheaper?
Several operations are evaluated simultaneously, each passing its results to the next without waiting (stream-based processing). It is much cheaper because no temporary relation is stored to disk.
Give two operations for which pipelining may not be possible.
Sort and hash-join.
Which factors affect join performance?
Available buffer space and the choice of inner vs outer relation.
Nested-loop join: advantages and disadvantage.
Requires no indices and can be used with any kind of join condition; but it is expensive since it examines every pair of tuples in the two relations.
Nested-loop join: worst-case cost, and which relation should be inner if one fits in memory?
Worst case: C = bR + (rR × bS) + bRS. If the smaller relation fits entirely in memory, use it as the inner relation: bR + bS + bRS.
Block nested-loop join: how does it work and what is its worst-case cost?
Every block of the inner relation is paired with every block of the outer relation. Worst case: C = bR + (bR × bS) + bRS. If neither fits in memory, choose the smaller relation for the outer loop.
When can an indexed nested-loop join be used, and which relation is outer if both have indices?
When an index is available on the inner relation's join attribute (or one is built for the join). If both have indices, use the relation with fewer tuples as the outer.
depositor (5,000 records, 100 blocks) ⋈ customer (400 blocks; primary B+-tree index on the join attribute, 4 levels): block nested loops vs indexed nested loops cost?
Block nested loops: 100 + 100 × 400 = 40,100. Indexed (primary B+-tree, 4 levels + 1 data access = 5): 100 + 5000 × 5 = 25,100 (each + bRS).
Sort-merge join: steps and restriction.
Sort both relations on the join attribute (if not sorted), then merge them, matching every pair with the same join value. Can be used only for equi-joins and natural joins.
How many block accesses does a merge-join need?
bR + bS + sorting cost (if not sorted) + bRS — each block needs to be read only once.
What is relational algebra, and why is it useful for query processing?
A formal language used to query and manipulate relational databases (selection, projection, union, join, …); it is very useful for representing execution plans.
Name the five basic relational algebra operations.
Selection (σ), projection (π), cross-product (×), set-difference (−), union (∪).
Selection vs projection: which is horizontal and which vertical?
Selection (σ) selects a subset of rows — horizontal. Projection (π) retains the required columns — vertical.
Why can relational algebra operations be composed?
Because each operation returns a relation — the algebra is "closed".
What is the schema of the result of a selection?
The same as that of the input relation.
Does projection eliminate duplicates? Do real systems?
The projection operator has to eliminate duplicates; real systems typically don't do duplicate elimination unless the user explicitly asks for it.
S2(sid, sname, rating, age) = {(28, yuppy, 9, 35.0), (31, lubber, 8, 55.5), (44, guppy, 5, 35.0), (58, rusty, 10, 35.0)}. What are σ rating>8 (S2) and π age (S2)?
σ rating>8 (S2) = (28, yuppy, 9, 35.0), (58, rusty, 10, 35.0). π age (S2) = 35.0, 55.5.
Using S1 and S2, what are S1 − S2 and S2 − S1?
S1 − S2 = (22, dustin, 7, 45.0). S2 − S1 = (28, yuppy, 9, 35.0), (44, guppy, 5, 35.0).
What does the cross-product S1 × R1 produce?
Each row of S1 paired with each row of R1 (for the slide instances: 3 × 2 = 6 rows).
Natural join R ⋈ S conceptually: the three steps.
Compute R × S; select rows where attributes appearing in both relations have equal values; project all unique attributes and one copy of each common one.
Why are joins called compound operators?
They involve cross product, selection, and (sometimes) projection.
S1 = {(22, dustin, 7, 45.0), (31, lubber, 8, 55.5), (58, rusty, 10, 35.0)}; R1(sid, bid, day) = {(22, 101, 10/10/96), (58, 103, 11/12/96)}. What does the theta join S1 ⋈ S1.sid<R1.sid R1 return?
(22, dustin, …, 58, 103, 11/12/96) and (31, lubber, …, 58, 103, 11/12/96) — both sid columns are kept.
When are two relational algebra expressions equivalent?
When on every legal database instance they generate the same set of tuples (order of tuples is irrelevant).
Equivalence rule 1.
Conjunctive selection can be deconstructed into a sequence of individual selections: σ θ1∧θ2 (E) = σ θ1 (σ θ2 (E)).
Equivalence rule 3.
Only the last in a sequence of projection operations is needed: π L1 (π L2 (… (π Ln (E)))) = π L1 (E).
Equivalence rule 4.
Selections combine with Cartesian products and theta joins: σ θ (E1 × E2) = E1 ⋈ θ E2; σ θ1 (E1 ⋈ θ2 E2) = E1 ⋈ θ1∧θ2 E2.
Equivalence rules 5 and 6.
5: theta joins (and natural joins) are commutative: E1 ⋈ E2 = E2 ⋈ E1. 6: natural joins are associative: (E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3); theta joins too, if θ2 involves attributes from only E2 and E3.
Equivalence rule 7a.
When θ0 involves only the attributes of E1: σ θ0 (E1 ⋈ θ E2) = (σ θ0 (E1)) ⋈ θ E2 — selection distributes over the theta join.
Equivalence rule 8a.
If θ involves only attributes from L1 ∪ L2: π L1∪L2 (E1 ⋈ θ E2) = (π L1 (E1)) ⋈ θ (π L2 (E2)).
Which set operations are commutative, and which is not?
Union and intersection are commutative (rule 9); set difference is not commutative.
Equivalence rules 11 and 12.
11: selection distributes over ∪, ∩ and − (e.g., σ θ (E1 − E2) = σ θ (E1) − σ θ (E2)). 12: projection distributes over union: π L (E1 ∪ E2) = π L (E1) ∪ π L (E2).
Why perform the selection σ branch_city="Brooklyn" (branch) before the join?
Performing the selection as early as possible reduces the size of the relation to be joined (rule 7a).
In the Brooklyn / balance > 1000 example, which rule makes "selections early" possible?
Join associativity (rule 6a): regroup as (branch ⋈ account) ⋈ depositor, then apply σ branch_city="Brooklyn" (branch) ⋈ σ balance>1000 (account).
How do you choose between (r1 ⋈ r2) ⋈ r3 and r1 ⋈ (r2 ⋈ r3)?
They are equal; if r2 ⋈ r3 is quite large and r1 ⋈ r2 is small, choose (r1 ⋈ r2) ⋈ r3 so a smaller temporary relation is computed and stored.
What is a transaction?
A set of logical operations to access and update the various data items of a database.
Which two main issues must transaction processing deal with?
Failures of various kinds (hardware failures, system crashes) and concurrent execution of multiple transactions.
What does ACID stand for?
Atomicity, Consistency, Isolation, Durability.
Atomicity: what must the system ensure if a transfer fails after step 3?
That updates of a partially executed transaction are not reflected in the database ("All or nothing rule").
Abort vs commit.
Abort: changes made to the database are not visible. Commit: changes made are visible.
Consistency in the $50 transfer example.
The total is maintained: 200 + 100 = 300 before, 150 + 150 = 300 after — the transaction takes the database from one consistent state to another.
When does the durability requirement start to apply?
Once the user has been notified that the transaction has completed; its updates must then persist even if there are software or hardware failures.
What goes wrong without isolation in the transfer example, and how can isolation be ensured?
Another transaction reading A and B between steps 3 and 6 sees an inconsistent database (A + B less than it should be). Isolation can be ensured by running transactions serially.
Who is responsible for each ACID property?
Atomicity: Transaction Manager. Consistency: Application programmer. Isolation: Concurrency Control Manager. Durability: Recovery Manager.
List the five transaction states.
Active; partially committed; failed; aborted; committed.
Partially committed vs committed.
Partially committed: after the final statement has been executed. Committed: after successful completion.
What is the aborted state, and what are the two options after it?
The transaction has been rolled back and the database restored to its state prior to the start. Options: restart the transaction (only if no internal logical error) or kill it.
Two advantages of concurrent execution.
Increased processor and disk utilization (better transaction throughput); reduced average response time (short transactions need not wait behind long ones).
What are concurrency control schemes?
Mechanisms to achieve isolation: they control the interaction among concurrent transactions to prevent them from destroying the consistency of the database.
What is a schedule, and which two rules must it follow?
A sequence of instructions specifying the chronological order of the instructions of concurrent transactions. It must consist of all their instructions and preserve the order within each individual transaction.
What is the last statement of a transaction that completes, and of one that fails?
Commit for a successful transaction (assumed by default); abort for a failed one.
Is Schedule 3 serial? Is it acceptable?
It is not serial, but it is equivalent to Schedule 1 (and preserves A + B), so it is acceptable — it is conflict serializable (slide 20).
When is a schedule serializable?
When it is equivalent to a serial schedule (conflict serializability or view serializability).
The three conditions for two operations to conflict.
They belong to different transactions; they operate on the same data item; at least one of them is a write operation.
Define conflict equivalent and conflict serializable.
S and S' are conflict equivalent if S can be transformed into S' by a series of swaps of non-conflicting instructions. S is conflict serializable if it is conflict equivalent to a serial schedule.
Schedule: T3 read(Q); T4 write(Q); T3 write(Q). Why is it not conflict serializable?
T4's write(Q) lies between T3's read(Q) and write(Q); these conflict, so no swaps give either < T3, T4 > or < T4, T3 >.
When is an arc drawn from Ti to Tj in a precedence graph?
When the two transactions conflict, and Ti accessed the data item on which the conflict arose earlier.
What is the precedence-graph test for conflict serializability?
A schedule is conflict serializable if and only if its precedence graph is acyclic; the serializability order is a topological sorting of the graph.
How long does cycle detection take?
Order n² time (n = number of vertices); better algorithms take order n + e (e = number of edges).
How does a transaction begin and end in SQL?
It begins implicitly. It ends by commit work (commits and begins a new one) or rollback work (aborts the current transaction).
What is a lock?
A mechanism to control concurrent access to a data item.
Exclusive (X) vs shared (S) lock.
X: the data item can be both read and written; requested with lock-X. S: the data item can only be read; requested with lock-S.
To whom are lock requests made, and when can the transaction proceed?
To the concurrency-control manager; the transaction can proceed only after the request is granted.
Which locks are compatible?
Only shared with shared: any number of transactions can hold S-locks on an item; if any transaction holds an X-lock, no other transaction may hold any lock on it.
What happens if a requested lock cannot be granted?
The requesting transaction is made to wait till all incompatible locks held by other transactions have been released; then the lock is granted.
T2: lock-S(A); read(A); unlock(A); lock-S(B); read(B); unlock(B); display(A+B). Why is this locking not sufficient to guarantee serializability?
It unlocks A before locking B; if A and B get updated in between the reads, the displayed sum A + B would be wrong.
What is a locking protocol?
A set of rules followed by all transactions while requesting and releasing locks; locking protocols restrict the set of possible schedules.
What are the two phases of two-phase locking?
Growing phase: may obtain locks, may not release locks. Shrinking phase: may release locks, may not obtain locks.
What does two-phase locking guarantee, and in what order are transactions serialized?
Conflict-serializable schedules; transactions can be serialized in the order of their lock points (where each acquired its final lock).
Lock conversions in 2PL: upgrade vs downgrade.
Upgrade: convert lock-S to lock-X — allowed in the first (growing) phase. Downgrade: convert lock-X to lock-S — allowed in the second (shrinking) phase.
What is a deadlock, and how is it handled?
A situation where neither transaction can make progress because each waits for the other to release a lock. One of them must be rolled back and its locks released.
Does two-phase locking ensure freedom from deadlocks?
No — two-phase locking does not ensure freedom from deadlocks.
Give two examples of starvation.
A transaction waits for an X-lock while a sequence of other transactions are granted S-locks on the same item; the same transaction is repeatedly rolled back due to deadlocks.
List the four reasons for starvation.
Unfair waiting scheme for locked items (priority queue); victim selection (same victim repeatedly); resource leak; denial-of-service attack.
How does the lock manager answer a lock request?
With a lock grant message, or a message asking the transaction to roll back (in case of a deadlock); the requesting transaction waits until it is answered.
What is the lock table, and how is it usually implemented?
A data structure recording granted locks and pending requests; usually an in-memory hash table indexed on the name of the data item being locked.
When is a new lock request granted in the lock table?
It is added to the end of the queue for the data item and granted if it is compatible with all earlier locks.
What does an edge Ti → Tj in a wait-for graph mean?
Ti is waiting for Tj to release a data item. The edge is removed when Tj no longer holds a data item needed by Ti.
When is the system in a deadlock state?
If and only if the wait-for graph has a cycle; a deadlock-detection algorithm must be invoked periodically to look for cycles.
Name two deadlock prevention strategies.
Pre-declaration: each transaction locks all its data items before it begins execution. Partial ordering: a transaction locks data items only in the order of a partial order imposed on all items.
Wait-die: what happens to an older and to a younger requester?
Older requester (smaller timestamp) waits; younger requester dies (rolled back) and is restarted later with the same timestamp. Non-preemptive.
Wound-wait: what happens to an older and to a younger requester?
Older requester wounds the younger holder (the holder is rolled back and restarted with its timestamp); younger requester waits. Preemptive.
Wait-die vs wound-wait: preemption, waiting of older transactions, and number of rollbacks.
Wait-die: non-preemptive; older transactions must wait for younger ones; more aborts and rollbacks. Wound-wait: preemptive; older transactions never wait for younger ones; fewer aborts and rollbacks.
Why do wait-die and wound-wait avoid starvation?
A rolled back transaction is restarted with its original timestamp, so older transactions have precedence over newer ones.
Timeout-based schemes: how they work, pro and cons.
A transaction waits for a lock only for a specified time, then is rolled back and restarted, so deadlocks are not possible. Simple to implement, but starvation is possible and a good timeout value is difficult to determine.
Deadlock recovery: which victim, and how far to roll back?
Choose the victim that will incur minimum cost. Either total rollback (abort and restart) or, more effective, roll back only as far as necessary to break the deadlock.
How is starvation avoided in deadlock recovery?
Include the number of rollbacks in the cost factor, so the same transaction is not always chosen as victim.