Data Abstraction and Schemas

Data abstraction is the practice of suppressing irrelevant detail while exposing exactly the information a given consumer of the data needs. In database systems this is formalized as a stack of three levels of description, first proposed in the 1975 ANSI/SPARC (Standards Planning and Requirements Committee) report and adopted, in spirit if not in exact terminology, by essentially every database textbook and system since. The three levels are: 1. Physical level (internal level). Describes how data is physically stored: the layout of records within files and blocks, which fields are indexed and by what structure (hash table, B+-tree), compression schemes, and physical placement across disks or storage nodes. This is the province of the storage engine and database administrator. 2. Logical level (conceptual level). Describes what data is stored and the relationships among data items, using a data model (relations, entity sets, documents) but without reference to physical storage. A database administrator or schema designer works here: "a `Student` has an `id`, a `name`, and a `major`; a `Student` enrolls in many `Course`s." 3. View level (external level). Describes partial, customized presentations of the logical data, tailored to particular applications or user roles. A billing application might see only tuition-related fields; a professor's grading application sees only enrollment and grade fields for their own courses. Multiple views can coexist over the same logical schema, and a view need not expose every attribute or every relation. Orthogonal to these three levels is the distinction between schema and instance. A schema is the overall structural design of a database at a given level — analogous to a variable's type declaration in a programming language, or a blueprint for a building. A schema is defined once (at design time) and changes only occasionally, through explicit schema evolution. An instance is the actual data stored at some point in time — analogous to the value a variable holds at runtime. Instances change with essentially every transaction (an `INSERT`, `UPDATE`, or `DELETE`), while the schema remains stable in between. Because a database has three levels, there are correspondingly three kinds of schema: a physical schema, a logical schema, and one or more view (external) schemas, each with its own instance-like counterpart of "current content" as expressed through that level.

The three levels are connected by mappings, and it is precisely these mappings that deliver data independence. Conceptually:

• The logical/physical mapping translates between the logical schema and the physical schema — it tells the system how a logical record (e.g., a `Student` tuple) corresponds to bytes in a file, and which index structures accelerate which logical queries.
• The view/logical mapping (also called the external/conceptual mapping) translates between each view schema and the logical schema — it tells the system how to compute a view's data from the underlying logical data, typically via a query or a stored "view definition."

Two independence guarantees fall directly out of this design:

• Physical data independence: the ability to change the physical schema (add an index, switch file organization, repartition data across disks) without changing the logical schema, and therefore without requiring any application or view above it to be rewritten. Only the logical/physical mapping needs updating.
• Logical data independence: the ability to change the logical schema (add an attribute, split a relation, rename a field) without necessarily requiring changes to every view or application, provided the change is compatible with existing views. Only the view/logical mapping for affected views needs updating. Logical data independence is harder to achieve fully than physical data independence, because logical changes are more likely to genuinely affect what applications can see.

The following pseudocode models how a query issued against a view is resolved down through the logical level to the physical level — the operational mechanism that makes the three levels work together at query time. ``` function EXECUTE_QUERY(view_name, query_expr): // Step 1: resolve view schema to logical schema view_def = LOOKUP_VIEW_DEFINITION(view_name) // view_def is itself a query expressed over the logical schema logical_query = SUBSTITUTE(query_expr, view_def) // e.g., "SELECT gpa FROM TranscriptView WHERE id = 5" // becomes a query over the base logical relations Student, Enrollment // Step 2: consult logical schema for relation/attribute existence & types logical_schema = LOOKUP_LOGICAL_SCHEMA() CHECK_TYPES_AND_NAMES(logical_query, logical_schema) // fails fast on schema mismatch // Step 3: query optimizer chooses a physical execution plan physical_schema = LOOKUP_PHYSICAL_SCHEMA() plan = OPTIMIZE(logical_query, physical_schema) // e.g., choose to use a B+-tree index on Student.id instead of a full scan // Step 4: execute plan against physical storage result = RUN_PLAN(plan, physical_storage) return result ``` Two properties of this pseudocode matter pedagogically. First, notice that `logical_query` at Step 1 never mentions files, blocks, or indexes — those appear only starting at Step 3. This textually enforces the separation: an application author writing `query_expr` at the view level literally cannot reference physical details, because the language available to them (e.g., SQL over a view) does not expose them. Second, notice that Step 3's choice of plan can change from one execution to the next (say, after an index is added) without any edit to Steps 1–2 — this is physical data independence made concrete: `OPTIMIZE` is re-run, but `SUBSTITUTE` and `CHECK_TYPES_AND_NAMES` are untouched.

