Advanced Database

Why query optimization is essential. A declarative SQL query can be evaluated by many different equivalent plans, which differ greatly in cost (disk accesses, CPU, memory, communication). A poor plan, such as computing a Cartesian product before applying selections, may take hours where a good plan takes seconds. Users cannot be expected to write efficient access strategies, so the DBMS must choose automatically. Optimization therefore reduces response time and resource use, and increases throughput.

Heuristic optimization. Heuristic optimization applies rules of thumb that nearly always reduce the cost, without calculating costs of all alternatives. The query is represented as a query tree, and it is transformed by rules into an equivalent but more efficient tree.

Main heuristic rules:

1. Break up conjunctive selections into a cascade of selections.
2. Push selections down the tree as early as possible, to reduce the number of tuples.
3. Push projections down, to remove unneeded attributes early.
4. Replace Cartesian product followed by selection with a join.
5. Reorder leaf relations/joins so that the most restrictive selection (smallest result) is executed first, and avoid Cartesian products.
6. Combine selection and projection sequences, and use pipelining of operations to avoid temporary files.

Example: SELECT name FROM EMP, DEPT WHERE EMP.dno=DEPT.dno AND DEPT.dname='Sales'. The initial tree is $\pi_{name}(\sigma_{EMP.dno=DEPT.dno \wedge dname='Sales'}(EMP\times DEPT))$. After optimization it becomes $\pi_{name}(EMP \bowtie_{dno} \sigma_{dname='Sales'}(DEPT))$, which is far cheaper.

Why query optimization is needed

A SQL query only states what is wanted; the DBMS must choose how to evaluate it. A query can be evaluated by many equivalent relational-algebra expressions and access paths, and their costs (disk I/O, CPU, memory, communication) can differ by orders of magnitude. For example, a join performed before a selection can create a huge intermediate result that a selection performed first would have avoided. The optimizer therefore picks an efficient execution strategy, which gives:

• Faster response time and higher throughput.
• Less disk I/O, CPU and memory use.
• Better use of indexes and of the physical design.
• The user does not need to write "efficient" queries by hand.

Heuristic query optimization

Heuristic optimization applies rules of thumb that nearly always reduce cost, without estimating exact costs. It works on the query tree (or query graph):

1. Convert the SQL query to an initial query tree (canonical form).
2. Move SELECT operations as far down the tree as possible, since they shrink the relations early.
3. Break conjunctive selections into a cascade of selections and push each to the relevant leaf.
4. Replace Cartesian product followed by a selection on a join condition with a JOIN.
5. Apply the most restrictive selections and joins first, i.e. those producing the smallest results, and reorder the leaf relations accordingly.
6. Move PROJECT operations down, keeping only the attributes needed later.
7. Identify subtrees that can be pipelined, so that intermediate results are not written to disk.

Example

Schema: EMPLOYEE(Ssn, Name, Salary, Dno), DEPARTMENT(Dnumber, Dname, Location).

Query: names of employees who work in the department named 'Research'.

SELECT Name FROM EMPLOYEE, DEPARTMENT
WHERE Dname = 'Research' AND Dno = Dnumber;

Initial tree (inefficient):

$\pi_{Name}\big(\sigma_{Dname='Research' \wedge Dno=Dnumber}(EMPLOYEE \times DEPARTMENT)\big)$

This builds the full Cartesian product first. After applying the heuristics:

$\pi_{Name}\big(EMPLOYEE \bowtie_{Dno=Dnumber} \sigma_{Dname='Research'}(DEPARTMENT)\big)$

• The selection on DEPARTMENT is pushed down, so only one tuple remains.
• The Cartesian product plus the join condition becomes a join.
• A projection can also be pushed down so that only (Name, Dno) of EMPLOYEE and Dnumber of DEPARTMENT are carried to the join.

The intermediate result is now tiny compared with $|EMPLOYEE| \times |DEPARTMENT|$ tuples, so the query runs much faster. The optimizer then chooses the physical algorithms (for example an index nested-loop join) for the final plan.

Assumptions. The library keeps MEMBERs and ITEMs. A member is either a STUDENT or a STAFF member, and a person can be both (for example a teaching assistant), so the member specialization is overlapping. An item is exactly one of BOOK, JOURNAL or DVD, so the item specialization is disjoint. Every item must belong to one of these types, so it is a total specialization. Members may also be only ordinary members, so the member specialization is partial.

EER design

• Superclass MEMBER(<u>member_id</u>, name, address, phone, join_date).
  • Subclasses STUDENT(program, semester, roll_no) and STAFF(department, designation).
  • Constraint: overlapping, partial. Notation: circle labelled o, single line to MEMBER.
• Superclass ITEM(<u>item_id</u>, title, publisher, year, shelf_no).
  • Subclasses BOOK(isbn, edition, pages), JOURNAL(issn, volume, issue) and DVD(duration, format).
  • Constraint: disjoint, total. Notation: circle labelled d, double line to ITEM (total participation).
• AUTHOR(<u>author_id</u>, name) with a many-to-many relationship WRITES to BOOK.
• MEMBER M : N ITEM through the relationship BORROWS(issue_date, due_date, return_date, fine).

 MEMBER ===(o)--- STUDENT, STAFF
    |M
 BORROWS(issue_date, due_date, return_date, fine)
    |N
  ITEM ====(d)=== BOOK, JOURNAL, DVD       BOOK M--WRITES--N AUTHOR

Mapping to the relational model

Rule used: for overlapping or partial subclasses, one relation per superclass and per subclass, with the subclass key copied from the superclass (option 8A). For a disjoint, total specialization, the subclass relations with a type column are possible too. Here we use one relation per class for clarity.

• MEMBER(<u>member_id</u>, name, address, phone, join_date)
• STUDENT(<u>member_id</u>, program, semester, roll_no), with member_id a foreign key to MEMBER
• STAFF(<u>member_id</u>, department, designation), with member_id a foreign key to MEMBER
• ITEM(<u>item_id</u>, title, publisher, year, shelf_no, item_type), where item_type is in {Book, Journal, DVD} and NOT NULL (it enforces totality and disjointness)
• BOOK(<u>item_id</u>, isbn, edition, pages), with item_id a foreign key to ITEM
• JOURNAL(<u>item_id</u>, issn, volume, issue), with item_id a foreign key to ITEM
• DVD(<u>item_id</u>, duration, format), with item_id a foreign key to ITEM
• AUTHOR(<u>author_id</u>, name)
• WRITES(<u>item_id</u>, <u>author_id</u>), with item_id a foreign key to BOOK and author_id a foreign key to AUTHOR
• BORROWS(<u>member_id</u>, <u>item_id</u>, <u>issue_date</u>, due_date, return_date, fine), with foreign keys to MEMBER and ITEM

A member can have rows in both STUDENT and STAFF (overlap). An item has a row in exactly one of BOOK, JOURNAL or DVD (disjoint), and always in one of them (total), which is checked through item_type.

Object-oriented databases (OODB) store data as objects, as in object-oriented programming, and combine database capabilities with object-oriented concepts.

Main concepts and features

1. Object and object identity (OID). Every object has a unique, system-generated OID that is independent of its attribute values and never changes. Objects refer to one another through OIDs.
2. Object structure. An object has a state (attribute values) and behaviour (methods/operations).
3. Type constructors. Complex objects are built with atom, struct (tuple), set, list/array and bag constructors.
4. Encapsulation. The internal state is hidden and accessed only through operations (methods). An interface is public and the implementation is private, which gives data independence.
5. Class, type and inheritance. Objects of the same structure form a class. Subclasses inherit attributes and methods of superclasses (single and multiple inheritance), which supports reuse and hierarchies.
6. Polymorphism and operator overloading. One operation name can behave differently for different classes. Late (dynamic) binding chooses the method at run time.
7. Complex objects. Structured objects (documents, CAD designs) are stored as a single unit; both structured and unstructured objects (BLOB) are possible.
8. Persistence and extensibility. Objects survive program termination, and user-defined types can be added.
9. Other features. Versioning, schema evolution, transactions, concurrency control and query language (OQL).

Object-relational model. An object-relational database (ORDBMS) keeps the relational model (tables, SQL) and extends it with object features. It allows user-defined types (UDTs), row types, collection types (ARRAY, MULTISET), inheritance between types and tables, methods, references (REF) and large objects. Example: a table Person can have a column of type Address (a struct) and a table Student UNDER Person. SQL:1999 and later versions (Oracle, PostgreSQL, Informix) follow this approach. It lets old relational applications continue while giving rich data modelling.

