Data Intensive Systems: Lecture 1

From Data to a DBMS

Modern software is useful only when data can be stored, shared, and queried correctly over time. The starting point is the difference between raw facts and meaning.

Data. Raw facts, used as input for reasoning and computation. Data may be useful, irrelevant, or redundant; on its own it carries no meaning.

Information. Data that has been organized and processed so that it is relevant to a problem and actionable for a decision; information in turn supports knowledge.

$\text{data} \xrightarrow{\;\text{organize}+\text{process}\;} \text{information}$

Once facts carry meaning, they need structure.

Database. A large, integrated, structured collection of data, modeling a real-world enterprise. It records entities, the kinds of objects we store data about, and relationships, the meaningful associations between them.

A university database stores students, courses, and professors, together with who enrolls in which course and who teaches it.

A database on its own is passive; software has to manage it.

Database Management System (DBMS). A software system that stores, manages, and provides access to databases. Its core role is efficient, reliable, convenient, and safe multi-user access to massive persistent data.

$\text{DBMS} = \text{database} + \text{programs to access and manage it}$

That core role packs several guarantees that a plain file system does not state.

Persistence. Data outlives any single program execution.
Concurrency control. Simultaneous operations are coordinated so the outcome stays correct.
Recovery. Hardware, software, and power failures do not corrupt the stored data.
Declarative access. Queries state what data is wanted, not how to fetch it from the bytes on disk.

To see why a file system is not enough, run two thought experiments. Two collaborators save the same file at nearly the same time: whose changes survive? Power fails halfway through a save: which changes survive? In both cases the honest answer is unclear, and over a platform whose promise is "unclear", every application must re-implement correctness on its own.

Transactional semantics. The guarantee that operations behave as complete, correct units of work (transactions), even under concurrency and failures. This is precisely the contract a file system leaves unstated; a DBMS provides it systematically.

The web has the same gap in a different form: it is strong at retrieval, but its data is unstructured and untyped, completeness is not guaranteed, and freshness and cross-item consistency are weak. Serious websites therefore place a DBMS behind the web layer rather than treat the web as one. A language model is not a DBMS either: it can sit in front of one, but by itself it offers no schema, no transactions, and no declarative data manipulation.

Ad-hoc query. A query formed for a specific immediate need rather than predefined as part of a fixed workflow. Convenient ad-hoc querying is the most visible capability a DBMS adds on top of storage: a question does not have to be anticipated by any program to be answerable.

Schemas and Data Independence

The central architectural question is how to keep one coherent meaning of the data while serving many users and storing bytes efficiently. The answer is to describe data with a model, and to split that description into levels.

Data model. A collection of concepts for describing data. A model is a deliberate abstraction: it hides storage detail so that structure and meaning come first. The dominant family is the relational model, where all data lives in flat tables; nested models (hierarchies, arrays, graphs, objects) instead admit structured values directly.

Relation. A named table whose rows are tuples and whose columns are attributes.

Schema. The structural description of a relation: its name, plus the name and type of every attribute.

A schema is a type and the stored data is a value of that type, the way string is a type and "hello" is a value.

Example 1. University schema.

Students(sid: string, name: string, login: string, age: integer, gpa: real)
Enrolled(sid: string, cid: string, grade: string)
Courses(cid: string, cname: string, credits: integer)

Relations connect to each other through values, not pointers.

Key. An attribute, or minimal set of attributes, whose value uniquely identifies a tuple within its relation. In Students, sid is a key: no two students share it.

Foreign key. An attribute, or set of attributes, in one relation whose values are key values of another relation, linking the two. In Enrolled, sid is a foreign key referencing Students.sid: the row (53666, Carnatic101, 5) makes sense only if student 53666 exists.

The same database is described at three levels of abstraction, each a schema in its own right.