Data abstraction is an architectural principle rather than an algorithm, so "complexity" here is best understood as the cost of query resolution through the layers, and "correctness" as a guarantee about isolation of change rather than a numeric bound.

Cost of resolution. Each layer in the pseudocode above adds a bounded amount of work:

• View resolution (`SUBSTITUTE`) is a syntactic rewrite of the query text using the stored view definition; this costs time proportional to the size of the query and view definition, $O(|Q| + |V|)$, and is independent of the size of the actual data.
• Schema/type checking (`CHECK_TYPES_AND_NAMES`) walks the query's attribute references against the logical schema's catalog, costing time proportional to the number of attribute references in the query, typically $O(|Q|)$ using a hashed catalog lookup.
• Physical plan selection (`OPTIMIZE`) is the expensive step in practice — its cost depends on the query optimizer's search strategy (dynamic programming over join orders is $O(3^n)$ for $n$ relations in the classic System R style, though heuristics prune this in practice) — but this cost exists regardless of whether abstraction layers are present; abstraction does not add asymptotic overhead to optimization, it only supplies the optimizer with a stable logical query to work from.
• Physical execution (`RUN_PLAN`) costs whatever the chosen access method costs (e.g., $O(\log n + k)$ for a B+-tree range scan returning $k$ results out of $n$ records), exactly as it would without any view layer.

The overall lesson: the three-level architecture adds only a small, query-size-proportional overhead (view substitution and catalog lookup) on top of unavoidable query processing costs, in exchange for the structural benefit of data independence. This is a textbook example of a favorable engineering tradeoff — a constant/linear-in-query-size cost purchases a global maintainability property.

Correctness argument for data independence. The claim to justify is: if the physical schema changes, but the logical/physical mapping is updated to preserve the logical schema's meaning, then no logical query or view definition needs to change, and all previously correct query results remain correct. The argument is an invariant-preservation argument. Define the invariant: > For every logical relation $R$ and every valid logical query $q$ over the logical schema, the value of $q$ evaluated via the current logical/physical mapping equals the value of $q$ evaluated via the original mapping, for all instances reachable by allowed updates. When a physical change is made (e.g., adding an index), the database administrator's obligation is to update the mapping so this invariant holds — concretely, the new mapping must still produce, for every logical tuple that existed before, the same logical-level answer as before (indexes only add alternate access paths to the same logical data; they do not change what data means). Because the invariant is maintained at the logical/physical boundary, and the view/logical mapping is untouched, by transitivity every view — and every application built on a view — continues to see identical results. This is why physical data independence is achievable by construction: physical reorganizations (indexing, compression, partitioning, file reorganization) are defined precisely as those changes that preserve the mapping invariant. Logical data independence is a weaker guarantee because logical schema changes can genuinely alter available information (e.g., dropping a column that a view depended on breaks that view no matter how you juggle mappings). The honest statement of the tradeoff is: physical data independence is essentially always achievable, since storage details are, by design, invisible above the physical/logical boundary; logical data independence is achievable only for view/logical mappings that do not depend on the removed or altered part of the logical schema — additive changes (new attributes, new relations) typically preserve it, while subtractive or restructuring changes typically do not.

Consider a small university database. We trace a single view-level query down through all three levels, and then show what happens when the physical schema changes.