Distributed database (DDB). A distributed database is a collection of logically related databases spread over several computers (sites) connected by a network. A distributed DBMS (DDBMS) manages it and makes the distribution transparent to users, who see it as a single database.

Benefits over a centralized database

1. Local autonomy and fit with the organization. Data is stored near where it is used (branches, departments), so local access is fast and local sites control their own data.
2. Improved performance. Local queries avoid network delay, load is shared, and queries can run in parallel on different sites.
3. Higher availability and reliability. A failure at one site does not stop the whole system.
4. Easier expansion (scalability). New sites can be added without redesigning the system.
5. Lower communication and hardware cost. Cheap small machines can be used instead of one large mainframe, and less data travels across the network.
6. Reduced bottleneck. There is no single point of failure or single overloaded server.

Availability. Availability is the probability that the system is continuously available during a time interval. In a DDB, data replicated at several sites can still be read or updated when one site or link fails, so the system remains operational and users find the data at some alternative site.

Reliability. Reliability is the probability that the system is running (not down) at a given moment, and that it behaves correctly. Failure of one node affects only its local data. Replication, distributed commit (two-phase commit) and recovery protocols keep the database consistent, so correct results are produced even after failures.

Scalability. Scalability is the ability to expand without interrupting the system. Horizontal scalability adds more nodes and distributes data among them; vertical scalability adds capacity (CPU, memory) to existing nodes. A DDB scales horizontally by adding sites and fragmenting or replicating data over them, with only a small performance penalty.

Costs are more complex design, concurrency control, recovery and security, but availability, reliability and scalability make DDBs suitable for large organizations.

Importance of indexing. An index is an auxiliary access structure on one or more fields (the indexing field) of a file. It works like the index of a book: instead of scanning every record, the DBMS searches the small index and goes straight to the block that contains the record.

• It reduces disk block accesses. A linear search of a file with $b$ blocks costs about $b/2$ accesses on average, while an index search costs about $\log_2 b_i + 1$, where $b_i$ is the number of index blocks.
• It speeds up selection, range queries, joins and sorted retrieval.
• Index entries are smaller than records, so more of the index fits in memory.
• Cost: extra storage and slower insert/delete/update since the index must be maintained.

Multilevel index. When the index itself is large, binary search on it is still costly. A multilevel index treats the index file (the first level) as an ordered file and builds a second-level index on it, then a third level, and so on, until the top level fits in a single disk block. Searching starts at the top block and goes down one level at a time, so the number of block accesses equals the number of levels plus one.

If the blocking factor (index entries per block) is $bfr_i$ (fan-out $fo$), a file with $r_1$ first-level entries needs $t=\lceil \log_{fo} r_1\rceil$ levels. Example: with 30,000 first-level entries and $fo=68$, the second level has $\lceil 30000/68\rceil=442$ entries, the third level has $\lceil 442/68\rceil=7$, and the fourth has 1 block, so 4 levels, i.e. 4 index accesses plus one data access. B-trees and B+-trees are dynamic multilevel indexes that stay balanced on insertion and deletion.

Aggregation is an abstraction in the ER/EER model that treats a relationship set together with its participating entities as a single higher-level entity, so that this whole can take part in another relationship. It models a "part-of" (has-a) relationship between a whole and its components. Ordinary ER cannot show a relationship between a relationship and an entity, and aggregation solves this.

Example. Employees work on projects (relationship WORKS_ON between EMPLOYEE and PROJECT). A company also wants to record which machine is used by an employee on a project. The machine is not related to the employee or the project alone, but to the assignment of the employee to the project.

• Aggregate WORKS_ON (EMPLOYEE, PROJECT) into a box that acts as one entity set.
• Define the relationship USES between this aggregate and MACHINE.

 EMPLOYEE --- WORKS_ON --- PROJECT        (the whole is an aggregate)
                 |
               USES
                 |
              MACHINE

Relational form: WORKS_ON(<u>emp_id</u>, <u>proj_id</u>) and USES(<u>emp_id</u>, <u>proj_id</u>, <u>machine_id</u>), where (emp_id, proj_id) is a foreign key to WORKS_ON.

Another example: a CAR is an aggregation of ENGINE, WHEEL and BODY. In EER, aggregation also describes a class built from its component classes. It avoids redundant relationships and expresses semantics clearly.

ODMG object model. The Object Data Management Group (ODMG) proposed a standard (ODMG 3.0) for object databases so that applications are portable across ODBMS products. Its parts are the object model, the Object Definition Language (ODL), the Object Query Language (OQL) and bindings to C++, Smalltalk and Java.

Features of the ODMG object model:

• Objects and literals. The basic building block is the object, which has an OID. Literals have values but no OID (atomic, collection and structured literals).
• Types. Objects are described by their interface (abstract behaviour), class (state and behaviour with implementation) and literal types.
• Properties. An object has attributes and relationships (binary, with inverses maintained by the system) and operations (methods with exceptions).
• Collections. Set, bag, list and array, with iterators.
• Inheritance. Behavioural inheritance of interfaces (:) and state-and-behaviour inheritance among classes (extends).
• Extents and keys. An extent is the set of all objects of a class; keys identify objects uniquely.
• Atomic objects, factory objects, database objects and transactions.

Object Query Language (OQL). OQL is the declarative query language of ODMG, with a syntax close to SQL (select ... from ... where) but working on objects and collections. It allows path expressions (dot notation) to follow relationships, method calls in queries, and nested queries, and it returns objects or literals.

Example:

select s.name
from s in Students
where s.department.name = "Computer" and s.cgpa > 3.0

Here s.department.name is a path expression; the result is a bag of strings. OQL can also use distinct, order by, group by, set operators (union, intersect, except) and quantifiers (exists, for all).

Query processing is the set of activities that translate a high-level query (SQL) into a low-level execution plan, execute the plan, and return the result. The main steps are:

1. Scanning, parsing and validation. The scanner finds tokens; the parser checks syntax; validation checks that relation and attribute names exist. An internal form (query tree or query graph) is made.
2. Translation to relational algebra. The SQL query is broken into query blocks and expressed in relational algebra.
3. Query optimization. The system chooses an efficient execution strategy among equivalent plans.
4. Code generation. The code that executes the chosen plan is generated.
5. Execution. The runtime database processor runs the plan and produces the result.

Query processing vs query optimization

Need for query optimization. An SQL query only states what is wanted, not how to get it. The same query can be evaluated by many equivalent plans (different orders of operations, different algorithms, with or without indexes), and their costs may differ by orders of magnitude. The optimizer picks a good plan so that the system uses less disk I/O, CPU time, memory and network time, giving a faster response and higher throughput for all users. Choosing the optimum plan by hand is not practical for users, so the DBMS does it.

Illustration. Consider SELECT name FROM EMPLOYEE E, DEPARTMENT D WHERE E.dno = D.dno AND D.dname = 'Research' where EMPLOYEE has 10,000 tuples and DEPARTMENT has 50 tuples, of which 1 is 'Research' and 200 employees work in it.

Plan 1. Compute the Cartesian product E × D (500,000 tuples), then select on the join condition and dname, then project. Huge intermediate result.

Plan 2. Join E and D first (10,000 tuples), then select dname = 'Research' (200 tuples), then project. Better but the join works on all employees.

Plan 3. Select D where dname = 'Research' first (1 tuple), then join with E using an index on E.dno (200 tuples), then project. The intermediate results are the smallest, so this plan is cheapest.

Choices the optimizer weighs: order of selections and joins, access path (full scan or index), join algorithm (nested-loop, sort-merge, hash join), and pipelining versus materialization. Using catalog statistics (number of tuples, blocks, distinct values) it estimates the cost of each plan and selects the cheapest, so that Plan 3 is chosen.

Why fragmentation is carried out. Fragmentation divides a global relation into smaller pieces (fragments) that are allocated to different sites.

• Locality of reference / usage. Applications usually use only part of a relation, so relevant data is stored near where it is used.
• Efficiency. Irrelevant data is not retrieved or transferred, and the size of the transmitted data is smaller.
• Parallelism. A query can be split into subqueries that run on different fragments at the same time.
• Security and balanced load. Sensitive parts can be kept apart; storage and processing are balanced across sites.
• Availability and performance improve with fewer remote accesses.

