12. DB Design Flashcards
2 main components of E-R models
entities and relationships
Entities in E-R models - def.
How are they depicted?
a real-world object described by a set of attribute values. An entity is usually depicted as a rectangle in our E-R model. In addition, the attributes/fields associated with the entity are depicted as ovals.
Relationships in E-R models - def.
How are they depicted?
association among two or more entities.
A relationship is usually depicted as a diamond in our E-R model. The attributes associated with the relationship are depicted as ovals.
Many-to-many relationships in E-R models - describe, how are they depicted?
each entity can participate in 0 or more times in the relationship and vice versa.
For example, many employees can work in many departments (0 or more) and departments can have many employees (0 or more).
Depicted: thin line
1-to-many relationship in E-R model
describe, constraint type, how is it depicted?
key constraint
E.g. each department has at most one manager (0 or 1) while employees can be managers for many (0 or more) departments
depicted: thin arrow
at least one relationship in E-R model
describe, constraint type, how is it depicted?
participation constraint
depicted: thick line (or arrow if both at least and at most one)
Example: one denotes that each employee works in at least one department. The other denotes that each department has at least one employee.
Weak entities in E-R model - describe, how are they depicted?
A weak entity can be identified uniquely only by considering the primary key of another (owner) entity. Owner entity set and weak entity set must participate in a one-to-many relationship set (one owner, many weak entities). Weak entity set must have total participation in this identifying relationship set. We depict a weak entity by bolding the rectangle and relationship as shown below. In addition, weak entities have only a “partial key” (dashed underline). In the example below, we say that every dependent is uniquely identified by their pname and an employees’ ssn and that each employee has 0 or more dependents attached to them.
Functional Dependencies - def.
Why do we need to find them?
A functional dependency X −→ Y means that the X column determines Y column in a table R. This means given any two tuples in table R, if their X values are the same, then their Y values must be the same (but not vice versa)
Functional dependencies help to determine redundancies in the schema. Redundancies lead to wasted storage and insert/delete/update anomalies, so we want to avoid them where possible.
What is a superkey?
A superkey is a set of columns that determine all the columns in the table. If X is a superkey of R, then X → R.
What is a candidate key?
A candidate key is a set of columns that determine all the columns in the table such that if we remove any of the columns in a candidate key, the resulting set will not be a superkey of the relation. If X is a candidate key of R, then X → R and for every strict subset Y ⊂ X, Y does not determine R.
For example, if columns K, L are the columns in a table and K is a primary key of the table (aka column K alone determines all the columns in the table) then KL is superkey and K is a superkey and a candidate key
Closure of a set of functional dependencies - def.
the closure of F, denoted as F+, is the set of all FDs that are implied by F. In broader terms, a closure is the full set of table relationships that can be determined from known FDs.
Boyce–Codd normal form - explain
What is BCNF decomposition?
If a relational schema is in BCNF then all redundancy based on functional dependency has been removed.
A relational schema R is in Boyce–Codd normal form if and only if for every one of its dependencies X → Y, at least one of the following conditions hold:
1) X → Y is a trivial functional dependency (Y ⊆ X),
2) X is a superkey for schema R.
BCNF decomposition is breaking up a relation that is not in BCNF into several relations that are all in BCNF
Lossy and lossless relations decomposition - explain
lossless decomposition - original relation can be reconstructed from decomposed relations.
lossy - original relation can’t be reconstructed from decomposed relations, some extra garbage data is generated.
Example:
dependency preserving decompositions - explain
If we make an insertion to a table and need to check that functional dependencies are still satisfied, we may have to join together the tables we decomposed, making every insertion we do costly.
We can avoid this problem through dependency preserving decompositions. Suppose we decompose R into X, Y, and Z. This decomposition is dependency preserving if enforcing FDs individually on each of X, Y, and Z implies that all FDs that held on R must also hold. Now, when making an insertion to a table, we will only need to check the FDs are satisfied on that relation (avoiding joins between decomposed relations) since this will be sufficient for enforcing all FDs that held on the original relation
First normal form - explain
The relation is in the first normal form if it does not contain any composite or multi-valued attribute, i.e. every attribute in that relation is singled valued attribute.
If a relation contains a composite or multi-valued attribute, it violates the first normal form