Logical schema (conceptual level): ``` Student(id, name, major, gpa) Enrollment(id, course, grade) ```

View schema `TranscriptView`, defined once at design time: ``` CREATE VIEW TranscriptView AS SELECT Student.id, Student.name, Enrollment.course, Enrollment.grade FROM Student, Enrollment WHERE Student.id = Enrollment.id ```

Application query, issued against the view: ``` SELECT name, course, grade FROM TranscriptView WHERE id = 5 ``` Step-by-step resolution:

Suppose the schema (as an instance, not structure) currently contains: ``` Student: (5, "Ada Lovelace", "CS", 3.9) Enrollment: (5, "Databases", "A"), (5, "Algorithms", "A-") ``` The query returns: ``` ("Ada Lovelace", "Databases", "A") ("Ada Lovelace", "Algorithms", "A-") ```

Now the DBA makes a physical change: `enroll.dat` is reorganized from a heap file into a file sorted by `course`, and the hash index on `id` is replaced by a B+-tree index on `id`. This is a physical schema change. Neither `Student`/`Enrollment` (logical schema) nor `TranscriptView` (view schema) changes one bit. Re-running the exact same application query, Step 3 now picks a different plan (B+-tree seek instead of hash lookup), but Steps 1–2 are byte-for-byte identical, and the final returned rows are identical. This is physical data independence, demonstrated rather than merely claimed.

Contrast with a logical change: suppose the registrar decides to split `Student` into `Student(id, name)` and `Major(id, major, gpa)`. This is a logical schema change. Since `TranscriptView`'s definition references `Student.name` directly — which still exists — the view survives unchanged; this is logical data independence for this view. But a hypothetical `AdvisingView` that referenced `Student.gpa` would break, because `gpa` no longer lives in `Student` — its view/logical mapping must be rewritten (though the view's external appearance to applications can still be preserved by rewriting the mapping to join against the new `Major` relation). This illustrates precisely why logical data independence is partial: it depends on which parts of the logical schema each view actually touches. Finally, to nail down schema vs. instance: the schema `Student(id, name, major, gpa)` never changes when Ada Lovelace enrolls in a new course or when her GPA is recomputed after finals — only the instance (the actual rows) changes. The schema changes only when the registrar's office redesigns the database's structure, an event that should be rare and deliberate, unlike instance updates which happen continuously.

The three-schema architecture is one of the few genuinely committee-authored ideas in computer science to become foundational, emerging from standardization efforts rather than a single inventor's paper — but it built directly on data independence concepts pioneered by Charles Bachman in his work on the Integrated Data Store (IDS), one of the first database management systems, and later refined by the CODASYL Data Base Task Group.

Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server — implements the three-level architecture concretely: the physical level is the storage engine (heap files, B+-tree and hash indexes, buffer pool management); the logical level is the set of table and constraint definitions in the system catalog; the view level is the `CREATE VIEW` mechanism together with row-level and column-level security policies that expose different slices of the logical schema to different users. Physical data independence is what lets a database administrator add an index to speed up a slow query, migrate a table to a different tablespace, or switch compression schemes — all without a single line of application code changing. Cloud data warehouses (Snowflake, BigQuery, Redshift) push this further: physical storage is entirely managed by the platform, and the logical schema (tables, views) is the only interface application developers ever see, making physical data independence a first-class selling point of the "separate storage from compute" architecture. Logical data independence underlies schema migration tooling in ORMs (object-relational mappers) and API versioning strategies: teams design views or API layers precisely so that internal schema refactors do not force every client application to update simultaneously. It also motivates the layered design of document databases (MongoDB) and even distributed systems: a well-designed public API is, in essence, a view schema, insulating consumers from internal logical or physical reorganization. These same abstraction principles reappear, formalized with a specific structure and notation, in The Relational Model and in the graphical design methodology of Entity-Relationship Modeling, both of which operate squarely at the logical level introduced here.

Ask the tutor: Can you show how logical data independence would play out if we vertically split a table into two, using a view to keep old applications working?