Fragmentation must be complete (all data is in some fragment), reconstructible (the original can be rebuilt) and disjoint (for horizontal fragments).

Horizontal vs vertical fragmentation

Why NoSQL systems are essential. Traditional relational databases are designed for structured data with a fixed schema and ACID transactions on a single server. Modern web applications (social networks, search, e-commerce, IoT) need to handle huge volumes of data, high read/write rates, and semi-structured or unstructured data (documents, graphs, logs). RDBMSs scale poorly horizontally, schema changes are costly, and joins are expensive on huge data. NoSQL ("Not only SQL") systems such as MongoDB, Cassandra, HBase, Redis and Neo4j are built to provide scalability, availability and flexibility on commodity clusters.

Characteristics of NoSQL systems

1. Scalability. Horizontal scaling by adding nodes (sharding/data partitioning), and distribution over many servers.
2. Availability, replication and eventual consistency. Data is replicated on multiple nodes; reads and writes go to any replica, giving high availability, and replicas become consistent eventually (BASE rather than ACID; CAP trade-off).
3. Flexible, schemaless or semi-structured data. No predefined schema; documents or key-value pairs can differ in structure.
4. Less powerful query languages. Simple APIs (get/put) or limited query languages; often no joins, since data is denormalized.
5. Versioning. Some systems keep multiple versions of data with timestamps.
6. Different data models. Document, key-value, column-family and graph stores.
7. Fast reads and writes with in-memory caching, and support for MapReduce-style processing of large data.

Spatial database. A spatial database is a database optimized to store and query data about objects in space: points, lines, polygons and regions with geometry, location and topology. Such data is used in GIS, maps, navigation, urban planning and environmental systems. It supports spatial data types (point, line, polygon), spatial operators (distance, intersection, contains, adjacent, within, buffer) and spatial indexes (R-tree, quadtree, grid files) to answer queries such as "find all hospitals within 5 km of a given location" or "which districts border Bagmati river".

Trigger. A trigger is a statement (a stored procedure) that the DBMS automatically executes in response to a specified event on a table, if a condition holds. It follows the Event-Condition-Action (ECA) model:

• Event: INSERT, UPDATE or DELETE on a table.
• Condition: an optional Boolean test.
• Action: the SQL statements to be executed, either BEFORE or AFTER the event, per row or per statement.

Example. Keep a log when a salary is raised by more than 10%.

CREATE TRIGGER salary_audit
AFTER UPDATE OF salary ON EMPLOYEE
FOR EACH ROW
WHEN (NEW.salary > OLD.salary * 1.10)
BEGIN
  INSERT INTO SALARY_LOG(emp_id, old_salary, new_salary, changed_on)
  VALUES (OLD.emp_id, OLD.salary, NEW.salary, CURRENT_DATE);
END;

Whenever the salary of an employee is updated by more than 10%, a log row is automatically inserted. Triggers enforce business rules, maintain audit trails and derived data, and keep integrity beyond declarative constraints.

a. CAP Theorem

Proposed by Eric Brewer, the CAP theorem states that a distributed data system cannot guarantee all three of the following properties at the same time; at most two can be fully achieved:

• Consistency (C). Every read sees the most recent write, so all nodes hold the same data at the same time.
• Availability (A). Every request to a working node receives a response (no error or timeout), even if some nodes are down.
• Partition tolerance (P). The system keeps working even if the network splits and messages between nodes are lost.

Since network partitions cannot be avoided in distributed systems, designers must choose between C and A when a partition occurs:

• CP systems (HBase, MongoDB in default mode) keep consistency and may refuse requests.
• AP systems (Cassandra, DynamoDB, CouchDB) stay available but may return stale data (eventual consistency).
• CA is possible only in a single node or non-partitioned system, such as a traditional RDBMS.

b. Deductive database

A deductive database is a database system that can deduce new facts from stored facts using rules and an inference mechanism. It is based on logic programming (Prolog/Datalog). It has:

• Facts stored in relations (extensional database), e.g. parent(ram, shyam).
• Rules (intensional database), defined by Horn clauses, e.g. ancestor(X,Y) :- parent(X,Y). and ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
• An inference engine that evaluates queries such as ancestor(ram, Who)? by bottom-up or top-down evaluation, supporting recursion.

Advantages: recursive queries, compact representation of knowledge and views. Applications include expert systems and knowledge bases.

Enhanced ER (EER) model. The EER model extends the basic ER model with object-oriented ideas so that complex applications (CAD, GIS, multimedia, university systems) can be modelled more precisely.

Features of the EER model

1. Subclass and superclass. A subclass is a subgroup of entities of a superclass that has meaningful special attributes or relationships. Example: EMPLOYEE (superclass) with SECRETARY, ENGINEER, TECHNICIAN (subclasses). A subclass entity is the same real-world entity as in the superclass (an "IS-A" relationship).
2. Inheritance. A subclass inherits all attributes and relationships of its superclass, and may add its own (local) ones. Multiple inheritance occurs when a subclass has more than one superclass (shared subclass).
3. Specialization. The top-down process of defining subclasses of a superclass based on some distinguishing characteristic (e.g. job type).
4. Generalization. The bottom-up process of combining several entity types with common features into a superclass.
5. Constraints on specialization/generalization.
   • Disjoint (d) vs overlapping (o): whether an entity can be a member of at most one subclass or of several.
   • Total vs partial: whether every superclass entity must belong to some subclass (double line) or not (single line).
   • Predicate-defined (attribute-defined) vs user-defined membership.
6. Specialization lattice and hierarchy. A hierarchy has each subclass with one superclass (tree); a lattice allows a subclass to have several superclasses.
7. Union type (category). A subclass whose members come from the union of different superclasses, e.g. OWNER may be PERSON, BANK or COMPANY.
8. Aggregation and composition (part-of abstraction), and classification/instantiation.

Specialization vs generalization

Both give the same final schema structure and use the same diagram notation; they differ in the direction of design.

Object-oriented database (OODB) vs object-relational database (ORDB)

Object database features included in SQL (SQL:1999 onward)

1. User-defined types (UDTs). CREATE TYPE address_t AS (street VARCHAR(30), city VARCHAR(20)); – distinct types and structured types with attributes and methods.
2. Row types and nested structure. A column can have a structured type, accessed with dot notation.
3. Collection types. ARRAY and MULTISET (and sets/lists in some systems) to store collections in a column.
4. Type inheritance. CREATE TYPE student_t UNDER person_t and table inheritance CREATE TABLE student OF student_t UNDER person.
5. Object identity and references. REF types and object identifiers; typed tables whose rows are objects, and dereferencing with ->.
6. Methods and encapsulation. Methods defined with the type; user-defined functions and procedures; operator overloading.
7. Large objects. BLOB and CLOB for multimedia.
8. Subtype polymorphism and substitutability, and the ONLY keyword to restrict a query to a table without its subtables.

Importance of distributed databases. Many organizations are geographically spread (branches, departments). A distributed database stores data at the sites where it is used, which gives faster local access, local control, higher availability and reliability, easy expansion, parallel query processing and lower communication costs than a single central database. It also reflects the organization's structure and supports data sharing across sites.

Transparency. Transparency is the concealment of the details of the distribution, so that users see the DDBMS as one logical database and do not need to know how or where the data is stored, replicated or accessed. It lets users write queries as if the database were centralized.

Types of transparency

1. Distribution (network) transparency. The user is unaware of the network and the distribution of data.
   • Location transparency: the command used does not depend on where the data or the issuing site is.
   • Naming transparency: each object has a unique name that is used regardless of site.
2. Fragmentation transparency. Users do not know that a relation is divided into horizontal or vertical fragments; a query on the global relation is automatically translated into fragment queries.
3. Replication transparency. Users are unaware that copies of data exist at several sites; the system keeps the copies consistent.
4. Concurrency transparency. Many users can run transactions at the same time without interference; consistency is preserved by distributed concurrency control.
5. Failure (recovery) transparency. Failures of sites or links are hidden; the system recovers and continues, preserving atomicity of global transactions (e.g. two-phase commit).
6. Performance transparency. The system performs as if centralized and chooses the cheapest strategy for distributed queries.
7. Migration transparency. Data can move between sites without affecting applications.
8. Heterogeneity transparency. Different hardware, operating systems, DBMSs and data models appear uniform.

