BSc CSIT (TU) Science Advanced Database (BSc CSIT, CSC461) Question Paper 2082 Nepal

Converting SQL Queries into Relational Algebra

SQL is a declarative language — it states what data is wanted, not how to retrieve it. Before a query can be executed and optimized, the DBMS first translates it into relational algebra, which is a procedural language with well-defined operators (σ, π, ⋈, ∪, etc.). Reasons for this conversion:

• Formal, unambiguous representation: Relational algebra has precise mathematical semantics, removing the ambiguity of SQL syntax and giving a clear internal form.
• Enables optimization: Algebraic expressions can be represented as a query tree and rewritten using equivalence rules, which is the basis of query optimization.
• Multiple equivalent plans: A single SQL query maps to many equivalent algebra expressions (different join orders, etc.); the optimizer chooses the cheapest.
• Procedural execution: Each algebra operator corresponds to a physical operator (scan, sort, join algorithm), making the query executable.
• Cost estimation: The size of intermediate results of each operator can be estimated, allowing the optimizer to compare plans.

Heuristic Optimization

Heuristic (rule-based) optimization improves a query by applying a set of transformation rules to the relational-algebra query tree, using general "rules of thumb" rather than detailed data statistics. The goal is to produce a query tree that minimizes the size of intermediate relations, lowering processing cost. It is faster and simpler than cost-based optimization but does not guarantee the globally optimal plan.

Main Heuristics Applied

1. Push selections (σ) down the tree so that rows are filtered as early as possible, reducing the number of tuples passed up.
2. Push projections (π) down to drop unneeded columns early, shrinking tuple width.
3. Perform the most restrictive operations first — apply the selection/join that produces the smallest result earliest.
4. Convert Cartesian products followed by a selection into a join (⋈), which is far cheaper.
5. Combine a cascade of selections into a single conjunctive selection.
6. Rearrange leaf nodes / join order so that the most selective operations execute first.

Example

Consider: Find names of employees who work in the 'Research' department.

SELECT E.Name
FROM Employee E, Department D
WHERE E.Dno = D.Dnumber AND D.Dname = 'Research';

Initial (canonical) tree — Cartesian product, then selection, then projection:

        π_Name
          |
   σ (E.Dno=D.Dnumber AND D.Dname='Research')
          |
          ×
        /   \
   Employee  Department

After applying heuristics — push σ_{Dname='Research'} down onto Department, turn the product + join condition into a join, and project early:

        π_Name
          |
          ⋈ (E.Dno = D.Dnumber)
        /   \
  π_{Name,Dno}   σ_{Dname='Research'}
      |              |
  Employee       Department

The optimized tree filters Department first (only one matching row) and joins on far fewer tuples, dramatically reducing the cost compared with computing the full Cartesian product.

Types of Transparency in a Distributed Database

Transparency means hiding the distributed nature of the database from users, so the system appears as a single logical database. The main types are:

• Distribution (Network) transparency: The user need not know where data is physically located or that the network exists. It has two parts:
  • Location transparency: A command is independent of the site where data is stored.
  • Naming transparency: Each object has a unique name; the user need not specify the site.
• Fragmentation transparency: The user works with the global relation without knowing it is split into horizontal/vertical fragments.
• Replication transparency: The user is unaware that multiple copies (replicas) of data exist; the system keeps them consistent.
• Design (Local mapping) transparency: Hides how global objects map to local schemas and the heterogeneity of underlying DBMSs.
• Transaction (Concurrency & Failure) transparency: Distributed transactions appear atomic and isolated, and the system recovers from site/communication failures transparently.

Distributed Database Architecture

A distributed database (DDB) is a collection of multiple logically interrelated databases distributed over a computer network, managed by a Distributed DBMS (DDBMS). The reference architecture extends the ANSI/SPARC three-schema model with schemas for distribution:

          +-------------------------+
          |     Global External     |   (user views)
          |        Schemas          |
          +-----------+-------------+
                      |
          +-----------v-------------+
          |   Global Conceptual     |   (logical description of
          |        Schema           |    whole DB, all relations)
          +-----------+-------------+
                      |
          +-----------v-------------+
          |   Fragmentation Schema  |   (how relations are split)
          +-----------+-------------+
                      |
          +-----------v-------------+
          |   Allocation Schema     |   (which fragment at which site)
          +-----------+-------------+
          |           |             |
   +------v---+  +----v-----+  +----v-----+
   | Local    |  | Local    |  | Local    |   (per-site internal/
   | Schema 1 |  | Schema 2 |  | Schema n |    conceptual schemas)
   +----+-----+  +----+-----+  +----+-----+
        |             |             |
     +--v--+       +--v--+       +--v--+
     | DB1 |       | DB2 |       | DBn |   (sites connected by network)
     +-----+       +-----+       +-----+

