Relational Model and Scheme

Relational Model

• A relation R features attributes A = {A1, A2, ..., An}.
• It is defined over 'n' domains D = {D1, D2, ..., Dn}.
• The domains are not necessarily distinct.
• The relation uses values {Dom₁, Dom2, ..., Domn}.
• It is a finite, time-varying set of n-tuples (d1, d2, ..., d₁) where each 'di' belongs to 'Domi'.
• There are constraints such as A1 ⊆ D1, A2 ⊆ D2, ..., An⊆ Dn.
• Represented as R(A1, A2, ..., An) or R(A1: D1, A2: D2, ..., An: Dn).
• An instance of R at a given time is a set of n-tuples: {(A1: d₁, A2: d2, ..., An: dn) | d₁ ∈ Dom₁, d₂ ∈ Dom2, ..., dn ∈ Domn}.
• It has a tabular structure where R is the table heading, attributes are table columns, and each tuple is a row.

Relational Scheme

• A relational scheme defines a set of attributes.
• Example: EMP(ENO, ENAME, TITLE, SAL, PNO, RESP, DUR) and PROJ (PNO, PNAME, BUDGET)

Relational Database Scheme

• A relational database scheme is a set of relation schemes.
• It is a set of sets of attributes.
• A relation over a scheme R = {A1, ..., An} is a subset of the Cartesian product of the domains of all attributes: r ⊆ Dom₁ × Dom₂ × ... × Domn.

Domains

• A domain is a type in the programming language sense.
• Examples: Name: String, Salary: Real.
• Domain values are a set of acceptable values for a variable of a given type.
• Examples: CdnNames = {...}, ProfSalary = {45,000 - 150,000}.
• Simple/Composite domains can include address which is Street name+street number+city+province+ postal code
• Binary operations can be performed, such as comparisons and addition, where there is domain compatibility
• Full support for domains is not fully provided in many current relational DBMSs.

Relation Keys

• Underlined attributes are relation keys and tuple identifiers.
• Tabular form is used

Repetition Anomaly

• The NAME, TITLE, and SAL attribute values are repeated for each project an employee is involved in
• This is a waste of space and complicates updates.

Update Anomaly

• If any attribute of a project, like an employee's salary (SAL), is updated, multiple tuples must reflect the change.

Insertion Anomaly

• It might not be possible to store information about a new project until an employee is assigned to it.

Deletion Anomaly

• If an engineer, who is the only employee on a project, leaves the company, all information about that project might be lost.
• Many tuples may be deleted.

Normalization

• Improves each relation individually based on desired characteristics.
• Involves normal forms.
• Normalization is a process of concept separation using a top-down approach by subsequent refinements and decompositions.
• Avoid combining unrelated sets of facts in one table. Each relation should contain an independent set of facts.
• Universal relation assumption is applied.
• This includes 1NF to 3NF and 1NF to BCNF.

Normalization Issues

• How to decompose a schema into a desirable normal form.
• Defined by lossless recomposability and dependency preservation.
• Lossless decomposition means no information loss.
• Reconstructability means the ability to recover the original relation with no spurious joins.
• Dependency preservation means the constraints holding on the original relation should be enforceable by the decomposed relations.
• Processing time may increase due to joins and there is denormalization.

Functional Dependence

• Relation R is defined over U = {A1, A2, ..., An} where X ⊆ U, Y ⊆ U.
• For all pairs of tuples t1 and t2 in any legal instance of relation scheme R, if t1[X] = t2[X] ⇒ t1[Y] = t2[Y], then X → Y holds in R.
• In relation EMP: (ENO, PNO) → (ENAME, TITLE, SAL, DUR, RESP)
• In relation PROJ: PNO → (PNAME, BUDGET)

Normal Forms Based on Functional Dependencies

• 1NF: Eliminates relations within relations or relations as attributes of tuples
• First Normal Form (1NF): Eliminates the partial functional dependencies of non-prime attributes to key attributes.
• Second Normal Form (2NF): Eliminates the transitive functional dependencies of non-prime attributes to key attributes.
• Third Normal Form (3NF): Eliminates the partial and transitive functional dependencies of prime (key) attributes to key.
• Boyce-Codd Normal Form (BCNF).

Relational Algebra

• Specifies how to obtain the result using a set of operators.
• Expressed as <Operator>parameters(〈Operands) → (Result)
• The operands are relations and result is also a relation.

Relational Algebra Operators

Fundamental

• Selection
• Projection
• Union
• Set difference
• Cartesian product

Additional

• Intersection
• θ-join
• Natural join
• Semijoin
• Division

Union Compatibility

• Union operations must have the same degree
• Corresponding attributes must be defined over the same domain

Selection

• Produces a horizontal subset of the operand relation.
• General form: σF(R) = {t | t ∈ R and F(t) is true}.
• R is a relation, t is a tuple variable, and F is a formula.
• F consists of operands (constants or attributes), arithmetic comparison operators (<, >, =, ≠, ≤, ≥), and logical operators (∧, ∨, ¬).

Projection

• Produces a vertical slice of a relation.
• General form: ΠA1,...,An(R) = {t[A1,..., An] | t ∈ R}.
• R is a relation, t is a tuple variable, and {A1,..., An} is a subset of R's attributes.
• Projection can generate duplicate tuples, with this feature being available in commercial systems and SQL.

Union

• Similar to set union.
• General form: R ∪ S = {t | t ∈ R or t ∈ S}.
• R and S are relations, t is a tuple variable.
• The result contains tuples that are in R or S but not both (duplicates removed), R and S must be union-compatible.

Set Difference

• General form: R - S = {t | t ∈ R and t ∉ S}.
• R and S are relations, t is a tuple variable.
• Result contains all tuples that are in R but not in S, R - S ≠ S - R.
• R and S must be union-compatible.