Together, these make distributed access simple for users and application developers.

Importance of hashing. Hashing is a file organization in which a hash function $h(K)$ is applied to the hash field (key) $K$ of a record and gives the address of the disk block (bucket) in which the record is stored.

• It provides very fast access, usually one block access, for equality search on the hash key, with average $O(1)$ cost regardless of file size.
• No separate index is needed, so storage and index maintenance are saved.
• Insertion and deletion are quick. Records are spread across buckets uniformly with a good hash function (e.g. $h(K)=K \bmod M$).
• Collisions (two keys with the same address) are resolved by open addressing, chaining or multiple hashing; for growing files, dynamic schemes such as extendible and linear hashing avoid full reorganization.
• Limitation: it is poor for range queries and ordered retrieval, and static hashing wastes space or overflows if the file size changes.

Primary file organization. The primary file organization is the way in which the records of a file are physically placed on the disk, i.e. the main storage structure that determines how records can be accessed. Common primary organizations are:

• Heap (unordered) file: records are appended at the end.
• Sorted (sequential) file: records are ordered on some field, which allows binary search.
• Hashed file: records are placed by hash address.
• B-tree/clustered structures.

A file can have only one primary organization, but many secondary access structures (indexes) can be added on other fields.

Aggregation is an abstraction in the ER/EER model in which a relationship between entities, with those entities, is treated as a single higher-level entity. It expresses a "part-of" (whole-part) relationship and allows a relationship to take part in another relationship, which plain ER cannot express directly.

Example. A WORKS_ON relationship connects EMPLOYEE and PROJECT. Management also wants a MANAGER to monitor each employee's work on a project. The monitoring concerns the combination (employee, project), not either entity alone. So WORKS_ON (with EMPLOYEE and PROJECT) is aggregated and then related to MANAGER by the relationship MONITORS.

 EMPLOYEE --- WORKS_ON --- PROJECT     [ aggregated into one entity ]
                  |
              MONITORS
                  |
               MANAGER

Relational schema: WORKS_ON(<u>emp_id</u>, <u>proj_id</u>, hours); MONITORS(<u>emp_id</u>, <u>proj_id</u>, <u>mgr_id</u>) with (emp_id, proj_id) referencing WORKS_ON and mgr_id referencing MANAGER.

Other examples are a CAR made of ENGINE, WHEELS and BODY, or a COMPUTER made of CPU, RAM and DISK. Aggregation hides detail, avoids redundant relationships, and keeps the semantics of the model clear.

ODMG object model. The ODMG (Object Data Management Group) standard defines a common object model for object databases, so that applications are portable among different ODBMSs. It is the basis of the Object Definition Language (ODL) and the Object Query Language (OQL).

Main concepts:

• Object and literal. An object has a unique identifier (OID); a literal has a value but no OID.
• Type, interface and class. An interface specifies abstract behaviour (operations); a class specifies state (attributes and relationships) and behaviour, and can be instantiated.
• Attributes, relationships and operations. Binary relationships are declared with inverses; operations have signatures and exceptions.
• Collections: set, bag, list, array and dictionary.
• Inheritance with : (interface/behaviour) and extends (class).
• Extents and keys.
• Transactions and atomic, structured and collection literals.

Object Definition Language (ODL). ODL is the language that defines object types in the ODMG model, i.e. the schema of an object database. It is independent of any programming language and can be mapped to C++, Smalltalk or Java, and it is like a DDL for object databases. A class is declared with its extent, key, attributes, relationships and operations.

Example:

class Student
( extent Students key roll_no )
{
  attribute string name;
  attribute short roll_no;
  attribute struct Address {string city, string street} address;
  relationship Department belongs_to inverse Department::has_students;
  float gpa();
};

class Department
( extent Departments key dname )
{
  attribute string dname;
  relationship set<Student> has_students inverse Student::belongs_to;
};

Steps in query processing

Query processing converts a high-level query (SQL) into an efficient execution plan and runs it.

1. Scanning, parsing and validation.
   • The scanner identifies tokens (keywords, relation and attribute names, operators).
   • The parser checks the syntax against the grammar.
   • The validator checks that relation and attribute names exist in the schema and that operations are semantically valid. The result is an internal representation, a query tree or query graph.
2. Translation to relational algebra. The query is divided into query blocks, and each block is translated into an extended relational algebra expression (e.g. $\pi_{name}(\sigma_{salary>30000}(EMPLOYEE))$).
3. Query optimization. The optimizer considers equivalent algebra expressions and choices of access paths and algorithms (heuristic rules such as selection pushing, and cost estimation using catalog statistics) and selects the cheapest execution plan (query evaluation plan).
4. Code generation. The code that carries out the plan is generated (compiled, or interpreted by the runtime database processor).
5. Execution. The runtime database processor executes the plan, using the file access, index and buffer managers, and returns the result to the user; errors at run time are reported.

SQL query -> Scanner/Parser/Validator -> Query tree -> Optimizer -> Execution plan -> Code generator -> Runtime processor -> Result

Fragmentation. Fragmentation is the process of dividing a global relation (or database) into smaller pieces called fragments, which are stored at different sites of a distributed database. Reasons: data is kept near its users (locality), only needed data is transferred, queries execute in parallel on fragments, and load is balanced. A correct fragmentation must be complete (every data item is in some fragment), reconstructible (the original relation can be rebuilt) and disjoint (for horizontal fragmentation, no tuple is in two fragments).

Horizontal fragmentation. A horizontal fragment is a subset of the tuples of a relation, defined by a selection condition on one or more attributes: $F_i=\sigma_{C_i}(R)$ All attributes are present in every fragment. The relation is rebuilt as $R = F_1\cup F_2\cup\dots\cup F_n$.

Example. EMPLOYEE(eid, name, salary, dno) with departments 4, 5 and 6.

• $EMP_4=\sigma_{dno=4}(EMPLOYEE)$ at the Kathmandu site
• $EMP_5=\sigma_{dno=5}(EMPLOYEE)$ at the Pokhara site
• $EMP_6=\sigma_{dno=6}(EMPLOYEE)$ at the Biratnagar site

Each site stores the employees of its own department, so queries on that department are local. A query on all employees is answered by the union of the three fragments. Derived horizontal fragmentation fragments a related relation (e.g. DEPENDENT) according to the fragmentation of its parent (EMPLOYEE) through a join on the foreign key.

Characteristics of NoSQL systems

1. Scalability. NoSQL systems scale horizontally by adding commodity nodes, with data distributed through partitioning (sharding), e.g. using consistent hashing, so large data and high throughput can be handled.
2. Availability, replication and eventual consistency. Data is replicated across nodes so that the system stays available if a node fails. Replicas may be briefly inconsistent but converge eventually (BASE: Basically Available, Soft state, Eventually consistent), in contrast to ACID. The CAP theorem trade-off favours availability and partition tolerance.
3. Replication models. Master-slave (reads from slaves, writes to master) or master-master (any replica accepts writes, with conflict resolution).
4. Sharding of files. Records are split over many nodes to spread the load.
5. High-performance data access. Hashing or range partitioning on keys gives fast single-record read/write.
6. Not requiring a schema / semi-structured data. Records may have different attributes; schema is flexible and can change without downtime.
7. Less powerful query languages. Mostly key-based access or simple APIs; joins are not supported, so data is denormalized.
8. Versioning. Some systems keep several versions of data items with timestamps.
9. Variety of data models. Document (MongoDB), key-value (Redis, DynamoDB), column-family (Cassandra, HBase) and graph (Neo4j).

Active database. An active database is a database system that can react automatically to events (database state changes or time events) by executing predefined actions, without user request. A conventional (passive) database only acts when commands are issued. Active behaviour is specified by Event-Condition-Action (ECA) rules:

• Event: what activates the rule (INSERT, UPDATE, DELETE, or a time).
• Condition: a predicate checked once the event occurs.
• Action: the operation done if the condition is true.

Applications: enforcing integrity constraints and business rules, maintaining derived data and audit logs, alerting (e.g. stock low), replication, and monitoring.

Triggers. A trigger is a database object (a procedure) that is automatically fired when a specified event occurs on a table, and it is the mechanism by which SQL implements ECA rules. It can run BEFORE or AFTER the event, for each row (FOR EACH ROW) or for each statement.