Layers explained:

1. Global Conceptual Schema (GCS): Describes all relations of the entire distributed database as if it were centralized.
2. Fragmentation Schema: Defines how each global relation is divided into fragments (horizontal, vertical, mixed).
3. Allocation Schema: Specifies at which site(s) each fragment is stored, and whether it is replicated.
4. Local Schemas: Each site has its own local conceptual and internal schema describing the locally stored fragments.

Architectural types:

The DDBMS components — query processor, transaction manager, and communication subsystem — coordinate across sites to provide the transparencies listed above.

Spatial Databases vs Regular Databases

A spatial database is designed to store, query, and manipulate spatial (geometric/geographic) data — points, lines, polygons, regions — in addition to ordinary alphanumeric data. It differs from a regular (relational) database in several ways:

In short, regular databases handle one-dimensional ordered values, whereas spatial databases must handle multidimensional data with specialized geometric operators and indexes.

Deductive Databases

A deductive database combines a relational database with logic programming / rule-based reasoning. It can derive (deduce) new facts from stored facts using inference rules, rather than storing every fact explicitly. It has two kinds of information:

• Facts (extensional database, EDB): stored base tuples (like relational tables).
• Rules (intensional database, IDB): logical rules (typically Datalog, a subset of Prolog) that define how to derive new relations.

Example (Datalog):

parent(john, mary).
parent(mary, ann).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Here the ancestor relation is deduced recursively from stored parent facts — something difficult to express in plain SQL.

Applying a Trigger in an Active Database

An active database reacts automatically to events using ECA (Event–Condition–Action) rules, most commonly implemented as triggers. A trigger is a stored block that the DBMS fires automatically on a specified INSERT, UPDATE, or DELETE.

Example: Keep a department's total salary updated automatically and log raises.

CREATE TRIGGER update_dept_total
AFTER UPDATE OF salary ON Employee
FOR EACH ROW
WHEN (NEW.salary <> OLD.salary)
BEGIN
  UPDATE Department
     SET total_salary = total_salary - OLD.salary + NEW.salary
   WHERE dno = NEW.dno;
END;

• Event: UPDATE OF salary ON Employee
• Condition: NEW.salary <> OLD.salary
• Action: adjust the department's total_salary

When any employee's salary changes, the DBMS automatically maintains the derived total_salary, demonstrating the reactive behaviour of an active database.

Replication and Allocation in Distributed Database Design

After a global relation is fragmented, the designer must decide where to place each fragment across the sites — this is the allocation problem — and how many copies of each fragment to keep — the replication decision.

Replication Techniques

Replication stores copies of the same fragment at multiple sites to improve availability and read performance, at the cost of more complex updates.

Benefits of replication: higher availability (survives site failure), faster local reads, load distribution.

Drawbacks: updates must be propagated to all copies, requiring concurrency control and consistency protocols (e.g., two-phase commit), increasing write cost.

Allocation Techniques

Allocation assigns each fragment (and its replicas) to one or more sites so as to minimize total cost — communication, storage, and processing — while meeting performance and availability needs.

• Non-redundant allocation: each fragment placed at a single "best" site, usually where it is accessed most (maximizes locality of reference).
• Redundant allocation: fragments placed at multiple sites (linked to replication).

Allocation is guided by an access frequency matrix describing how often each site accesses each fragment, balancing:

• Locality of reference — place data near where it is used.
• Communication cost — minimize inter-site data transfer.
• Availability and reliability — replicate critical fragments.
• Storage cost and update overhead.

Together, well-chosen fragmentation, replication, and allocation give a distributed design that is efficient, available, and balanced.

CAP Theorem

