Q3Data Base Management System

(a) Physical vs logical data independence

Data independence refers to the capacity of a database system to let one level of its architecture change without requiring changes at the next higher level. The DBMS achieves this through the three-schema (ANSI-SPARC) architecture, which separates a database into three distinct levels of description.

• External level: consists of multiple external schemas (or views), each tailored to the needs of a particular group of users or applications, showing only the portion of data relevant to them.
• Conceptual level: a single conceptual schema describing the overall logical structure of the entire database for the whole community of users, independent of any particular application and independent of physical storage details.
• Internal level: describes the physical storage structure of the database - the actual files, indexes, access paths, data types, and storage allocation used on disk.

Physical data independence is the capacity to change the internal (physical) schema - for example switching from a heap file organization to a hashed one, adding or dropping an index, reorganizing storage across different disks, or changing block sizes - without having to change the conceptual schema or any external schema/application program. Because application programs are written against the conceptual/external level and not against physical storage details, the DBA can tune physical storage for performance at any time with no impact on existing code. This is the most commonly and easily achieved form of independence, since the mapping between the conceptual and internal levels is maintained solely by the DBMS.

Logical data independence is the capacity to change the conceptual schema - for example adding a new entity type, adding new attributes to an existing entity, splitting or merging relations, or restructuring relationships - without having to rewrite existing external schemas or the application programs built on those external views. This is harder to achieve than physical data independence because external views are more closely tied to the conceptual schema; the mapping between the external and conceptual levels must be carefully maintained so that, for instance, adding a new column to a base table does not break existing queries or views that never referenced that column.

In short, physical data independence insulates users from changes between the internal and conceptual levels, while logical data independence insulates users from changes between the conceptual and external levels; both together allow the database schema to evolve over time while keeping existing applications stable.

(b) Set operators of relational algebra

Relational algebra provides four binary operators borrowed from mathematical set theory that combine two relations to produce a new relation. The first three - union, intersection, and set difference - require the two operand relations to be union-compatible, meaning they must have the same number of attributes and each corresponding pair of attributes must be drawn from the same domain.

• Union (R UNION S, symbol: the cup operator): produces a relation containing all tuples that appear in R, in S, or in both, with duplicate tuples eliminated. Example: if R lists students enrolled in a Database course and S lists students enrolled in a Networks course, R UNION S gives all students enrolled in at least one of the two courses.
• Intersection (R INTERSECT S, symbol: the cap operator): produces a relation containing only the tuples that appear in both R and S. Using the same example, R INTERSECT S gives students enrolled in both Database and Networks.
• Set difference (R MINUS S, symbol: the minus operator): produces a relation containing tuples that appear in R but not in S. R MINUS S gives students enrolled in Database but not in Networks; note that difference is not commutative, since S MINUS R would instead give students in Networks but not Database.
• Cartesian product (R TIMES S, symbol: the cross/times operator): does not require union-compatibility; instead it combines every tuple of R with every tuple of S, producing a relation whose degree is the sum of the degrees of R and S and whose cardinality is the product of the cardinalities of R and S. For example, if R is a Customer relation with 10 tuples and S is a Car relation with 20 tuples, R TIMES S produces 200 tuples, each pairing one customer row with one car row; this operator is mainly useful as the basis for defining join operations by following it with a selection condition.

These set operators, together with the fundamental operators selection, projection, and rename, form a complete basis from which more advanced relational algebra operators such as join and division can be derived.

The union-compatibility requirement for union, intersection, and set difference deserves emphasis, since it is a frequent source of confusion. Two relations R and S are union-compatible only if they have the same degree (same number of attributes) and, for each position, the domain of the attribute in R matches the domain of the corresponding attribute in S; the attribute names themselves do not need to match, only their domains and position. For example, a relation STUDENT_A(Name, Age) and a relation STUDENT_B(FullName, Age) are union-compatible as long as Name and FullName share the same underlying domain (say, character strings) and Age shares the same domain (say, integers) in both. If the relations are not union-compatible - for instance, if one has three attributes and the other has two, or if corresponding attributes have incompatible domains - the union, intersection, and set-difference operations are undefined and cannot be applied directly.

Cartesian product, by contrast, places no such restriction on its operand relations, precisely because it does not attempt to match up corresponding tuples; instead it simply pairs every tuple in the first relation with every tuple in the second, regardless of whether the two relations describe similar kinds of entities. Because of this, Cartesian product is rarely useful on its own - a raw Cartesian product between Customer and Car, for example, would pair every customer with every car, including cars they do not own, producing a huge and mostly meaningless result. Its practical value comes from combining it with a selection condition that restricts the paired tuples to only those satisfying a matching condition (such as Customer.CustomerID = Car.OwnerID), which is exactly how the theta-join and natural-join operators of relational algebra are formally defined in terms of the more primitive Cartesian product and selection operators.