CREATE TRIGGER low_stock
AFTER UPDATE OF qty ON PRODUCT
FOR EACH ROW
WHEN (NEW.qty < NEW.reorder_level)
BEGIN
  INSERT INTO REORDER(product_id, order_date) VALUES (NEW.product_id, CURRENT_DATE);
END;

When product quantity falls below the reorder level, a reorder record is automatically created.

a) Big data

Big data refers to data sets so large, fast-growing or varied that traditional database tools cannot capture, store, manage or analyse them efficiently. Sources include social media, sensors/IoT, transaction logs, web clicks and multimedia.

It is described by the V's: Volume (terabytes to petabytes and beyond), Velocity (speed of generation and processing, streaming), Variety (structured, semi-structured and unstructured data), and often Veracity (data quality) and Value.

Technologies: distributed storage (HDFS), MapReduce/Hadoop and Spark for processing, NoSQL databases, data warehouses and data lakes. Applications include recommendation, fraud detection, healthcare analytics and targeted marketing.

b) Information retrieval (IR)

Information retrieval is the discipline of finding relevant documents (mostly unstructured text) in a large collection in response to a user's information need, expressed as a keyword query. Web search engines are the best-known example.

Key concepts:

• Indexing: an inverted index maps each term to the list of documents containing it. Preprocessing includes tokenization, stop-word removal and stemming.
• Retrieval models: Boolean, vector space (TF-IDF weights with cosine similarity) and probabilistic models.
• Evaluation: $\text{Precision}=\frac{|\text{relevant retrieved}|}{|\text{retrieved}|}$ and $\text{Recall}=\frac{|\text{relevant retrieved}|}{|\text{relevant}|}$.
• Differences from DBMS: IR deals with unstructured data and approximate (ranked) matches, while DBMS queries structured data with exact matches.

Object database concepts

1. Object and object identity (OID). An object is a real-world entity with a state (values of attributes) and behaviour (operations). Each object has a system-generated, immutable OID that is independent of its values, so objects can be referred to by other objects, and two objects with equal values remain distinct.
2. Encapsulation. The structure and implementation of an object are hidden; it is accessed only through its interface of operations (methods). This gives data independence and protects integrity.
3. Class and type. A class (type) defines the structure and the operations shared by a set of similar objects. Objects are instances of a class.
4. Inheritance. A subclass inherits attributes and methods of its superclass (single or multiple inheritance), enabling reuse and class hierarchies.
5. Polymorphism and overloading. The same operator name can have different implementations for different classes. With late binding, the method is chosen at run time by the object's actual class.
6. Complex objects. Objects can be composed of other objects (nested), and structured (built with type constructors) or unstructured (BLOB).
7. Persistence, versioning and schema evolution. Objects survive after program termination; versions of objects can be stored; the class definitions can change.
8. Relationships are represented by references through OIDs, with inverses.

Type constructors. Type constructors are the mechanisms used to build complex object structures from simpler (atomic) types:

• Atom: basic built-in types (integer, string, float, boolean, char).
• Struct (tuple): a fixed set of named attributes, e.g. struct Name{ string first, string last }.
• Set: an unordered collection of distinct elements of the same type.
• List: an ordered collection that may have duplicates.
• Array: a fixed or variable-length indexed collection.
• Bag (multiset): an unordered collection allowing duplicates.

Example: define type EMPLOYEE: tuple( name: tuple(first: string, last: string); address: string; projects: set(tuple(pname: string; hours: float)) ); Here the constructors tuple and set are nested to define a complex object.

Distributed database architectures

A distributed database (DDB) is a collection of logically related databases spread over a computer network, managed by a distributed DBMS (DDBMS) that makes the distribution transparent to users. The main architectures are:

1. Shared-nothing (parallel / distributed) architecture. Each site has its own processor, memory and disk. Sites communicate only through the network and each holds a part of the data. It scales well, and most distributed databases follow it.
2. Shared-memory architecture. Several processors share a common main memory and disks over a fast bus. It is simple to program, but it does not scale well and the bus becomes a bottleneck.
3. Shared-disk architecture. Each processor has private memory but all can access all disks through an interconnection network. Failure of one node does not lose data, but disk contention can occur.
4. Client-server architecture. Clients run applications and user interfaces, and servers handle data storage, query processing and transactions. It can be two-tier (client with DB server) or three-tier (client, application server, DB server).
5. Peer-to-peer architecture. Every site acts as both client and server. Each site has local and global conceptual schemas, so any site can accept queries and coordinate them.
6. Federated (multidatabase) architecture. Autonomous, often heterogeneous databases are integrated, each retaining local autonomy. A federated schema or middleware presents a unified view. Federated systems are either loosely coupled (the users build the federation) or tightly coupled (a federation administrator does).

Data fragmentation

Fragmentation is the process of dividing a relation into smaller pieces (fragments) that are stored at different sites. This improves locality of reference, parallelism, availability and performance. The fragments must be complete (no data is lost), reconstructible (the original relation can be rebuilt) and disjoint, except for the keys.

• Horizontal fragmentation: a subset of tuples, defined by a selection. For example, $\sigma_{Dno=5}(EMPLOYEE)$ keeps the employees of department 5. The original is rebuilt by UNION.
• Vertical fragmentation: a subset of attributes, defined by a projection. For example, $\pi_{Ssn,Name}(EMPLOYEE)$ and $\pi_{Ssn,Salary}(EMPLOYEE)$. Each fragment keeps the primary key, and the original is rebuilt by JOIN.
• Mixed (hybrid) fragmentation: horizontal and vertical fragmentation applied together.

After fragmentation, a fragmentation schema, an allocation schema (which site stores which fragment) and optionally replication of fragments are defined.

Specialization is a top-down process of defining subclasses of an entity type, and generalization is the bottom-up process of combining entity types into a superclass. Constraints on both are of two kinds.

1. Constraints on which entities may belong to a subclass (predicate-defined)

• Predicate-defined (condition-defined): membership is decided by a condition on an attribute of the superclass. For example, in EMPLOYEE, JobType = 'Secretary' defines the SECRETARY subclass.
• Attribute-defined: all subclasses use the same defining attribute, for example JobType.
• User-defined: there is no condition, and the user adds entities to the subclass manually.

2. Constraints on the relationship between subclasses (disjointness and completeness)

• Disjointness constraint:
  • Disjoint (d): an entity can belong to at most one subclass. For example, an employee is either a SECRETARY or an ENGINEER.
  • Overlapping (o): an entity can belong to more than one subclass. For example, a person can be both STUDENT and EMPLOYEE.
• Completeness (totalness) constraint:
  • Total: every entity in the superclass must belong to at least one subclass. It is shown by a double line.
  • Partial: an entity need not belong to any subclass. It is shown by a single line.

These combine into four types: disjoint-total, disjoint-partial, overlapping-total and overlapping-partial.

Hashing is a technique that maps a search-key value directly to the address of a disk block (bucket) using a hash function $h(K)$, for example $h(K) = K \bmod M$, where $M$ is the number of buckets. A record with key $K$ is stored in bucket $h(K)$, and it is retrieved from the same bucket. When two keys map to the same bucket, a collision occurs, and it is resolved by chaining, open addressing or multiple hashing. Variants for files that grow are extendible hashing, linear hashing and dynamic hashing.

How it improves efficiency

• Equality searches (WHERE key = value) need about one block access, i.e. $O(1)$, instead of the $O(\log n)$ of a B-tree index or $O(n)$ of a linear scan.
• Insertion, deletion and update also go straight to the right bucket, so they are fast.
• No ordered index structure needs to be kept, which saves storage and maintenance time.
• Hash joins and hash-based grouping or duplicate elimination use it to partition data and make joins and aggregation faster.
• Records spread evenly over buckets, which reduces overflow and access cost.

Limitation: hashing is poor for range queries and ordered retrieval, because neighbouring keys are scattered over different buckets.

The ODMG (Object Data Management Group) object model is the standard model for object databases, on which the Object Definition Language (ODL) and Object Query Language (OQL) are based. Its main concepts are:

• Object and literal: the basic building block is the object, which has a unique object identifier (OID), a state (attribute values) and behaviour (operations). Literals have values but no OID, and they are atomic (integer, float, string, boolean, enum), collection or structured.
• Types and classes: a type is specified by an interface (abstract behaviour only), a class (state and behaviour, instantiable) or a literal definition.
• Attributes and relationships: an attribute holds a value of a literal type. A relationship links objects of two classes (binary, with 1:1, 1:N or M:N cardinality) and maintains referential integrity through inverse relationships.
• Operations: methods with a signature that define the behaviour of an object type, which may raise exceptions.
• Collections: Set, Bag, List, Array and Dictionary.
• Inheritance: behaviour inheritance (interface, with : notation) and extends inheritance (class inheritance, with the extends keyword). Multiple behaviour inheritance is allowed.
• Extents and keys: the extent is the set of all current instances of a class. A key is one or more attributes with unique values.
• Factory objects and database objects: factory objects create new objects, and the database object provides operations such as bind and lookup.

Example ODL:

class Employee (extent employees key ssn) {
  attribute string name;
  attribute string ssn;
  relationship Department works_for inverse Department::has_emps;
  float annual_salary();
};

A query tree is a tree data structure of a relational-algebra expression. Leaf nodes are the input relations, internal nodes are relational operations (selection, projection, join and so on), and the root gives the final result. Execution proceeds bottom-up: an internal node runs when its operands are available and is then replaced by its result.

Uses in query processing

• The parser translates the SQL query block into an initial query tree, which is the internal representation used by the optimizer.
• It shows the order of operations clearly, so it can be restructured using algebra equivalence rules (for example moving selections and projections down).
• Heuristic optimization transforms the initial tree into an equivalent, cheaper tree.
• It is used to compare alternative evaluation strategies and estimate their costs, and to choose the join order (left-deep trees suit pipelining).
• It identifies subtrees that can be pipelined, so that intermediate results are not materialised.
• The final tree is converted into an execution plan of physical operators and algorithms.

Example: for $\pi_{Name}(\sigma_{Dname='Research'}(EMPLOYEE \bowtie DEPARTMENT))$, the tree is optimised by pushing the selection down to DEPARTMENT before the join.

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

• Consistency (C): every read returns the most recent write, so all nodes see the same data at the same time.
• Availability (A): every request to a non-failing node receives a response, even if it is not the latest data.
• Partition tolerance (P): the system keeps working even if the network drops or delays messages between nodes.

Network partitions cannot be ruled out in a real distributed system, so the real choice is between consistency and availability when a partition occurs:

• CP systems keep consistency and partition tolerance, but may refuse requests during a partition. Examples are MongoDB, HBase and Redis.
• AP systems keep availability and partition tolerance, but may return stale data, with eventual consistency. Examples are Cassandra, DynamoDB and CouchDB.
• CA systems need no partition tolerance, so they are in practice single-node or traditional RDBMSs.

CAP guides NoSQL design. Most NoSQL databases relax consistency and follow BASE (Basically Available, Soft state, Eventual consistency) instead of ACID.

Big Data refers to data sets so large, fast-growing or varied that traditional database systems cannot capture, store, manage and analyse them efficiently. They need distributed technologies such as Hadoop, Spark and NoSQL stores. Typical sources are social media, sensors and IoT devices, logs and transactions.

The 3 V's

1. Volume: the sheer amount of data, from terabytes to petabytes and zettabytes. For example, the data generated daily by Facebook or by online transactions.
2. Velocity: the speed at which data is generated and must be processed, often in real time or near real time. For example, streaming sensor data and stock tickers.
3. Variety: the different forms of data: structured (relational tables), semi-structured (JSON, XML) and unstructured (text, images, video, audio).

Further V's are often added, such as Veracity (data quality and trustworthiness) and Value (usefulness of the insights).

A trigger is a database object, a procedure stored in the database, that is executed automatically when a specified event occurs on a table or view. It follows the Event-Condition-Action (ECA) model:

• Event: an INSERT, UPDATE or DELETE (for example "when a new employee is inserted").
• Condition: an optional test that decides whether the action runs (for example WHEN salary > supervisor's salary).
• Action: the SQL statements or procedure that are executed.

Triggers can fire BEFORE or AFTER the event, and either once per statement or once per row.

CREATE TRIGGER salary_check
AFTER INSERT OR UPDATE OF salary ON employee
FOR EACH ROW
WHEN (NEW.salary > 100000)
BEGIN
  INSERT INTO audit_log VALUES (:NEW.ssn, SYSDATE);
END;

Uses of triggers

• Enforcing complex integrity constraints and business rules that cannot be written as ordinary constraints.
• Auditing and logging changes to data.
• Automatically deriving or updating values (for example a total or a computed column).
• Maintaining replicated or summary tables, and keeping data consistent across tables.
• Sending alerts or notifications when certain conditions occur.
• Preventing invalid transactions, and supporting security checks.

Why spatial databases are needed

Spatial data describes objects with a location and shape in space (points, lines, polygons) such as maps, roads, rivers, buildings and satellite images. Ordinary relational databases cannot store such data properly or answer queries like "which hospitals are within 2 km of this point?" efficiently. Spatial databases are needed because they:

• Provide spatial data types (point, line, polygon) and spatial operators and functions.
• Use spatial indexes (R-tree, quadtree, grid file) for fast searching.
• Support GIS, navigation, urban planning, environmental monitoring, telecom and location-based services.
• Allow spatial and non-spatial data to be queried together.

Common types of analysis of spatial data

1. Measurement: distance, length, area and perimeter.
2. Spatial queries: range queries (all objects in a region), nearest-neighbour queries and spatial joins.
3. Topological analysis: relations such as contain, intersect, overlap, touch and adjacent.
4. Proximity / buffer analysis: finding objects within a given distance of a feature.
5. Overlay analysis: combining several map layers to produce a new one.
6. Network analysis: shortest path and routing.
7. Spatial pattern and clustering analysis: hot spots, spatial data mining and classification.

(a) Map Reduce

MapReduce is a programming model and framework (introduced by Google, implemented in Hadoop) for processing very large data sets in parallel on a cluster of commodity machines. The data is stored in a distributed file system (GFS/HDFS), and the computation is moved to the data. A job has two user-defined functions:

• Map: takes input key-value pairs and emits intermediate key-value pairs, $(k_1, v_1) \rightarrow list(k_2, v_2)$.
• Reduce: receives each intermediate key with the list of all its values, and combines them into the final result, $(k_2, list(v_2)) \rightarrow list(v_3)$.

Between the two steps, the framework performs a shuffle and sort that groups all values by key.

Example (word count): Map emits (word, 1) for each word; Reduce adds the counts for each word.

Advantages are scalability, fault tolerance (failed tasks are re-run) and simplicity of parallel programming.

(b) Multimedia database

A multimedia database (MMDB) stores and manages multimedia data, such as text, images, audio, video and graphics, along with their descriptive metadata. Features:

• Large objects are stored as BLOBs or in external files.
• Content-based retrieval: search by features such as colour, texture, shape, or sound, not only by keywords (query by example).
• Special indexing and similarity search (feature vectors, R-trees).
• Support for temporal and synchronisation requirements, and for streaming of audio and video.
• Compression, and quality of service for playback.

Applications: digital libraries, video on demand, medical imaging, e-learning, news and entertainment archives, and surveillance.

Why SQL is converted into relational algebra. SQL is declarative: it states the result wanted but not the steps. The DBMS cannot execute it directly, so the parser translates each query block into an extended relational algebra expression (a query tree). This is done because:

• Relational algebra is procedural, so it gives a definite sequence of operations ($\sigma$, $\pi$, $\bowtie$, $\cup$ ...) that can be implemented by algorithms.
• It has well-defined equivalence rules, which let the optimizer rewrite an expression into other equivalent but cheaper forms.
• Each operator maps to physical algorithms (index scan, sort-merge join, hash join) whose cost can be estimated.
• It gives a uniform internal representation (query tree) that is independent of the surface syntax.

A complex SQL query is first broken into query blocks (SELECT-FROM-WHERE-GROUP BY-HAVING), and each block is translated into algebra and optimized separately; nested subqueries are treated as separate blocks.

Heuristic optimization. Heuristic optimization uses rules of thumb (heuristics) to transform the initial query tree into a final one that is expected to execute more efficiently, without computing costs of alternative plans. The rules usually, though not always, reduce intermediate result size. It is cheap to apply and is typically followed by cost-based choices for access paths and join algorithms.

Main heuristics.

1. Cascade of selections: break $\sigma_{c_1 \wedge c_2 \wedge \dots \wedge c_n}(R)$ into $\sigma_{c_1}(\sigma_{c_2}(\dots\sigma_{c_n}(R)))$.
2. Push selections down the tree as far as possible, so fewer tuples are processed by later operations. Selection commutes with other selections and with joins (when the condition involves only one relation's attributes).
3. Apply the most restrictive selections first, i.e. those that yield the fewest tuples (smallest selectivity).
4. Replace Cartesian product followed by a selection by a join: $\sigma_{A=B}(R \times S) \equiv R \bowtie_{A=B} S$, and reorder joins so that products are avoided and smaller relations are joined first (associativity of join).
5. Push projections down to leave only the attributes needed by later operations, reducing tuple size: $\pi_{L}(R \bowtie S)$ becomes $\pi_L(\pi_{L_1}(R) \bowtie \pi_{L_2}(S))$, keeping join attributes.
6. Identify subtrees that can be pipelined so intermediate results are not materialized.

Example.

SELECT S.Name FROM STUDENT S, ENROLL E, COURSE C
WHERE S.Id = E.Sid AND E.Cid = C.Cid AND C.Title = 'Databases' AND S.Year = 2;

Initial tree: $\pi_{Name}\big(\sigma_{S.Id=E.Sid \wedge E.Cid=C.Cid \wedge Title='Databases' \wedge Year=2}((S \times E) \times C)\big)$.

After applying the heuristics:

$\pi_{Name}\Big(\big(\pi_{Id,Name}(\sigma_{Year=2}(S)) \bowtie_{Id=Sid} E\big) \bowtie_{Cid=Cid} \pi_{Cid}(\sigma_{Title='Databases'}(C))\Big)$

The selections on STUDENT and COURSE are done first at the leaves, both Cartesian products are changed into joins, and projections discard unneeded columns, so the intermediate results are far smaller than the full product of the three tables.

Types of transparency in a distributed database. Transparency hides the complexity of distribution from the user, who sees the system as if it were a single centralized database.

1. Distribution (network) transparency: the user need not know where data is stored.
   • Location transparency: a command works the same regardless of the site where data resides.
   • Naming transparency: each object has a unique name, accessible without specifying its site.
2. Replication transparency: the user is unaware that copies of data exist at multiple sites.
3. Fragmentation transparency: the user is unaware that a relation is divided into horizontal or vertical fragments; queries are written against the global relation.
4. Concurrency transparency: many users can access data at the same time without interference, and consistency of all copies is maintained.
5. Failure transparency: the system continues to function and recovers correctly despite site or link failure.
6. Performance transparency: the system performs as well as a centralized one, with the optimizer choosing the cheapest strategy.
7. Heterogeneity transparency (in federated systems): differences in hardware, OS and DBMS are hidden.

Distributed database architecture. A DDBMS is built from multiple sites connected by a network. Each site has its own processor, storage and local DBMS.

• Schema levels. The global conceptual schema (GCS) describes the logical structure of the whole database as if it were not distributed. It is mapped to fragmentation schema (how global relations are divided into fragments) and allocation schema (which site stores which fragment and its replicas). Each site then has a local conceptual schema and local internal schema (physical storage). External schemas give user views.
• Components. At each site there is a global transaction manager / query processor (decomposes global queries into sub-queries, optimizes them and coordinates execution), and a local DBMS that executes sub-queries and manages local data. The data dictionary (global catalog) stores fragmentation, allocation and replication information.
• Architectural models.
  • Client-server: clients handle the user interface; servers manage data and execute queries.
  • Peer-to-peer: all sites are equal, each acting as both client and server, with global conceptual schema integrating local ones.
  • Federated / multidatabase: autonomous, possibly heterogeneous databases share data through a federated schema or multidatabase language.
• Query flow. A user query on the global schema is decomposed, localized to fragments using the fragmentation schema, optimized to reduce data transfer, sent to the relevant sites, and the partial results are combined.
• Concurrency and commit. Distributed concurrency control (e.g. distributed locking) and two-phase commit protocol ensure atomicity across sites.

Spatial versus regular databases.

Spatial databases also need special handling for very large objects and complex query processing.

Deductive databases. A deductive database is one that can deduce new facts from stored facts using rules (logic programming, usually Datalog), with a built-in inference engine. It has two parts:

• Extensional database (EDB): facts stored explicitly as relations, e.g. parent(ram, shyam).
• Intensional database (IDB): rules defining virtual relations, e.g. ancestor(X,Y) :- parent(X,Y). and ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

Queries such as ancestor(ram, W)? are answered by deriving facts through bottom-up or top-down evaluation. Rules support recursion, which plain SQL handles poorly, and they give a compact way to express knowledge.

Triggers in active databases. An active database has rules that react automatically to events, using the Event-Condition-Action (ECA) model: on event, if condition, then action. A trigger is applied by creating it with CREATE TRIGGER, specifying the event (INSERT/UPDATE/DELETE), timing (BEFORE/AFTER), granularity (FOR EACH ROW or statement), the condition (WHEN) and the action.

Example: keep an audit of salary raises, and block salary decreases.

CREATE TRIGGER salary_audit
AFTER UPDATE OF salary ON Employee
FOR EACH ROW
WHEN (NEW.salary > OLD.salary)
BEGIN
    INSERT INTO Salary_Log(emp_id, old_sal, new_sal, changed_on)
    VALUES (OLD.emp_id, OLD.salary, NEW.salary, SYSDATE);
END;

When a row's salary is updated, the DBMS detects the event, evaluates the condition and automatically inserts a record into Salary_Log. The user does not call the trigger explicitly. Similarly, a BEFORE UPDATE trigger can raise an error when NEW.salary < OLD.salary.

Replication. Replication means storing copies of a fragment or relation at more than one site.

• Fully replicated: the whole database is copied at every site. Maximum availability and read performance, but updates are expensive and concurrency control is complex.
• Non-replicated (fully partitioned): each fragment is stored at exactly one site. No update overhead but low availability and reliability.
• Partially replicated: some fragments are replicated, depending on access frequency. This is the usual compromise.

Benefits: higher availability and reliability (if a site fails, copies exist elsewhere), better read performance since queries use a local copy, and load balancing. Costs: more storage and the need to keep copies consistent (synchronous or asynchronous update propagation, primary-copy or quorum methods).

The degree of replication depends on how often each fragment is read versus updated at each site. Read-heavy data should be replicated more, while update-heavy data should be replicated less.

Allocation. Allocation is deciding at which site each fragment (or copy) is stored. It is usually modelled as an optimization problem to minimize the total cost of storage and communication, subject to response-time and capacity constraints. The information needed includes the database fragments, the types and frequencies of queries and transactions at each site, site capabilities, and network costs.

Strategies:

• Centralized: all data at one site.
• Partitioned (fragmented): fragments each at one site.
• Selective replication: key fragments replicated at selected sites.
• Full replication.

Allocation is chosen so that data is placed near where it is used most, giving local access and lower communication cost. The result is recorded in the allocation schema of the global catalog.

CAP theorem. In a distributed data system it is impossible to guarantee all three of the following at the same time; at most two can be had:

• Consistency: every read sees the latest write; all nodes show the same data.
• Availability: every request to a working node receives a response.
• Partition tolerance: the system keeps working even when network failures split the nodes.

Because partitions are unavoidable in practice, a system must choose between consistency (CP, e.g. HBase, MongoDB) and availability (AP, e.g. Cassandra, DynamoDB) during a partition. Traditional RDBMS give consistency and availability (CA) but on a single node or network without partitions.

Cost-based query optimization. In cost-based optimization the optimizer generates several candidate execution plans for a query, estimates the cost of each one, and picks the plan with the lowest estimated cost. It is more accurate than purely heuristic optimization.

The cost components are:

• Disk access cost (reading and writing blocks), usually the dominant factor.
• CPU cost of processing tuples.
• Memory (buffer) usage.
• Communication cost in distributed systems.

The estimates use information stored in the system catalog: the number of tuples $r$, number of blocks $b$, blocking factor $bfr$, number of distinct values of attributes, selectivity of conditions, available indexes and their levels. For example, the cost of a linear search is $b$ block accesses, of a binary search $\log_2 b$, and of an index search on a B+-tree is roughly the number of levels plus one. The result size of a selection is estimated as $r \times s$, where $s$ is the selectivity. For joins the optimizer estimates the size of intermediate results and compares join orders and algorithms (nested loop, index join, sort-merge, hash join). To limit the search space, dynamic programming or left-deep trees are used.

NoSQL ("not only SQL") systems are non-relational databases designed to store and process very large, varied and rapidly changing data across distributed clusters. Their main features are:

1. Scalability (horizontal): capacity grows by adding more commodity nodes (scale-out), not by buying a bigger server. Data is sharded across nodes.
2. Availability, replication and fault tolerance: data is replicated over several nodes, so the system keeps running if a node fails; this gives high availability, usually favouring AP in the CAP theorem.
3. Schema-less / flexible data model: records can have different structures and the schema can evolve without migrations. Main data models are key-value, document, column-family and graph stores.
4. Weaker consistency (BASE): Basically Available, Soft state, Eventual consistency, instead of full ACID, to gain speed and availability.
5. High performance: simple access by key, no complex joins, with in-memory caching and efficient writes support high throughput and low latency.
6. Non-SQL / simple APIs: access through simple APIs, query languages like CQL or JSON queries, or MapReduce, and often no support for joins.
7. Distributed processing: use of parallel processing such as MapReduce on large datasets.
8. Open source and low cost: many NoSQL systems (MongoDB, Cassandra, Redis, Neo4j) run on cheap hardware.
9. Handling big data variety: suitable for semi-structured and unstructured data such as logs, social data and sensor data.

Typical uses: social networks, real-time analytics, content management, caching, IoT. Limitations include limited transaction support and lack of standardization.

Two main types of constraints apply to specialization and generalization in the EER model.

1. Disjointness constraint. This specifies whether the subclasses of a specialization may share members.

• Disjoint (d): an entity of the superclass can belong to at most one of the subclasses. Example: EMPLOYEE specialized into SECRETARY, ENGINEER, TECHNICIAN by job type, where each employee has one job type.
• Overlapping (o): an entity can belong to more than one subclass at the same time. Example: PERSON specialized into STUDENT and TEACHER, where a person may be both.

2. Completeness (participation) constraint. This specifies whether every entity in the superclass must be a member of some subclass.

• Total (shown by a double line): every superclass entity must belong to at least one subclass. Example: every VEHICLE is either a CAR or a TRUCK.
• Partial (single line): some superclass entities may belong to no subclass. Example: an EMPLOYEE need not be in any of the specialization subclasses.

The two constraints are independent, so there are four combinations: disjoint-total, disjoint-partial, overlapping-total and overlapping-partial. In diagrams the letters d or o are written in the circle joining the superclass and subclasses.

Supertype and subtype. In EER modelling (and in object databases) entity types can be arranged in a hierarchy.

• A supertype (superclass) is a generic entity type that holds the attributes and relationships common to a set of more specialized entity types.
• A subtype (subclass) is a specialized entity type that is a subgroup of the supertype and has additional attributes/relationships of its own. It is related to the supertype by an IS-A relationship, and every member of the subtype is also a member of the supertype.

A subtype inherits all attributes and relationships of its supertype, so they are stored once in the supertype. The process of defining subtypes from a supertype is specialization; the process of combining subtypes into a supertype is generalization.

Example. Supertype EMPLOYEE(Emp_id, Name, Address, Hire_date). Subtypes:

• SECRETARY with the extra attribute Typing_speed.
• ENGINEER with the extra attribute Eng_type.
• MANAGER with the extra attribute Bonus.

An engineer entity has Emp_id, Name, Address, Hire_date (inherited) and Eng_type (own). A subtype may also take part in its own relationships, e.g. MANAGER manages DEPARTMENT. A discriminator attribute such as Job_type can show which subtype an employee belongs to.

Disjointness and overlap are the two possible values of the disjointness constraint on a specialization.

Both can be combined with the completeness constraint (total or partial). The difference is that disjointness restricts an entity to one subclass, whereas overlap places no such restriction.

The Object Definition Language (ODL) of the ODMG standard describes object schemas. An ODL schema can be shown with graphical notations, similar to ER/UML class diagrams. The common notations are:

1. Class (interface) box. A rectangle, divided into compartments, represents a class. The top gives the class name, the middle lists attributes (with types), and the bottom lists operations (methods). For example, Employee with attributes Name, Ssn, Salary and operation age().
2. Attributes. Listed inside the class box as attribute type name. Structured attributes can be shown as nested struct, and collection-valued ones as Set, List, Bag or Array of a type.
3. Relationships. Drawn as lines between class boxes. Each relationship has a name and an inverse relationship; ODL relationships are binary and always paired with their inverse. The cardinality is shown by the line ends: a single-line end means a single reference (1), and a double arrow or * means a collection (N). Thus 1:1, 1:N and M:N can be shown, e.g. Department has_emps (set of Employee) inverse works_for.
4. Inheritance (specialization). A line with a triangle/arrow pointing to the superclass shows extends (class inheritance) or : (interface inheritance), e.g. Manager to Employee.
5. Extent and key. Often written next to the class name, e.g. (extent all_employees key Ssn).
6. Aggregation/composition. A diamond on the line can show that one object is composed of another.
7. Operations. Shown with signature and return type, e.g. float salary().

Example: Employee box (Name, Ssn) connected to Department box (Dname, Dnumber) by two relationship lines works_for (single-valued) and has_emps (set-valued), each labelled as the inverse of the other.

Mapping an EER schema to relations extends the ER-to-relational mapping with steps for specialization/generalization and categories.

Steps for the ER part.

1. Regular entity type becomes a relation with its simple attributes; primary key chosen.
2. Weak entity type becomes a relation including the owner's primary key as a foreign key.
3. Binary 1:1 relationship uses a foreign key (or merged relation).
4. Binary 1:N relationship puts the foreign key on the N side.
5. Binary M:N relationship becomes a new relation with the two primary keys as foreign keys.
6. Multivalued attributes become a separate relation; n-ary relationships become a new relation.

Steps for EER (specialization/generalization). For a superclass $C$ with subclasses $S_1, \dots, S_m$ and key $k$:

• Option 8A (multiple relations, superclass and subclasses): relation $L$(k, attributes of $C$) for the superclass, and for each subclass $L_i$(k, attributes of $S_i$), with $k$ as primary key and also a foreign key to $L$. Works for any constraint (disjoint/overlapping, total/partial).
• Option 8B (multiple relations, subclasses only): one relation per subclass containing all attributes of $C$ plus those of $S_i$. Used when specialization is total and disjoint.
• Option 8C (single relation with a type attribute): one relation with the attributes of $C$ and all subclasses plus a type attribute $t$ saying which subclass. For disjoint specializations (many NULLs possible).
• Option 8D (single relation with multiple type attributes): one relation with Boolean type flags, for overlapping subclasses.

Categories (union types) are mapped using a new surrogate key.

Example. EMPLOYEE(Ssn, Name, Address) with disjoint, partial subclasses SECRETARY(Typing_speed) and ENGINEER(Eng_type).

Option 8A gives:

• EMPLOYEE(Ssn, Name, Address)
• SECRETARY(Ssn, Typing_speed), Ssn FK to EMPLOYEE
• ENGINEER(Ssn, Eng_type), Ssn FK to EMPLOYEE

Option 8C gives EMPLOYEE(Ssn, Name, Address, Job_type, Typing_speed, Eng_type), with NULL in the attributes that do not apply.

In an object database, persistence means that an object continues to exist after the program that created it ends. ODMG-style systems (and ODL/OQL bindings) have transient objects (lost at program end) and persistent objects (stored in the database). Persistence can be specified in two ways.

1. Persistence by naming. The programmer gives an object a unique, persistent name (a handle) in the database, using a bind-type operation, and that object becomes persistent. The name acts as an entry point from which the object can be retrieved later, using the name in another program. For example:

d = new Department;          // transient so far
d.bind("Computer_Dept");     // now persistent, with name
...
x = lookup("Computer_Dept"); // retrieve in a later session

Naming is a simple mechanism, but practical only for a small number of objects, since each needs its own distinct name. Names are normally given to extents (collections) or a few root objects.

2. Persistence by reachability. An object becomes persistent if it is reachable, by following references, from another persistent object (a named root). Persistent objects form a graph, and every object reachable from a persistent root through references is automatically persistent. For example, if Computer_Dept is persistent and has a set of Employee references, adding a new Employee object to that set makes it persistent too, with no explicit naming. Objects that become unreachable from all roots are no longer persistent and may be garbage collected.

The two methods are used together: a few objects are made persistent by naming (the roots), and the rest of the data becomes persistent by reachability from them.