The CAP theorem (Brewer's theorem) states that a distributed data store can simultaneously guarantee at most two of the following three properties:

• Consistency (C): Every read returns the most recent write — all nodes see the same data at the same time.
• Availability (A): Every request receives a (non-error) response, even when some nodes fail.
• Partition tolerance (P): The system continues to operate despite network partitions (dropped/lost messages between nodes).

Because network partitions are unavoidable in real distributed systems, P must be tolerated, forcing a choice between:

• CP systems (sacrifice availability during a partition) — e.g., HBase, MongoDB in strong mode.
• AP systems (sacrifice strong consistency, offer eventual consistency) — e.g., Cassandra, DynamoDB.

Cost-Based Query Optimization

Cost-based optimization (CBO) chooses an execution plan by estimating the cost of alternative plans and selecting the cheapest, using actual data statistics rather than only rules of thumb.

How it works:

1. Generate alternative plans — different join orders, join algorithms (nested-loop, sort-merge, hash join), and access paths (full scan vs index scan).
2. Estimate cost of each plan using statistics from the system catalog: number of tuples, number of distinct values, index existence, block sizes, and selectivity of conditions.
3. Cost factors: primarily disk I/O (block accesses), plus CPU cost, memory usage, and (in distributed systems) communication cost.
4. Select the plan with the lowest estimated cost for execution.

Unlike heuristic optimization, CBO can find a near-optimal plan because it accounts for real data distribution, but it requires accurate statistics and is more computationally expensive.

Features of NoSQL Systems

A NoSQL (Not Only SQL) system is a non-relational data store built for large-scale, distributed, high-availability applications. Its main features are:

• Flexible / schema-less data model: Records need not share a fixed structure; the schema can evolve dynamically (e.g., JSON/BSON documents with different fields per record).
• Horizontal scalability (scale-out): Data is sharded/partitioned across many commodity servers; capacity and throughput increase by adding nodes rather than upgrading one machine.
• High availability and replication: Data is automatically replicated across nodes so the system tolerates node and network failures with little or no downtime.
• BASE consistency model: Most systems favour Basically Available, Soft state, Eventual consistency over strict ACID transactions, in line with the CAP theorem trade-off.
• Distributed architecture: Designed from the ground up to run on clusters, often spanning multiple data centres.
• Simple / specialized query interface: Access is through APIs or simple query languages; expensive joins are avoided and data is often denormalized.
• Handles large volume and variety (Big Data): Efficiently stores structured, semi-structured, and unstructured data.
• Variety of data models: Key-value, document, wide-column, and graph stores, each optimized for a workload.

These features make NoSQL well suited to web-scale, real-time, and Big Data workloads where relational databases struggle to scale.

Constraints on Specialization and Generalization

In the EER model, when a superclass is specialized into subclasses, two independent kinds of constraints control how member entities are distributed among the subclasses.

1. Disjointness (Disjoint vs Overlapping) Constraint

This specifies whether an entity may belong to more than one subclass of the same specialization.

• Disjoint (d): An entity instance can be a member of at most one subclass. Shown with a circle marked d.
  • Example: EMPLOYEE specialized by job type into SECRETARY, ENGINEER, MANAGER — an employee has exactly one job type.
• Overlapping (o): An entity instance may belong to several subclasses simultaneously. Shown with a circle marked o.
  • Example: PERSON specialized into STUDENT and EMPLOYEE — a person can be both at once.

2. Completeness (Total vs Partial) Constraint

This specifies whether every entity of the superclass must belong to some subclass.

• Total specialization: Every superclass entity must be a member of at least one subclass. Shown with a double line from superclass to the circle.
  • Example: every VEHICLE must be either a CAR or a TRUCK.
• Partial specialization: A superclass entity need not belong to any subclass. Shown with a single line.
  • Example: an EMPLOYEE need not be a MANAGER or ENGINEER.

Combinations

The two constraints are orthogonal, giving four valid combinations:

Supertype and Subtype

In the EER model, a supertype (superclass) is a generic entity type that holds attributes and relationships common to a group of related entities, while a subtype (subclass) is a specialized entity type that is a subset of the supertype and has its own additional attributes or relationships specific to it.

Key points:

• A subtype is an "IS-A" specialization of its supertype (e.g., a Car IS-A Vehicle).
• A subtype inherits all attributes, relationships, and the identifier (key) of its supertype — this is attribute and relationship inheritance.
• The supertype stores shared data once, avoiding redundancy; subtypes store only what is special to them.
• A supertype may have several subtypes governed by disjoint/overlapping and total/partial constraints.

Example

Supertype EMPLOYEE with subtypes ENGINEER, SECRETARY, and MANAGER:

                 EMPLOYEE  (supertype)
          attributes: EmpID, Name, Salary
                        |
                       /d\          (disjoint specialization)
                      / | \
                     /  |  \
            ENGINEER  SECRETARY  MANAGER   (subtypes)
            +Specialty +TypingSpeed +BonusAmount

• EMPLOYEE (supertype): common attributes EmpID, Name, Salary.
• ENGINEER (subtype): inherits the above plus Specialty.
• SECRETARY (subtype): inherits the above plus TypingSpeed.
• MANAGER (subtype): inherits the above plus BonusAmount.

Thus shared information is modelled once in the supertype, and each subtype adds only its distinguishing attributes.

Disjointness vs Overlap Constraints

Both are disjointness constraints in EER specialization that specify whether an entity of the superclass may simultaneously belong to more than one subclass.

Disjoint Constraint

• An entity instance of the superclass can be a member of at most one subclass of the specialization.
• The subclasses are mutually exclusive.
• Represented by a circle/triangle marked with the letter d.
• Example: EMPLOYEE specialized into FULL_TIME and PART_TIME — an employee is exactly one of them.

Overlap Constraint

• An entity instance of the superclass can be a member of more than one subclass at the same time.
• The subclasses may share instances.
• Represented by a circle/triangle marked with the letter o.
• Example: PERSON specialized into STUDENT and EMPLOYEE — a working student belongs to both.

Comparison

Note: this disjointness/overlap choice is independent of the total/partial (completeness) constraint.

Graphical Notations for Representing ODL Schemas

An ODL (Object Definition Language) schema describes the classes (interfaces), their attributes, relationships, and methods of an object database. Because ODL is text-based, its schemas are commonly visualized graphically, most often using the ODL/ODMG class diagram notation (a variant of the entity/UML-style class diagram). The main graphical elements are:

• Classes (objects): Drawn as rectangles (boxes), with the class name at the top. This is the analogue of an entity type.
• Attributes: Listed inside the class box (or attached as ovals in the ER-style variant), showing each property of the class.
• Relationships: Drawn as lines/edges connecting two class boxes. Because ODL relationships are binary and bidirectional (with inverses), each direction is labelled with its relationship (traversal-path) name.
• Cardinality (multiplicity): Indicated on the relationship edges to show 1:1, 1:N, or M:N, often using single-headed vs double-headed arrows (an arrow toward a single object vs toward a collection).
• Inheritance (IS-A): A subclass is connected to its superclass by an edge with a special marker (e.g., a triangle/arrow pointing to the superclass), showing the extends/: relationship and inheritance of attributes, relationships and methods.
• Methods (operations): Usually shown as a separate compartment in the class box (or omitted in schema-only diagrams), giving the operation signatures.

Example sketch:

   +----------------+   worksIn (1)   +----------------+
   |   Employee     |---------------->|   Department   |
   |----------------|                 |----------------|
   | empId          |<----------------| deptId         |
   | name           |  staff (N)      | dname          |
   +----------------+                 +----------------+
           ^ (extends)
           |
   +----------------+
   |   Manager      |
   +----------------+

These notations let designers represent the full ODMG object schema — classes, attributes, inverse relationships with cardinalities, and inheritance — in a clear visual form before writing the textual ODL.

Mapping EER to Relations

Mapping an EER schema to relations extends the basic ER-to-relational algorithm with extra steps for the EER concepts (specialization/generalization, etc.). The key steps are:

1. Map regular (strong) entity types → one relation each, with all simple attributes; choose a primary key.
2. Map weak entity types → a relation including the owner's primary key as part of its key (foreign key).
3. Map 1:1 and 1:N relationships → post a foreign key in the appropriate relation.
4. Map M:N relationships → create a separate junction relation with foreign keys to both sides.
5. Map multivalued attributes → a separate relation.
6. Map specialization/generalization (the EER-specific step) using one of these options:

Example

EER: superclass EMPLOYEE(SSN, Name, Salary) specialized (disjoint, partial) into ENGINEER(EngType) and SECRETARY(TypingSpeed).

Using Option A (superclass + subclass relations):

EMPLOYEE ( SSN, Name, Salary )                 PK: SSN
ENGINEER ( SSN, EngType )                      PK/FK: SSN -> EMPLOYEE
SECRETARY ( SSN, TypingSpeed )                 PK/FK: SSN -> EMPLOYEE

• EMPLOYEE holds the common attributes.
• ENGINEER and SECRETARY each hold the inherited key SSN (as both primary key and foreign key) plus their own specific attribute.
• To get all data about an engineer, join EMPLOYEE with ENGINEER on SSN.

This preserves inheritance through the shared key and represents the specialization correctly in the relational model.

Specifying Object Persistence

In an object database (ODMG model), objects can be transient (exist only during program execution) or persistent (survive after the program ends and are stored in the database). There are two mechanisms to make an object persistent and later retrieve it:

1. Persistence by Naming

An object is made persistent by giving it a unique, user-defined persistent name. This name acts as a root / entry point into the database through which the object can be directly retrieved in later sessions.

• A name is assigned to an object (e.g., via a bind/naming operation).
• The name must be unique within the database.
• Naming every object would be impractical, so usually only a few key root objects are named.

Example: bind a named root DepartmentList to a collection object so applications can fetch it by that name.

2. Persistence by Reachability

An object becomes persistent if it is reachable — directly or transitively — from a persistent root object (a named object). When a named object is stored, the system automatically makes persistent all objects referenced by it, then all objects those reference, and so on (transitive closure).

• This is also called persistence by reference or transitive persistence.
• A persistent root is typically a named collection (extent); any object inserted into it, and everything that object points to, becomes persistent.

Example:

DepartmentList   (named persistent root)
      |
      v
   Department  ----> Employee ----> Project

Naming only DepartmentList makes the Department, Employee, and Project objects reachable from it persistent automatically.

Summary

In practice, a small number of objects are made persistent by naming, and the bulk of the database becomes persistent automatically by reachability.