What does a DBMS contain?
Information about a particular enterprise: a collection of interrelated data, a set of programs to access the data, and an environment that is both convenient and efficient to use.
Data redundancy and inconsistency in file systems
Multiple file formats, duplication of information in different files.
Difficulty in accessing data (file systems)
Need to write a new program to carry out each new task.
Integrity problems (file systems)
Integrity constraints (e.g., account balance > 0) become "buried" in program code rather than being stated explicitly; hard to add new constraints or change existing ones.
Atomicity of updates: the problem and the 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.
Concurrent access problem: the example
Two people reading a balance (say 100) and updating it by withdrawing money (say 50 each) at the same time — uncontrolled concurrent accesses can lead to inconsistencies.
Security problems (file systems)
Hard to provide user access to some, but not all, data.
Physical level of abstraction
The lowest level of abstraction: describes how a record (e.g., instructor) is stored.
Logical level of abstraction
Describes what data is stored in the database, and the relationships among the data.
View level of abstraction
Application programs hide details of data types; views can also hide information (such as an employee's salary) for security purposes.
Database schema vs instance
Schema: the overall design of the database (analogous to the type of a variable). Instance: the actual content of the database at a particular point in time (analogous to the value of a variable).
Physical data independence
The ability to modify the physical schema without changing the logical schema (applications depend on the logical schema).
What is a data model?
A collection of tools for describing data, data relationships, data semantics and data constraints.
List the data models.
Relational; Entity-Relationship (mainly for database design); object-based (object-oriented and object-relational); semi-structured (XML); older: network and hierarchical.
What is DDL?
Data Definition Language: a specification notation for defining the database schema.
What does the data dictionary contain?
Metadata (data about data): the database schema; integrity constraints (e.g., primary key); authorization (who can access what).
What is DML, and what else is it called?
Data Manipulation Language: a language for accessing and manipulating the data organized by the appropriate data model; also known as query language.
Pure vs commercial query languages
Pure: used for proving properties about computational power and for optimization (relational algebra, tuple and domain relational calculus). Commercial: used in commercial systems — SQL is the most widely used.
How do application programs 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). Physical design: deciding on the physical layout of the database.
The two approaches to ensuring each relation is "good"
The Entity Relationship Model (an enterprise as entities and relationships, drawn as an E-R diagram) and Normalization Theory (formalize what designs are bad, and test for them).
What do object-relational data models add to the relational model?
Object orientation and constructs for added data types; attributes with complex types, including non-atomic values such as nested relations — while preserving relational foundations and upward compatibility.
What was XML originally intended for, and what is it now used for?
Originally a document markup language, not a database language; new and nested tags made it a great way to exchange data — the basis for all new generation data interchange formats.
What is the storage manager, and what are its tasks?
A program module that provides the interface between the low-level stored data and the application programs and queries. Tasks: interaction with the OS file manager; efficient storing, retrieving and updating of data.
The three steps of query processing
1. Parsing and translation; 2. Optimization; 3. Evaluation.
What is a transaction?
A collection of operations that 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 and transaction failures. Concurrency-control manager: controls the interaction among concurrent transactions to ensure consistency.
Which database users use query tools, and which use application interfaces?
Sophisticated users (analysts) use query tools; naive users (tellers, agents, web users) use application interfaces.
The four database architectures
Centralized; client-server; parallel (multi-processor); distributed.
Two-tier vs three-tier architecture
Two-tier: the client application talks over the network directly to the database system. Three-tier: the application client talks to an application server, which uses the database system.
Who defined the relational data model?
Ted Codd (late 1960s and 1970s); he won the ACM Turing Award for this work.
What is the domain of an attribute?
The set of allowed values for that attribute.
What does "atomic" mean for attribute values?
Indivisible — attribute values are (normally) required to be atomic.
What is null?
A special value that is a member of every domain; it indicates that the value is "unknown". It causes complications in the definition of many operations.
Relation schema (with the example)
R = (A1, A2, …, An), where A1 … An are attributes — e.g., instructor = (ID, name, dept_name, salary).
Formally, what is a relation r?
A subset of D1 × D2 × … × Dn — a set of n-tuples (a1, …, an) where each ai ∈ Di.
Does the order of tuples matter in a relation?
No — relations are unordered; tuples may be stored in an arbitrary order.
Superkey
A set of attributes K ⊆ R whose values are sufficient to identify a unique tuple of each possible relation r(R) — e.g., {ID} and {ID, name} for instructor.
Candidate key
A minimal superkey — e.g., {ID} for instructor.
Primary key
One of the candidate keys, selected to be the primary key.
Foreign key constraint
A value in one relation (referencing) must appear in another (referenced) — e.g., dept_name in instructor references department.
The 6 basic operations of relational algebra
Select, project, union, set difference, Cartesian product, and rename.
The three pure query languages and their computing power
Relational algebra, tuple relational calculus, domain relational calculus — equivalent in computing power.
What are the input and the output of every relational query?
Input: a table (or set of tables). Output: a table; all data in the output appears in one of the input tables.
σ (selection)
Selects rows (tuples): returns the rows of the input relation that satisfy the predicate — e.g., σ salary >= 85000 (instructor).
Π (projection)
Selects columns (attributes): outputs the specified attributes from all rows and removes duplicate tuples — e.g., Π ID, salary (instructor).
How can intersection be written with set difference?
r ∩ s = r − (r − s).
r = (α,1), (α,2), (β,1); s = (α,2), (β,3). What are r ∪ s, r − s and r ∩ s?
r ∪ s = (α,1), (α,2), (β,1), (β,3); r − s = (α,1), (β,1); r ∩ s = (α,2).
Cartesian product r × s: how many rows?
Every row of r is paired with every row of s: rows(r) × rows(s) — e.g., 2 × 4 = 8 rows on slide 15.
ρ x (E)
Rename: returns the expression E under the name X, so a relation can be referred to by more than one name.
In r × s, both relations have attribute B. How are the two Bs named?
r.B and s.B.
Natural join r ⋈ s
A relation on schema R ∪ S: for each pair of tuples that have the same value on each attribute in R ∩ S, add one tuple combining them.
Write r ⋈ s using Π, σ and × (r on A,B,C,D; s on B,D,E).
Π A, r.B, C, r.D, E (σ r.B = s.B ∧ r.D = s.D (r × s)).
Where did SQL come from?
IBM's Sequel language, developed as part of the System R project at the IBM San Jose Research Laboratory, renamed Structured Query Language (SQL).
What does the SQL DDL allow you to specify?
The schema for each relation; the domain of each attribute; integrity constraints; and also indices, security and authorization, and the physical storage structure.
char(n) vs varchar(n)
char(n): fixed length string of length n. varchar(n): variable length string with maximum length n.
numeric(p,d)
Fixed point number: precision of p digits, d of them to the right of the decimal point — numeric(3,1) stores 44.5 but not 444.5 or 0.32.
BOOLEAN and DATE in SQL
BOOLEAN has three values: TRUE, FALSE and UNKNOWN. DATE has ten positions: yyyy-mm-dd.
The three integrity constraints in create table
not null; primary key (A1, …, An); foreign key (Am, …, An) references r.
Does a primary key attribute need "not null"?
No — a primary key declaration on an attribute automatically ensures not null.
alter table r add A D: what value do existing tuples get?
null for the new attribute.
Why drop sec_id from the primary key of takes?
To ensure a student cannot be registered for two sections of the same course in the same semester.
select / from / where ↔ relational algebra
select ↔ projection (Π); from ↔ Cartesian product (×); where ↔ selection predicate (σ).
distinct vs all in select
distinct forces the elimination of duplicates; all specifies that duplicates should not be removed.
select 'A' from instructor returns…
A table with one column and N rows (one per instructor tuple), each with value "A".
Are SQL names case sensitive?
No — SQL names are case insensitive (Name ≡ NAME ≡ name).
Is the keyword "as" required for renaming?
No — as is optional: instructor as T ≡ instructor T.
% and _ in like patterns
% matches any substring; _ matches any (single) character.
'_ _ _' vs '_ _ _ %'
'_ _ _' matches any string of exactly three characters; '_ _ _ %' matches any string of at least three characters.
Are like patterns case sensitive?
Yes — patterns are case sensitive.
Default order in order by
Ascending (asc); use desc for descending.
Tuple occurs m times in r, n times in s: union all / intersect all / except all
m + n; min(m, n); max(0, m − n).
Do union, intersect and except keep duplicates?
No — they automatically eliminate duplicates; use union all, intersect all, except all to retain them.
5 + null = ?
null — the result of any arithmetic expression involving null is null.
Any comparison with null returns…
unknown (e.g., 5 < null, null <> null, null = null).
unknown or true; false and unknown; not unknown
true; false; unknown.
How is a where predicate that evaluates to unknown treated?
As false.
Rule for attributes in select with group by
Attributes in the select clause outside of aggregate functions must appear in the group by list.
where vs having
where predicates are applied before forming groups; having predicates are applied after the formation of groups.
Aggregates and null
All aggregates except count(*) ignore null values; with only null values, count returns 0 and the others return null.
Where can a subquery appear in select … from … where …?
In select: a subquery generating a single value; in from: any valid subquery; in where: B <operation> (subquery).
F <comp> some r
True if there exists at least one t in r such that F <comp> t. (= some) ≡ in, but (≠ some) ≢ not in.
F <comp> all r
True if F <comp> t for every t in r. (≠ all) ≡ not in, but (= all) ≢ in.
exists r / not exists r
exists r ⇔ r ≠ Ø (the subquery is nonempty); not exists r ⇔ r = Ø.
Correlated subquery and correlation name
A correlated subquery is an inner query that uses a variable of the outer query; that variable (e.g., S) is the correlation name.
The unique construct
Tests whether a subquery has any duplicate tuples; true if the subquery contains no duplicates.
The with clause
Defines a temporary relation whose definition is available only to the query in which the with clause occurs.
Scalar subquery: what is it, and what if it returns several tuples?
A subquery used where a single value is expected; a runtime error occurs if it returns more than one result tuple.
delete … where salary < (select avg(salary) …): how does SQL handle the changing average?
It first computes avg(salary) and finds all tuples to delete, then deletes them without recomputing avg or retesting the tuples.
insert into … select …: when are results inserted?
The select-from-where statement is evaluated fully before any of its results are inserted.
Raise salaries ≤ 100000 by 5% and others by 3% in one statement
update instructor set salary = case when salary <= 100000 then salary * 1.05 else salary * 1.03 end
Join condition vs join type
Join condition: which tuples in the two relations match, and what attributes are in the result. Join type: how tuples that do not match any tuple in the other relation are treated.
Inner join returns…
Rows only when there is at least one row from both tables that matches the join condition.
What is an outer join?
An extension of the join that avoids loss of information: it computes the join and then adds the non-matching tuples of one relation, using null values.
Left, right and full outer join: which rows are kept?
Left: all rows from the left table. Right: all rows from the right table. Full: all rows from both tables.
course natural left outer join prereq: which extra row appears, and how?
CS-315 (Robotics), with prereq_id null — it has no prereq row.
course natural full outer join prereq: which rows have nulls?
CS-315 (prereq_id null) and CS-347 (title, dept_name and credits null).
What is a view?
Any relation that is not of the conceptual model but is made visible to a user as a "virtual relation"; it hides certain data from certain users.
Does create view evaluate the query and store a new relation?
No — a view definition causes the saving of an expression, which is substituted into queries using the view.
When does view v1 depend directly on v2? When is a view recursive?
v1 depends directly on v2 if v2 is used in the expression defining v1. A view is recursive if it depends on itself.
View expansion: the loop and when it terminates
Repeat: find a view relation vi in e1 and replace it by the expression defining vi, until no view relations remain. It terminates as long as the view definitions are not recursive.
Conditions for a view that most SQL implementations can update
One database relation in from; only attribute names in select (no expressions, aggregates or distinct); unlisted attributes can be set to null; no group by or having.
insert into faculty values ('30765', 'Green', 'Music') becomes…
An insertion of ('30765', 'Green', 'Music', null) into instructor.
Materialized view
A physical table containing all the tuples of the view's query result; it becomes out of date when the underlying relations are updated, so it must be maintained.
How does an SQL transaction end, and what is the default on most databases?
With commit work or rollback work. By default, each SQL statement commits automatically (auto commit can be turned off for a session).
Atomic transaction
Either fully executed or rolled back as if it never occurred.
What do integrity constraints guard against?
Accidental damage to the database — they ensure that authorized changes do not result in a loss of data consistency.
unique (A1, …, Am): what does it declare, and may the values be null?
The attributes form a candidate key; candidate keys are permitted to be null (unlike primary keys).
Referential integrity
A value that appears in one relation for a given set of attributes also appears for a certain set of attributes in another relation.
Alternatives to cascade in a foreign key
set null and set default (e.g., on delete …, on update …).
Are subqueries in check clauses and create assertion supported?
Subqueries in check: not supported by pretty much any database (alternative: triggers). create assertion: also not supported by anyone.
date, time, timestamp, interval
date: year, month, date; time: hours, minutes, seconds; timestamp: date plus time of day; interval: a period of time (date − date gives an interval).
What is an index for?
A data structure used to speed up access to records with specified values for index attributes (e.g., create index studentID_index on student(ID)).
Type vs domain in SQL
They are similar, but domains can have constraints, such as not null, specified on them.
blob vs clob; what does a query return for one?
blob: binary large object; clob: character large object. A query returns a pointer rather than the large object itself.
Read, Insert, Update, Delete authorization
Read: reading, not modification. Insert: new data, not modifying existing data. Update: modification, not deletion. Delete: deletion of data.
Index, Resources, Alteration, Drop authorization
Index: create/delete indices. Resources: create new relations. Alteration: add/delete attributes. Drop: delete relations.
Does a privilege on a view give privileges on its underlying relations?
No — granting a privilege on a view does not imply granting any privileges on the underlying relations.
Revoking a privilege: three rules
Revoking from public leaves those granted it explicitly; a privilege granted twice by different grantees may be retained; all privileges that depend on the revoked one are also revoked.
grant teaching_assistant to instructor — what happens?
The role instructor inherits all privileges of teaching_assistant (roles can be granted to other roles).
references privilege and with grant option
references allows creating a foreign key (grant reference (dept_name) on department to Mariano); with grant option lets the user transfer the privilege.
The 5 steps in building a database for an application
1. Understand the real-world domain; 2. specify it with a conceptual model (ER); 3. translate to the DBMS model (relational); 4. create the schema (DDL); 5. load data (DML).
In the database design steps, logical design vs physical design
Logical: how data will be structured logically (entities, attributes, keys, relationships). Physical: how data will be stored (storage, performance).
Why work through conceptual problems in the data model?
A data model is more generalized and abstract than a database design, and it is easier to change a data model than a database design.
The three basic concepts of the ER model
Entity sets, relationship sets, attributes.
Entity vs entity set
Entity: an object that exists and is distinguishable from other objects. Entity set: a set of entities of the same type that share the same properties.
Relationship set (definition)
A mathematical relation among n ≥ 2 entities, each taken from entity sets: {(e1, …, en) | e1 ∈ E1, …, en ∈ En}.
Can a relationship set have attributes? Example?
Yes — advisor may have the attribute date (when the student started being associated with the advisor).
proj_guide: what degree, between which entity sets?
Ternary — between instructor, student and project.
The four mapping cardinalities of a binary relationship set
One to one, one to many, many to one, many to many.
Directed line (→) vs undirected line (—) in an E-R diagram
→ signifies "one"; — signifies "many".
advisor one-to-many (instructor to student): what does it allow?
An instructor is associated with several (including 0) students; a student with at most one instructor.
Composite vs simple attribute
Composite: can be subdivided to yield additional attributes (address, phone number). Simple: cannot be subdivided (age, gender, marital status).
Best way to handle a multivalued attribute
Create a new entity composed of the original multivalued attribute's components (several new attributes can cause structural problems).
Derived attribute (with examples)
An attribute whose value is calculated from other attributes — age from date of birth; total cost = quantity ordered × unit price.
In an entity box, what do { phone_number } and age ( ) mean?
{ phone_number }: a multivalued attribute. age ( ): a derived attribute.
The two conditions for a weak entity
1. It is existence-dependent on its parent entity. 2. It inherits at least part of its primary key from its parent entity.
Existence independence
The entity exists apart from all of its related entities — a strong (regular) entity.
How is a weak entity set drawn?
A double rectangle; its discriminator is underlined with a dashed line; the identifying relationship set is a double diamond.
Rectangle, diamond, underline in an E-R diagram
Rectangle: entity set (attributes inside). Diamond: relationship set. Underline: primary key attributes.
What are roles in a relationship?
Labels for the part each occurrence of an entity set plays when the entity sets need not be distinct — in prereq, "course_id" and "prereq_id".
Naming rule for entity names
Descriptive of the objects, using terminology familiar to the users, and singular.
Total vs partial participation
Total (mandatory, minimum 1, double line): every entity participates in at least one relationship. Partial (optional, minimum 0): some entities may not participate.
Chen l..h: what do minimum 1, maximum 1 and maximum * mean?
Minimum 1: total participation. Maximum 1: at most one relationship. Maximum *: no limit.
Crow's foot: oval vs vertical hash mark
Oval: minimum 0 (optional participation). Vertical hash mark: minimum 1 (mandatory participation).
How is a many-to-many relationship set reduced to a schema?
A schema with the primary keys of the two participating entity sets and any descriptive attributes — advisor = (s_id, i_id).
Weak entity set → schema
A table that includes a column for the primary key of the identifying strong entity set — section(course_id, sec_id, sem, year).
Multivalued attribute M of entity E → schema
A separate schema EM with the primary key of E and an attribute for M; each value is a separate tuple — inst_phone = (ID, phone_number).
Where does the foreign key go for a one-to-many relationship that is total on the many-side?
In the "many" side: add an attribute holding the primary key of the "one" side (dept_name in instructor).
One-to-one relationship set: which side gets the extra attribute?
Either side can be chosen to act as the "many" side.
Is a schema for the relationship between a weak entity set and its identifying strong entity set needed?
No — it is redundant (section already contains the attributes of sec_course).
How many arrows may leave a ternary relationship?
At most one — more than one arrow has two possible meanings, so it is outlawed.
Why replace parents (child, father, mother) with father and mother?
Two binary relationships allow partial information (e.g., only the mother being known).
Specialization vs generalization
Specialization: top-down — sub-groupings become lower-level entity sets. Generalization: bottom-up — entity sets with the same features combine into a higher-level set. They are inversions, drawn the same way (ISA triangle).
Attribute inheritance
A lower-level entity set inherits all the attributes and relationship participation of the higher-level entity set to which it is linked.
Partial vs total completeness; which is the default?
Partial: not every supertype occurrence is in a subtype (the default). Total: every supertype occurrence is in at least one subtype.
Disjoint vs overlapping subtypes: implementation
Disjoint (d): one subtype discriminator attribute in the supertype. Overlapping (O): one discriminator attribute for each subtype.
Specialization schemas: drawback of method 1 and of method 2
Method 1 (higher-level key + local attributes): accessing two relations for an employee's information. Method 2 (all attributes in each schema): name, street, city stored redundantly for people who are both students and employees.
Aggregation: what is it, and what is the eval_for schema?
Treating a relationship as an abstract entity, allowing relationships between relationships. eval_for (s_ID, project_id, i_ID, evaluation_id); proj_guide becomes redundant.
UML class diagrams vs E-R diagrams
UML class diagrams correspond to E-R diagrams, with several differences — e.g., the position of the cardinality constraint is reversed.
The seven steps of mapping ER to relations
1 regular entity sets; 2 weak entity sets; 3 binary 1:1; 4 binary 1:N; 5 binary M:N; 6 multivalued attributes; 7 n-ary relationship sets.
Step 1: regular (strong) entity set
Create a relation R that includes all the simple attributes of E.
Step 2: weak entity set
Create a relation with all its simple attributes, and include the primary key of the owner as foreign key attributes — DEPENDENT (Essn, name, Sex, Birthdate, Relationship).
The three approaches for a binary 1:1 relationship
(1) Foreign key approach; (2) merged relation option; (3) cross-reference (relationship relation) option.
1:1 foreign key approach: which relation gets the foreign key?
Better to choose the entity set with total participation in R to play the role of S (the relation that includes the other's primary key).
When is the merged relation option appropriate for a 1:1 relationship?
When both participations are total.
MANAGES (1:1): how is it mapped?
EMPLOYEE's primary key goes into DEPARTMENT as Mgr_ssn, with Start_date as Mgr_start_date.
Step 4: binary 1:N relationship
In the relation S at the N-side, include the primary key of the other entity set as a foreign key, plus the relationship's simple attributes.
SUPERVISION (1:N recursive on EMPLOYEE): how is it mapped?
The primary key of EMPLOYEE is added to EMPLOYEE itself as a foreign key, Super_ssn.
Step 5: binary M:N relationship
Create a new relation S with the primary keys of the participating entity sets as foreign keys and any simple attributes — WORKS_ON (Essn, Pno, Hours).
Step 6: multivalued attribute A of an entity with key K
Create a new relation R whose primary key is the combination of A and K — DEPT_LOCATIONS (Dnumber, Dlocation).
Step 7: n-ary relationship (with the example)
Create a new relation with the primary keys of all participating entity sets as foreign keys and any simple attributes — SUPPLY (Sname, Proj_name, Part_no, Quantity).
ER → relational: 1:1/1:N, M:N, n-ary
1:1 or 1:N: a foreign key. M:N: a "relationship" relation and two foreign keys. n-ary: a "relationship" relation and n foreign keys.
ER → relational: composite and multivalued attributes
Composite: a set of simple component attributes. Multivalued: a relation and a foreign key.
Option 8A
Multiple relations — superclass and subclasses: L for C with {k, a1…an}; Li for each subclass with {k} ∪ its attributes. Works for any specialization.
Option 8B and when it works
Subclass relations only, each with its attributes ∪ {k, a1…an}. Only works for total subclasses; only recommended if disjoint.
Option 8C and when it works
A single relation with all attributes plus one type (discriminating) attribute t naming each tuple's subclass. Works only for disjoint subclasses.
Option 8D and its example
A single relation with all attributes plus a Boolean type attribute for each subclass; used for overlapping subclasses — PART with Mflag and Pflag.
The four informal measures of quality for relation schema design
1. Semantics of the relation attributes; 2. reducing redundant information in tuples; 3. reducing null values in tuples; 4. disallowing spurious tuples.
The three update anomalies
Insertion anomalies, deletion anomalies, modification anomalies.
Three reasons for nulls
Attribute not applicable or invalid; attribute value unknown (may exist); value known to exist but unavailable.
Guideline #4 (spurious tuples)
Relations should satisfy the lossless join condition: no spurious tuples should be generated by joining any relations.
What is normalization?
Decomposing unsatisfactory "bad" relations by breaking up their attributes into smaller relations.
When does α → β hold on R?
If and only if, for any legal relation r(R), whenever two tuples agree on α they also agree on β.
r(A, B) = (1,4), (1,5), (3,7): A → B? B → A?
A → B does NOT hold; B → A does hold.
Determinant and dependent in A → B
A is the determinant; B is the dependent — each value of A is associated with exactly one value of B.
Superkey and candidate key in terms of FDs
K is a superkey iff K → R. K is a candidate key iff K → R and no proper subset α of K has α → R.
What does 1NF disallow?
Composite attributes, multivalued attributes and nested relations — only single atomic values are permitted.
EMP_PROJ (Ssn, Ename, {Phone#}) in 1NF
EMP_PROJ1 (Ssn, Ename) and EMP_PROJ2 (Ssn, Phone#).
Prime attribute
An attribute that is a member of the primary key K.
Full vs partial functional dependency
Full: removing any attribute from the determinant breaks the FD. Partial: some attributes can be removed and the FD still holds.
{SSN, PNUMBER} → HOURS and {SSN, PNUMBER} → ENAME: full or partial?
HOURS: full (neither SSN nor PNUMBER alone determines it). ENAME: partial (SSN → ENAME holds).
2NF (definition)
Every non-prime attribute is fully functionally dependent on the primary key — no partial dependency on the primary key.
When can the 2NF test be skipped?
When the primary key contains a single attribute.
Transitive functional dependency
X → Y is transitive if some set Z, neither a primary nor a candidate key, has X → Z and Z → Y — e.g., SSN → DNUMBER → DMGRSSN.
3NF (definition)
In 2NF, and no non-prime attribute is transitively dependent on the primary key.
BCNF (definition)
Whenever an FD X → A holds in R, X is a superkey of R.
Is every 3NF relation in BCNF?
No — every BCNF relation is in 3NF, but there exist relations in 3NF that are not in BCNF.
{Student, course} → Instructor; Instructor → Course: normal form and decomposition
In 3NF, not BCNF (Instructor is not a superkey). Decompose into {Student, Instructor} and {Instructor, Course}.
Car_Sale: why is it not in 2NF?
Car# → Date_sold and Salesman# → Commission% are not full FDs on the primary key (Car#, Salesman#) — they are partial dependencies.
Volatile vs non-volatile storage
Volatile loses its contents when power is switched off (cache, main memory). Non-volatile keeps them (secondary and tertiary storage, battery-backed main memory).
Flash memory: reads, writes, power failure
Data survives power failure; reads are roughly as fast as main memory; writes are slow (few microseconds) and erase is slower.
Magnetic disk: role and access type
The primary medium for long-term storage (typically the entire database); direct-access — data can be read in any order, unlike tape.
Tape storage: use and access
Used primarily for backup and archival data; sequential-access — much slower than disk; very high capacity.
The storage hierarchy from fastest to slowest
Cache, main memory, flash memory, magnetic disk, optical disk, magnetic tapes.
Primary, secondary and tertiary storage
Primary: fastest, volatile (cache, main memory). Secondary (on-line): non-volatile, moderately fast (flash, magnetic disks). Tertiary (off-line): non-volatile, slow (tape, optical).
Sector and cylinder
Sector: a division of a track, the smallest unit of data that can be read or written (typically 512 bytes). Cylinder i: the ith track of all the platters.
Three things the disk controller does to protect data
Computes and attaches checksums to each sector; reads back a sector after writing it; remaps bad sectors.
SAN vs NAS
SAN: many disks connected by a high-speed network to servers. NAS: networked storage with a file system interface (networked file system protocol), not a disk interface.
Access time = ?
Seek time + rotational latency — the time from issuing a request until data transfer begins.
Average seek time and average rotational latency
Each is 1/2 of its worst case (average seek would be 1/3 if all tracks had the same number of sectors).
MTTF of 1,200,000 hours for 1000 new disks means…
On average, one disk will fail every 1200 hours. MTTF decreases as the disk ages.
Block size trade-off
Smaller blocks: more transfers from disk. Larger blocks: more space wasted due to partially filled blocks (typical 4–16 KB).
Why is writing to a log disk very fast?
It writes a sequential log of block updates, so no seeks are required.
RAID: what does it stand for, and what does it provide?
Redundant Arrays of Independent (originally Inexpensive) Disks — a view of a single disk of high capacity and speed (parallel disks) and high reliability (redundant data).
100 disks, each MTTF 100,000 hours: system MTTF?
1000 hours (about 41 days) — some disk out of many fails much sooner than one specific disk.
Mirroring (shadowing)
Duplicate every disk: every write goes to both disks, reads from either; data is lost only if a disk and its mirror both fail before repair.
Block-level striping with n disks
Block i of a file goes to disk (i mod n) + 1.
RAID 0 and RAID 1
RAID 0: block striping, non-redundant (data loss not critical). RAID 1: mirrored disks with block striping — best write performance; popular for log files.
RAID 4: scheme and weakness
Block-interleaved parity with the parity block on a separate disk; the parity disk is a bottleneck for independent block writes.
RAID 5 vs RAID 4
RAID 5 distributes data and parity among all N + 1 disks, giving higher I/O rates and avoiding the parity-disk bottleneck; it subsumes level 4.
RAID 6
P+Q redundancy — like level 5 with extra redundant information to guard against multiple disk failures; better reliability at higher cost.
RAID 1 or RAID 5: which for what?
Level 1: high update environments such as log disks (better write performance). Level 5: low update rate and large amounts of data.
Hot swapping and data scrubbing
Hot swapping: replacing a disk while the system runs, without power down. Data scrubbing: continually scanning for latent failures and recovering from copy/parity.
Where does fixed-length record i start?
At byte n × (i − 1), where n is the size of each record.
Free list
The file header stores the address of the first deleted record; each deleted record stores the address of the next — pointers linking all free records.
Variable-length records: how are variable attributes and nulls stored?
Variable-length attributes as a fixed-size (offset, length), with data after the fixed-length attributes; nulls by a null-value bitmap.
Slotted page header and pointers
Header: number of record entries, end of free space, location and size of each record. Pointers point to the header entry, not the record, so records can move.
Heap vs sequential vs hashing file organization
Heap: records anywhere, no ordering. Sequential: ordered by the search key. Hashing: a hash function on an attribute gives the block.
Sequential file: inserting when there is no free space
Insert the record in an overflow block and update the pointer chain; reorganize the file from time to time.
Multitable clustering of department and instructor: good and bad for
Good for department ⋈ instructor and one department with its instructors; bad for queries involving only department (and gives variable size records).
What does the data dictionary (system catalog) store?
Metadata: relations and their attributes (names, types, lengths), views, integrity constraints, user and accounting information including passwords, statistics (tuples per relation), physical organization and location, indices.
When is a replaced buffer block written back to disk?
Only if it was modified since the most recent time it was written to/fetched from the disk.
Why can LRU be a bad buffer-replacement strategy?
For access patterns with repeated scans of data, e.g., a nested-loops join; a mixed strategy with hints from the query optimizer is preferable.
Pinned block, toss-immediate, MRU
Pinned: not allowed to be written back to disk. Toss-immediate: free the block once its final tuple is processed. MRU: pin the block in use; after its final tuple it is unpinned and becomes the most recently used block.