External schema. What one user or application sees: views, often used for access control. Students_Info(sid, name) hides age and GPA; Course_Enrollment(cid, #enrolled) exposes only counts.
Logical (conceptual) schema. The single global structure of the data that all users and programs share. The three university relations.
Physical (internal) schema. How the data is stored: files, indexes, and layout. Unordered files, with indexes on Students.sid and Courses.cid.

The mapping runs

$\text{external schemas} \;\rightarrow\; \text{logical schema} \;\rightarrow\; \text{physical schema}$

with many external views onto one logical schema, realized by one physical layout.

Applications look through views at the logical schema; only the engine ever sees the physical one.

Data independence. The ability to change the schema at one level without changing the schema at the level above it.

Logical data independence. The logical schema can change without breaking the external views.
Physical data independence. The physical schema can change without breaking the logical schema or the views.

This is why the levels exist: storage layouts and indexes improve constantly, and applications keep working while they do.

DBMS Architecture and Database Design

Beneath the logical schema sits the engine. A query arrives in a declarative language such as SQL and descends through a stack of layers, each built only on the layer below it.

Query optimization and execution. Turn a declarative query into an efficient plan and run it.
Relational operators. Implement the plan's building blocks: selection, projection, join.
Access methods. Organize records into files and indexes that can locate data quickly.
Buffer management. Keep the disk pages currently in use cached in memory.
Disk space management. Allocate, read, and write pages on disk.

Transaction management and concurrency control cut across all five layers; they are how the engine delivers transactional semantics.

Designing the database itself is also staged, moving from problem understanding to implementation choices.

Requirements analysis. Understand what users need and what the database must support.
Conceptual design. Describe the enterprise data at a high level, independent of storage and implementation.
Logical design. Translate the conceptual description into the data model of the DBMS, typically relations.
Schema refinement. Improve the relational schema, in particular by normalization.
Physical design. Choose indexes and storage layout for the expected workload.
Security design. Decide who may access what, typically through external views.

Conceptual design is the stage with its own modeling language. It fixes three things:

which entities and relationships exist in the enterprise,
what information about them the database must store,
which integrity constraints must always hold.

Its standard language is the Entity-Relationship (ER) model, and the result is an ER diagram, a picture of the conceptual schema that maps systematically into a relational schema.

Entities, Attributes, and Relationships

An ER design starts from what exists: objects, their properties, and their associations.

Entity. A real-world object, distinguishable from every other object.

Attribute. A named property describing an entity, with values drawn from a domain, the set of values it may take. In the basic ER model attribute values are atomic (no internal structure) and single-valued (one value per entity).

Entity set. A collection of similar entities that share the same attributes. Its key is, exactly as for a relation, a minimal set of attributes whose values uniquely identify the entities in the set.

In the diagram, an entity set is a rectangle, each attribute an ellipse joined to it, and the key underlined.

The entity set Employees with attributes ssn, name, lot; ssn is the key (solid underline).

An instance of an entity set is the collection of entities currently stored in it. For Employees: (123-22-3666, John, P1) and (231-31-5368, Tom, P2), each a tuple over the declared attributes.

The pattern from relations repeats: the entity set declares the shape, the instance is the current content.

Entities become useful when they are associated.

Relationship. An association among two or more entities. A relationship set collects similar relationships and is drawn as a diamond joined to the participating entity sets. A relationship may carry its own descriptive attributes.

Works_In associates Employees and Department; its attribute since records when each assignment began. since belongs to the association itself, not to either entity.

The Works_In relationship set between Employees and Department, with descriptive attribute since.

An instance of a relationship set is the set of relationship tuples currently stored. Each Works_In(ssn, did, since) tuple ties one employee to one department through a date, so the instance is best read as concrete links between entity instances, not as a table.

Instance of Works_In(ssn, did, since): each stored relationship tuple is one concrete link from an employee, through a date, to a department.

A single entity set can participate in several relationship sets, and even several times in the same one. Its appearances then need to be told apart.

Role name. A label identifying the function of an entity set that appears more than once in the same relationship set.

In Reports_To, Employees participates twice, as supervisor and as subordinate, so each relationship tuple pairs one employee in each role. The same entity set still participates in Works_In independently.

Reports_To is a self-relationship on Employees: the same entity set participates twice, under the roles supervisor and subordinate, while still taking part in Works_In.

Key and Participation Constraints

By itself a relationship set lets any entity take part in any number of relationship instances. Two independent questions sharpen this into exact cardinality: may an entity appear more than once, and must it appear at least once?

Key constraint. Each entity in the set participates in at most one relationship instance. Drawn as an arrow from the entity set into the relationship.

Read an arrow as "at most once".

Key constraints set cardinality: no arrow is many-to-many, one arrow is one-to-many, arrows on both sides are one-to-one. An arrowhead means at most one.

With no arrows, Works_In is many-to-many: an employee may work in several departments and a department has many employees. The arrow into Manages makes it one-to-many: each department has at most one manager. Arrows on both sides of Drives make it one-to-one: each driver drives at most one vehicle and each vehicle has at most one driver.

Total participation. Every entity in the set participates in at least one relationship instance; drawn as a thick line. The default is partial participation, a thin line: an entity may participate in none.

Read a thick line as "at least once".

A thick line means total participation; a thin line is partial. The thick border and thick arrow on Manages combine total participation with a key constraint.

The two markings answer independent questions, so they combine freely into the full cardinality semantics.

Line	Arrow	Meaning
thick	none	total, many: participates at least once, possibly often
thick	arrow	total, at most one: participates exactly once
thin	arrow	partial, at most one: participates zero or one time
thin	none	partial, many: participates any number of times, possibly none

Weak Entities

Some entities have no key of their own and exist only relative to another entity.

Weak entity. An entity identified uniquely only by combining its own partial key with the primary key of an owner entity. The relationship linking it to the owner is its identifying relationship.

Three structural rules follow from "exists only through its owner".

Ownership. Owner and weak entity set are in a one-to-many relationship: one owner, many weak entities.
Total participation. The weak entity set participates totally in the identifying relationship, since no weak entity exists without an owner.
Partial key. Drawn with a dashed underline, it identifies weak entities only within the scope of one owner.

The weak entity set and its identifying relationship are drawn with thick borders, and the arrow from the weak entity marks the key constraint.

Dependents is a weak entity (thick border) owned by Employees through the identifying relationship Policy (thick diamond). pname is a partial key (dashed underline); the thick arrow marks total participation with a key constraint.

Dependents is owned by Employees through Policy. Two employees may each insure a dependent named Bob, so pname alone identifies nobody; the pair (owner's ssn, pname) is unique.

ISA Hierarchies

Some subgroups of an entity set carry extra attributes or join relationships of their own. ISA captures this specialization while keeping the shared attributes in one place.

ISA hierarchy. A superclass entity set with one or more subclass entity sets, where every subclass entity is a superclass entity and inherits all of its attributes. Declaring A ISA B means: every A is a B, has every attribute of B, and adds the attributes declared on A.

Hourly_Emps and Contract_Emps are subclasses of Employees: they inherit ssn, name, lot and add their own specialized attributes.

Two orthogonal constraints govern membership in the subclasses.

Overlap constraint. May an entity belong to two subclasses at once? Default no: the subclasses are disjoint.
Covering constraint. Must every superclass entity belong to some subclass? Default no: the coverage is partial.

ISA earns its place in two situations: when a subclass needs its own descriptive attributes, and when a relationship applies to exactly one subclass rather than to the whole superclass.

Example 2. Student hierarchy.

A Student is classified by degree (Bachelor or Post-Graduate) and by status (Full-time or Part-time) at the same time: two overlapping branches off the same superclass. Within each branch the subclasses are disjoint: a student is a Bachelor or a Post-Graduate, never both. Post-Graduate specializes further into Master and Doctorate, and the leaves join their own relationships: Bachelors register for Projects, Post-Graduates for a Thesis.

A deep ISA tree: Student specializes by degree and by status (two overlapping branches), Post-Graduate splits further into Master and Doctorate, and leaf subclasses join their own relationships.

Aggregation

ISA relates entity sets to entity sets. Aggregation answers a different need: letting a relationship participate in another relationship.

Aggregation. Treats a relationship set, together with its participating entity sets, as a single higher-level entity set. Drawn as a dashed box around the relationship; the box then participates in further relationships like any entity set.

Departments sponsor projects through Sponsors, and an employee must monitor each sponsorship. A ternary relationship among Projects, Departments, and Employees would lose the point: monitoring applies to the sponsorship itself, not to an independent triple. Aggregating Sponsors gives Monitors the right second participant.

The Sponsors relationship together with Projects and Departments is enclosed in a dashed box and treated as a single entity set, which then participates in Monitors with an Employee.

Design Choices

A correct ER schema is rarely unique. Three decisions recur, and each is settled by the semantics of the data and the queries the application must support.

Entity or attribute. Attributes are atomic and single-valued, so a concept must become an entity as soon as one entity needs several of them, or their internal structure matters. An employee with several addresses, or an address whose city, street, and zip must be queried separately: either way, address becomes an entity. The same reasoning applies to relationship attributes: if Works_In carries from and to, an employee can work in a department over only one period; recording several periods requires a separate Duration entity linked by its own relationship.

Entity or relationship. If a concept has its own identity, or must participate in other relationships, make it an entity rather than a relationship.

Binary or ternary. Prefer binary relationships when a ternary one decomposes into binary ones without losing information. Keep the ternary only when no combination of pairwise facts implies the triple.

The ER model expresses a great deal of semantics directly in the diagram: keys, participation, weak entities, ISA, aggregation. What it cannot express, such as a manager must also work in the department they manage, has to be enforced by the application or by database-level integrity constraints.