Cartesian (Cross) Product

• For relations R of degree k1 and cardinality n1, and S of degree k2 and cardinality n2.
• Cartesian product: R × S = {t [A1,...,Ak1, Ak1+1,...,Ak1+k2] | t[A1,………,Ak1] ∈ R and t[Ak1+1,...,Ak1+k2] ∈ S}.
• The result of R × S is a relation of degree (k1 + k2) and consists of all (n1 * n2)-tuples.
• Each tuple is a concatenation of one tuple of R with one tuple of S.

0-Join

• Derived from Cartesian product.
• Primary classification is between inner join and outer join.
• General form: R ⋈F(R.Ai, S.Bj) S = {t[A1,...,An, B1,...,Bm] | t[A1,...,An] ∈ R and t[B1,...,Bm] ∈ S and F(R.Ai, S.Bj) is true}.
• R and S are relations, t is a tuple variable, and F (R.Ai, S.Bj) is a selection formula
• A derivative of Cartesian product: R ⋈F S = σF(R × S).

Types of Join

Equi Join

• Is a special case of a 0-join
• The formula F only contains equality (=) as an arithmetic operator.

Natural Join

• It is a equi-join of two relations R and S over an attribute (or attributes) common to both R and S
• It projects out one copy of those attributes
• R ⋈ S = ΠR∪SσF(R × S)

Outer Join

• Inner join requires that the joined tuples from two operand relations satisfy the join predicate, outer does not.
• It ensures that tuples from one or both relations that do not satisfy the join condition still appear in the final result with other relation's attribute values set to NULL.
• Three types: left (tuples from left operand are always in the result), ring (tuples from the right operand relation are always in the result), and full (Tuples from both relations are always in the result).

Semijoin

• Semijoin of relation R, defined over attributes A, by relation S, defined over attributes B: a subset of tuples of R that participate in the join of R with S.
• RF S = ΠA(RF S) = ΠA(R) ⋈ ΠA∩B(S) = R ⋈F ΠA∩B(S)
• Decreases the number of tuples needed to form the join.
• Results in a decreased number of secondary storage accesses by making better use of memory
• Reduces the amount of data transmitted between sites to evaluate a query in a DDB
• The resultant relation does not have the PAY attribute and is therefore smaller.

Division (Quotient)

• For relations R of degree 'k1' and S of degree 'k2', where A (attributes of R) and B (attributes of S), and B is a subset of A.
• T = R ÷ S gives T of degree k1-k2 where Y = A-B. For a tuple 't' to appear in T, the values in 't' must appear in R in combination with every tuple in S.
• Derivation: R ÷ S = ΠY(R) – ΠY((ΠY(R) × S) – R)

Relational Calculus

• Specifies the characteristics of the final result.
• Includes tuple relational calculus and domain relational calculus.

Tuple Relational Calculus

• Queries of the form {t | F{t}} where 't' is a tuple variable, and F is a well-formed formula.
• Includes atomic formulas and tuple variable membership expressions.
• An atomic formula is R.t or R(t) where tuple 't' belongs to relation R.
• Conditions are s[A] θ t[B] or s[A] θ c where 's' and 't' are tuple variables, 'A' and 'B' are components of 's' and 't', 'c' is a constant, and θ is a comparison operator.
• SQL is an example of tuple relational calculus, at least in simple examples

Domain Relational Calculus

• Queries of the form {x1, x2, ..., xn | F(x1, x2, ..., xn)}
• F is a well-formed formula in which x1, x2, ..., xn are the free variables.
• QBE is an example

Computer Network

• An interconnected collection of autonomous computers that exchange information among themselves.
• Components are hosts (nodes, end systems), switches, and communication links.

Internet

• A network of networks consisting of clients, intranets, ISP networks, and servers.

Types of Networks (by scale)

Wide Area Network (WAN)

• Distance between nodes > 20km, can reach thousands of kms
• Incurs long delays due to distances
• Heterogeneous transmission media
• Speeds of 150Mbps to 10Gbps (OC192 backbone).

Local Area Network (LAN)

• Limited geographic scope (typically < 2km)
• Speeds of 10-1000 Mbps
• Short delays and low noise

Metropolitan Area Network (MAN)

• In between LAN and WAN

Types of Networks (by topology)

Irregular

• No consistent configuration.
• E.g., the Internet.

Bus

• Typical in LANs such as Ethernet
• Uses Carrier Sense Medium Access with Collision Detection (CSMA/CD).

Others

• Star
• Ring
• Mesh

Communication Schemes

Point-to-point (unicast)

• One or more direct/indirect links between each pair of nodes.
• Only communicates between two nodes
• Sender and receiver are identified by addresses in the message header.
• Message leverages one of multiple links between the sender and receiver using switching or routing.

Broadcast (multi-point)

• Messages are transmitted over a shared channel.
• Includes multi-cast, where the message is sent to a subset of nodes.

Communication Alternatives

• Twisted pair
• Coaxial
• Fiber optic cable
• Satellite
• Microwave
• Wireless.

Data Communication

• Hosts are connected by "links," each of which can carry one or more "channels."
• A "link" is a physical entity, whereas a "channel" is a logical one.
• The amount of data transmitted over the channel is called "bandwidth."
• Alternative messaging schemes include packet switching.
• Messages are divided into fixed size packets routed from source to destination when packet switching
• A dedicated channel between the sender and the receiver for the session with circuit switching

Communication Protocols

• Software that ensures reliable and efficient communication between hosts.
• Arranged in a layered architecture known as the protocol stack or protocol suite.
• Transmission Control Protocol/Internet Protocol(TCP/IP) is the best-known which is used in the internet