CS 220 P

Topic 0: Introduction

​

Professor Sharad Mehrotra

DBH 2091

sharad AT ics uci edu

949 824 5975

​

Office Hours: by appointment

Loc: DBH 2091

​

​

1

Outline

• Introduction to the course / logistics

​

• A walk down memory lane - a historical perspective on data models (TODAY)

​

• Introduction to Data Management technologies (NEXT CLASS)

2

CS 220P Course Website

• All course information will be posted online

​

• URL: https://sites.google.com/uci.edu/compsci-220p-fall-2025?usp=sharing

​

​

• Class Notes available before class on the Web.

3

Teaching Assistants

Office hour: Mon 1-3pm

CompSci 220P

Shiyuan Zhou (szhou20@uci.edu),

​

Keming Li (kemingl1@uci.edu)

​

​

DATA 220P

Nada Lahjouji (nlahjouj@uci.edu)

​

4

• nlahjouj@uci.edu

Course Textbook

• Database Systems Concepts, Silberschatz, Korth, and Sudarshan (7th edition)
• Chapters 1-9, 11, 14,17
• Link: http://www.db-book.com/

​

​

5

​

• Developed by a Swedish Company MySQL AB - 1995
• Purchased by Sun Microsystems (~ 1B) - 2008
• Oracle Purchased Sun (~ 8B) - 2009
• Now MySQL is an open-source relational database supported by Oracle
• It is one of the most popular SQL databases for small/medium corporations. Amongst the most popular for Web applications.
• Works across multiple platforms --windows, Mac, Linux, Unix, BSD, Symbian, etc.
• See class Website for details on how to download and install.

6

Course Requirements

​

• Assignments (one per topic) - 50 %

​

• Mid-term Exam - 20 %

​

• End-term Exam - 30 %

7

Assignments

​

• Submission using Gradescope
• accessible via Canvas

​

• Late submission:
• Sorry -- No grace period after due date
• Except under exceptional circumstances
• Job interviews, out of town trip, breaks etc. do not qualify as exceptional circumstances!

​

• Working in Groups
• do your assignments in groups of size 3
• Peer learning enables deeper understanding, get better grades
• get used to working in groups (important to employers)
• if you prefer working by yourself, you can do assignments individually
• you are not stuck with a group member the whole quarter, you can change groups in between assignments if your current group does not work for you

​

8

Exams

• Midterm on 2^nd class of Week 6
• topics covered -- Material covered until Week 5

​

• End term Exam - during exam week
• comprehensive, but focused on topics covered after midterm exam.

​

​

​

​

9

Academic Honesty Requirement

​

• Receiving/giving assistance to other students taking the exams, including discussion the exam with students in another section of the course, is strictly disallowed

​

• For assignments, you will submit one assignment per group. You will neither ask other students to, or agree to other students to put your/their name on assignments for which you/they have not contributed from the beginning.

​

• The course follows a Zero-tolerance policy to cheating, no exceptions. Violating the academic honesty code on assignments, quizzes, or exams will result in automatic F in the course!

10

Class Discussions & Interactions

​

• ED:

​

• questions will be answered by us during 2 hours of each weekday (typically between 11 am to 12 pm and 9 pm to 10 pm)

​

• Accessible from class web site on Canvas

​

11

Material Covered in CS 220P

​

• Programming with Databases
• Modeling and design
• Database programming using SQL
• Extended data types &UDFs
• Data Analytics
• semi-structured data, graph data
• NL2SQL

Database Course Menu @ UCI

​

12

MCS

​

CS 220P --- grad level 122A

CS 222P – MS. Version of 222

CS223P – MS. Version of 223

CS 224P – intro to big data

UNDERGRADUATE

CS 122A ---- SQL

CS 122B --- advanced web based applications

CS 122 C ---- same as 222

CS 122D ----- new/emerging data systems

Grad Classes

CS 222 --- implementing databases

CS 223 -- transactions, distributed databases

CS 224 -- emerging research trends in DBMS

Database Management Environment

13

Applications/queries

Query processor

Storage manager

User

Metadata

Database

Database: Collection of interrelated information about the world being modeled.

DBMS: General purpose software to define, create, modify, retrieve, delete and manipulate a database

Vendors: Oracle, IBM, Microsoft. Amazon, Google, Cloud based solutions by SalesForce, Couchbase, Aerospike…...

DBMS

The Paleolithic Period … pre database systems era

• There were no general-purpose tools for managing large volumes of data…
• OS provided resource management
• Data was stored in files
• Applications performed data management functionalities
• Fault-tolerance
• Concurrency control
• Reliability
• Optimizations
• …
• Such functionalities had to be re-implemented for each application

14

Consistency Example

Consider a withdraw application that read the account balance, deducts money, and writes the new account balance.

​

Now consider Tom and Jerry executing the deduct application concurrently.

​

In file systems, the last writer “wins” !

​

If both Tom and Jerry read the balance prior to the other updating it, irrespective who who writes last, the balance is wrong!

​

Unlike file systems DBMS do not allow such inconsistencies to occur!

​

​

15

Reliability Example

Consider that you are able to get a ticket for the FIFA world cup finals in New Jersey

​

So you reserve a ticket from Orange County to EWR

​

The reservation is written into the file

​

Unfortunately, an untimely power outage prevents the file from being saved, or worse,

causes the file to be corrupted.

​

you are denied the flight with no evidence of reservation (airline sold your seat to someone else)

​

​

you lose your money!

​

​

Unlike file systems, database systems provide guarantees that applications effects are not lost despite all types of failures!

​

16

The Neolithic Period…the arrival of Database Systems

• Early file systems evolve into general-purpose data management tools.

​

• DBMS Goals:
• Efficiency and scalability (faster than files)
• Management of large heterogeneous types of structured data
• High reliability
• Information sharing (multiple users)

​

17

Data Model

• Database systems are identified by the data model they support

​

• Data Model are a set of concepts and tools used to model and represent data in the database

​

​

• A data model enables user to specify the schema (metadata) of their database and also ways to access the stored data.

​

​

​

18

Schema versus Instance

• Schema:
• Overall design, structure, and constraints over the database
• Referred to as metadata
• Changes infrequently
• Instance:
• Set of data currently instantiated in the database
• Changes frequently

​

19

​

(John, 10), (Cindy, 15), (Martha, 10)

(10, Toy, John), (15, Sales, Cindy)

Dept

SCHEMA

​

Tables

Emp (ename, dep#)

Dept(dep#, dname, mgr)

Constraints

each department has

a single manager

​

Instance

The Dark Ages ….

• Network & hierarchical data models
• Objects pointing to each other forming networks and hierarchies, resulted in data spaghetti
• Applications needed to chase pointers
• There was little data abstraction or separation of concerns
• little difference between physical data representation and logical data representation
• optimization was entirely left to application writers
• There were no clean data management languages
• Unless you are a Cobol fan!

​

20

The Relational Era..

• Relational model proposed by Codd
• Everything is a relation
• Query consists of algebraic composition of a few powerful operators
• Equivalent to a first-order relational calculus

​

• Primary features
• Simple clean data representation
• solid mathematical basis
• data abstraction
• Users did not need to be concerned about how data is stored physically
• simple declarative query language
• User’s specify what to compute not how to do it.
• optimization by the system

​

21

21

Relational Model

• Example of tabular data in the relational model

22

Customer-

name

Customer-id

Customer-

street

Customer-

city

Account-

number

Johnson

​

Smith

​

Johnson

​

Jones

​

Smith

192-83-7465

​

019-28-3746

​

192-83-7465

​

321-12-3123

​

019-28-3746

Alma

​

North

​

Alma

​

Main

​

North

Palo Alto

​

Rye

​

Palo Alto

​

Harrison

​

Rye

A-101

​

A-215

​

A-201

​

A-217

​

A-201

Attributes

A Sample Relational Database

23

Data Abstraction supported by Relational Model

• Hiding system complexity and physical storage details from users and application programs

24

Physical Level

Logical Level

View1

View 2

View n

Physical description of data and storage organization

higher level representation

(that describes logical structure of data)

Customized views

(that describe how users see data). Closer to how applications may view data

​

Data Independence

The ability to write programs at one level of abstraction and have the programs still work when a lower-level changes.

​

• Logical data independence:
• Protecting applications from change to logical structure of data

​

• Physical data independence:
• Protecting applications from changes to physical storage of data.

​

25

Examples

• You are using a given DBMS & decide to change the physical record layout for the Customer table. The logical schema stays the same. All application programs will continue to run, because of ‘physical data independence.’

​

• You change the Customer table schema by adding a new column. All old programs still run, because the relational model gives (some) ‘logical data independence.’

​

• However, if you drop the Customer column, probably many programs will no longer run, because they used that column in their view of the data.

​

26

Types of Data Model

​

• Different models at different abstraction levels:

​

• conceptual model: defines data at level useful for specific tasks /roles. (e.g., entity-relationship model)

​

• logical model: describes data at logical level (e.g., relational model, object-oriented model, semi-structured model such as XML and JSON)

​

• physical model: usually very database system specific and part of the data definition language of the underlying database

​

27

Entity-Relationship Model

• Example of schema in the entity-relationship model

28

Depositor

Entity Relationship Model (Cont.)

• E-R model of real world
• Entities (objects)
• E.g. customers, accounts, bank branch
• Relationships between entities
• E.g. Account A-101 is held by customer Johnson
• Relationship set depositor associates customers with accounts

​

• Widely used for database design
• Database design in E-R model usually converted to design in the relational model (coming up next) which is used for storage and processing

29

Data Definition Language (DDL)

• Specification notation for defining the database schema
• E.g.�create table account (� account-number char(10), balance int);

​

• DDL compiler generates a set of tables stored in a data dictionary

​

• Data dictionary contains metadata about the tables

30

Simple Query Language -- Algebra & Calculus

​

Customer(CustomerID, Name, City, Age)

​

Relational Algebra

​

π_Name​(σ_{City=′Irvine′ ∧ Age>30​}(Customer))

​

Relational Calculus

​

{t.Name ∣ t∈Customer ∧ t.City=′Irvine′ ∧ t.Age>30}

31

SQL -- intergalactic Data Speak!

• Two classes of languages
• Procedural – user specifies what data is required and how to get those data
• declarative – user specifies what data is required without specifying how to get those data
• SQL is a declarative language
• based on aspects of relational algebra & calculus.
• at its heart SQL maintains its simplicity and elegance of relational languages.

​

• SQL quickly became the most widely used query language

32

SQL in the DML Role

Inserting Data:

INSERT into account values (‘one’, 10), (‘two’,20);

​

​

Retrieving Data:

SELECT * from account;

​

​

Basic SQL has limited expressibility

• cannot implement any arbitrary function in SQL

​

Application programs generally access databases through one of

• Language extensions to allow embedded SQL
• Application program interface (e.g. ODBC/JDBC) which allow SQL queries to be sent to a database

33

Data Wars (1)

​

• Codasyl versus relational debates began…
• Heated arguments during early SIGMODS
• Codasyl: relational model is too simple, applications built using it will never scale in performance.
• Relational: network/hierarchical models have no formal basis, are too complex, and unmanageable as application complexity increases.
• Relational model found many supporters
• Specially at universities
• Its simplicity was enticing

​

34

Data Wars (2)

​

• Many projects started off trying to implement a relational DBMS
• System R @ IBM Almaden (Chamberlin, Boyce, Selinger, …..)
• Ingres @ Berkeley (Stonebraker, ..)
• These early systems led to the technologies that drive modern data management
• Early prototypes became products
• DB2 & Ingres
• Principle designers from both the System R teams & Ingres left to start companies
• Oracle, Sybase
• Early relational companies went door to door converting industry to the relational model
• Industry got hooked on to the simplicity of writing complex applications in relational model
• Boeing among the first converts (early adopter of DB2)
• CIA and government agencies (early adopters of Oracle)

35

Era of Object-Oriented Programming

• As the data wars were settling with the victory of the relational model (Codd got a Turing Award for it!), the world of programming discovered the benefits of object-orientation.

​

• Emergence of languages such as Smalltalk, C++

​

• Advantages of OO:
• Object that encapsulated methods to access/manipulate objects.
• Classes & Inheritance.
• …

​

• Such languages allowed us to look at data at a much more conceptual level (objects, relationships) compared to the tabular representation offered by Relational databases

36

Pointer’s Strike Back…

• Complex objects in emerging database applications could not be effectively represented as records in relational model.
• Representing information in relational systems required complex and inefficient conversion into and from the relational model to the application programming language.
• Object databases provide a direct representation of objects to DBMSs overcoming the impedance mismatch problem

37

Application

data structures

Relational

representation

RDBMS

Copy and

translation

Transparent

ODBMS

data transfer

Object Oriented Databases

• Evolved as persistent Object Oriented Programming Languages:
• Start with an OO language (e.g., C++, Java, SMALLTALK) which has a rich type system
• Add persistence & concurrency to the objects in programming language where persistent objects stored in databases

​

38

CS 220P

Notes 01

38

Disadvantages of ODBMS Approach

• Low protection
• since persistent objects manipulated from applications directly, more changes that errors in applications can violate data integrity.
• Non-declarative interface:
• difficult to optimize queries
• difficult to express queries
• But …..
• Some ODBMSs offered a declarative query language OQL to overcome the problem.
• OQL was very similar to SQL and could be optimized effectively.
• OQL could be invoked from inside ODBMS programming language.
• Objects can be manipulated both within OQL and programming language without explicitly transferring values between the two languages.
• OQL embedding maintains simplicity of ODBMS programming language interface and yet provides declarative access.

39

CS 220P

Notes 01

39

POSTGRES

• Introduced object orientation into relational DBMSs.
• Fundamental Concepts.
• Each record has an OID.
• Types: rich set of types available for columns. Allowed users to define new types.
• Type system supported inheritance
• User could define classes
• Users could add new functions & Operators that could be called from within POSTQUEL.
• and a bunch of additional features including triggers (we will learn these later).

​

40

CS 220P

Notes 01

40

The Return of the Relations … POSTGRES

• Relational model evolved into ORDBMSs that include “best of” object-oriented concepts

​

• Amongst the first ORDBMS prototype built @ Berkeley� POSTGRES Illustra Informix

​

• Has had major impact on major commercial DBMS which have all migrated to ORDBMS model.

​

• SQL3 supported by modern databases adapted many of the concepts developed in Postgres

41

CS 220P

Notes 01

41

bought by

commercialized

Dawn of New Era - the World Wide Web!

• WWW led to the proliferation of semi-structured data & specialized data stores for things such as graphs…
• Sample Technologies: OEM, Lore, XML DBs, XQuery
• Key Takeaway: Relational DBs extended with XML & semi-structured database support

​

42

CS 220P

Notes 01

42

OID1: {

name → "Sharad",

affiliation → OID2 }

​

OID2: {

dept → "CS",

univ → "UCI" }

​

​

{

"name": "Sharad",

"affiliation": {

"dept": "CS",

"univ": "UCI"

}

}

​

​

OEM Graph (Stanford)

JSON tree

And then Came the Clouds….

led to two major developments.

​

1. cloud databases - data moved from prem to cloud

​

• internet scale applications - big data and no SQL movement.

​

UCI played a major role in both….

​

​

​

​

43

Cloud Databases and Serverless Computing

Motivation: Scalability, elasticity, zero-maintenance

•Key Systems: Snowflake, BigQuery, Redshift, Aurora, CosmosDB

•Takeaway: Data-as-a-service, disaggregation of storage/compute

​

​

44

NetDB2 - Database Service

• Developed in collaboration with University of California, Irvine , IBM Silicon Valley Lab, and IBM Almaden

​

• Possibly the very first Database as a Service

​

• Deployed on the Internet

​

• UCI was the first pilot school

​

• Used by 15 universities and more than 2000 students to help teaching database classes

​

• Later hosted by IBM Toronto, Scholars Program

(Feb, 2002)

45

For Us: Maintenance and Administration!

Database as a Service, Hacigumus, Iyer, Mehrotra, ICDE 2002

Internet Scale Applications…

•led to the big-data & NoSQL movement.

•Key Systems: GFS, MapReduce, Bigtable, Hadoop, MongoDB, Cassandra

•Takeaway: One-size-fits-all broken → Polyglot systems

​

46

AsterixDB System Overview

47

ASTERIX Cluster

Hi-Speed Interconnect

47

Asterix Client Interface

AQL Compiler

Metadata Manager

Hyracks Dataflow Engine

Dataset / Feed Storage

LSM Tree Manager

…..

Asterix Client Interface

AQL Compiler

Metadata Manager

Hyracks Dataflow Engine

Dataset / Feed Storage

LSM Tree Manager

(ADM = ASTERIX Data Model;

AQL = ASTERIX Query Language)

​

The return of SQL in Big Data

•Motivation: Analysts love SQL

•Key Systems: Hive, Spark SQL, Spanner, Presto, Snowflake

•Takeaway: SQL reasserts itself on distributed, cloud-native systems

​

48

And Now to the current times … AI/ML and Data Systems

Motivation: Data is fuel for AI

•Key Systems: Feature stores, vector DBs (FAISS, Pinecone, Milvus), RAG pipelines

•Takeaway: DBs evolving into AI-native infrastructure

​

SQL & Relational databases still remain the most important building blocks of modern data infrastructures.

​

Next class: Peek inside relational database systems

​

​

49

The AI progress - the new revolution

• Just when relational model had driven out object-oriented database technology, WWW led to the proliferation of semi-structured data & specialized data stores for things such as graphs….

​

• We will continue this story towards the end of the course when we peek at the No/New SQL movement of the last decade …

​

​

For now, note that relational system remains the most important data management technology to date, and most No/New SQL have roots in the relational databases.

​

Next class: Peek inside relational database systems

50

CS 220P

Notes 01

50

51

CS 220P

Lecture 2: A peek into the DBMS technology … �

• Professor:
• Sharad Mehrotra
• DBH 2082
• sharad AT ics uci edu

​

​

Relational Databases

• Model everything as a relation/tables.
• High level declarative query language - SQL.
• E.g. find the name of the customer with customer-id 192-83-7465� select customer.customer-name� from customer� where customer.customer-id =� ‘192-83-7465’

​

• SQL query is translated down to a set of operators arranged into an execution pipeline

​

53

How Relational Databases Work

• SQL query translated down to a set of operators arranged into an execution pipeline
• Databases support variety of different implementation of these operators.
• optimizer chooses the specific implementation based on what it deems would minimize cost of execution. This is referred to as the query plan.
• Query processor executes the query plan.
• Execution of the query is implemented as a single atomic operation called a transaction.
• If failures occur during transaction, effect of the transaction is rolled back on recovery completely.

54

Layered Structure of a DBMS

55

Lock

Manager

Transaction

Manager

Access

Methods

(Indices)

Disk Space and I/O Manager

Log

Manager

Data

Files

Index

Files

Catalog

Files

WAL

SQL

Query plans

API calls

Storage Manager

Key DBMS Components

• Query Parser and Optimizer
• Given SQL query, generates a plan for their execution
• Optimization consists of rewriting plans into more efficient execution plans based on rules and/or estimating cost of execution.
• Storage Manager
• Query Processor
• Orchestrates execution of the query given a plan. Supports implementation of relational operators.
• Storage Manager
• Support APIs to provide access to data stored in the database.
• Provides the abstraction of a record-oriented file system where file is a set of records.
• Supports access methods for efficient associative search.
• Transaction Manager
• Support consistency in presence of concurrent access and reliability in the presence of failures
• Distributed Data Management

56

Need for Query Optimization

• Consider two tables
• Employee(ename, salary, department)
• say 1000 entries
• Manager(mname, department)
• say 10 entries
• Query:
• List the names of employees for the department of which Sharad is the manager

​

57

Strategy 1

• For each entry M in Manager
• read record M
• For each entry E in employees
• read Entry E
• If (E.department == M.department) and (M.mname = “sharad”)
• print E.ename
• Cost Analysis:
• Outer loop 10 iterations. 1 read operation each time.
• Inner loop 1000 iterations. 1 entry read each time.
• total number of reads = 10 + 1000*10 = 10,010.

​

58

Strategy 2

• For each entry M in Manager
• If M.mname = “sharad”
• temp = M.department
• For each entry E in Employees
• If E.department == temp
• print E.ename
• Cost Analysis:
• first loop 10 iterations. 1 read operation each time.
• Second loop 1000 iterations. 1 read operation each times.
• Total number of reads = 1010.
• Strategy 2 is 10 times better compared to 1.

​

• Optimizer’s Goal: Often “bad” plans can be orders of magnitude worse compared to “good” ones. The optimizer Chooses a ”good” plan from an exponential number of them with the goal to ensure that the chosen plan is ”good” 🡪 might not be the best!

59

Need for Indexing

• Consider a table with 100 million records
• E.g., each record contains information about sale of an item to a customer
• Let us assume size of each record is 1K bytes.
• Thus, size of table is 100 Gbytes
• Now imagine searching to records of sales of “ipad 5”.
• At 250 Mbytes/sec, it will take 400 seconds to perform the search!

​

• Indexes will help make such searches fast …
• They can help in many other ways as we will learn later.

​

• Let us see how…..

60

How indexes help!

• Create an index file that contains for each record r in the data file, a record that contains value of product-name (e.g., ipad5) in r and pointer to r in data file.
• Each record in index file == 12 byte product name + 4 byte pointer = 16 bytes.
• Size of index file 1.6 GB.
• Time to search for ipad5 records in index @250MB/sec approx. 6 seconds.
• Say there are 100 records of ipad 5. Cost of following 100 records to read from data file ~ 20ms * 100 == 2sec.
• Total time to find ipad 5 query --- 6 + 2 = 8 seconds.
• Order of magnitude better compared to searching data file directly!
• Much more on indexing later and how it helps ….

61

…

…

<ipad 5, John ,…..$399, 22 Main Sreet.>

<ipad pro, Bob ,…..$999, 22 1st Sreet.>

<ipad 5, Tim ,…..$399, 22 1st Sreet.>

​

…

…

<ipad 5,ptr.>

<ipad 5,ptr.>

<ipad 10,ptr.>

Index File on product-name

Data File

Large Records – each 1K, 100M records

Large file – 100GB

Small Record – each 16 B, 100M records

small file – 1.6GB

Transaction Concept

• Atomicity:
• all or nothing execution.
• Consistency:
• execution of a transaction leaves system state as well as the state of the real world consistent.
• Isolation:
• partial effects of a transaction are hidden from each other.
• Durability:
• a successful transactions effects survives future system malfunctions.

62

Example of Transaction

• Withdraw $100 checking account using an ATM.
• Atomicity:
• account debited if and only if t user gets money from the ATM
• Consistency:
• balance of account is always positive.
• Isolation:
• concurrent execution of withdraw, deposit, transfers does not result in an incorrect balance of account.
• Durability:
• after withdraw terminates, and the ATM dispenses money account reflects that $100 withdrawn despite failures.

63

Motivation of Isolation

• Consider two transactions--
• read account A, debit the value by $100 and write the new value to A.
• read account A, credit the value by $200 and write the new value to A.
• Let initial value of A be $1000.
• Final value should be $1100.
• Consider the following execution if concurrency is permitted:
• read1(A,1000) read2(A,1000) write2(A,1200) write1(A,900)
• for the above execution the value of A is 900!

64

Importance of the Transactions

• Transaction concept supports:
• simple failure semantics -- either all the effects of the transaction appear or none do-- all or nothing
• an isolated view of the world -- protection from partial effects of concurrently executing transactions
• Makes application development easy
• complex, possibly distributed applications that share data and resources can be developed without explicitly dealing with synchronization and fault-tolerance.

​

65

Transactions versus Other Concurrent Programming Environments

• Concurrent programs prevalent in a variety of other areas in CS
• operating systems, parallel programming, distributed systems.
• support Powerful Language Constructs:
• to specify concurrent behavior of applications (programmers responsibility to deal with failures and concurrency issues).
• In contrast transactions relieve the application programmers of these tasks.

66

What they offers

• Data abstraction & independence
• Reduced Application Development Time

​

• Efficient Data Access

​

• Concurrent access (without compromising consistency)
• Failure resilience

​

• Data Integrity and security

67

Key Database Technologies

Powerful Data Models and query languages

Storage Manager, Indexing & Query Processing

Transaction Manager

Views & fine-grained SQL level authorization

CS 220 P

Lecture 2: Introduction to the DBMSs�

Professor:

Sharad Mehrotra

DBH 2082

sharad AT ics uci edu

​

​

Relational Databases

• Model everything as a relation/tables

​

• High level declarative query language - SQL.
• E.g. find the name of the customer with customer-id 192-83-7465� select customer.customer-name� from customer� where customer.customer-id =� ‘192-83-7465’

​

• SQL query is translated down to a set of operators arranged into an execution pipeline
• Databases support variety of different implementation of these operators.
• optimizer chooses the specific implementation based on what it deems would minimize cost of execution. This is referred to as the query plan.
• Query processor executes the query plan.
• Execution of the query is implemented as a single atomic operation called a transaction.
• If failures occur during transaction, effect of the transaction is rolled back on recovery completely.

​

69

Database Management System Architecture

Database and

Indices

Transaction

Manager

Buffer manager

File system

Metadata

and data

dictionary

compilers

evaluator

optimizer

Query processor

Storage manager

Application Queries Schema changes

Key Database Technologies

• File Management
• provides a file abstraction as a collection of records stored in disk
• Index Management and Access Methods
• implements techniques for associative access to data
• Query Optimization and Processing
• given a query and data storage structures, determines an efficient strategy to evaluate the query.
• Transaction management
• ensures consistency of the database in presence of concurrent transactions and various types of failures
• Catalog Management
• maintains database schema information
• Authorization and Integrity Management
• tests for integrity constraints and user authorization

Storage Media and their Properties

• Random Access Memory
• ‘volatile’ -- does not survive system failures
• Static versus Dynamic
• Static RAM - very fast, very expensive, used in caches
• Dynamic RAM – 10X slower compared to SRAM, cheaper, used as main memory
• random access is very fast
• Capacity typically limited to fit the entire database.

​

Storage Media and their Properties

​

• Disks
• Non-volatile storage – content survives power failure
• Data needs to be transferred to main memory prior to being processed.
• Unit of storage & transfer -- blocks
• Solid State Disk (SSD) versus Magnetic Disks
• SSD - more expensive (30X), faster, no moving parts, less power, require erasure before writing, asymmetric read/write properties, blocks wear out after ~100K writes, seq. read/write about 1.5 times faster than random
• Magnetic disks -- cheaper, not as robust, more power, seq. access much faster than random.
• Tape
• Really cheap, sequential I/O devices. Handy for backups, sometimes for archival.

Databases and Storage Devices

• Due to capacity, cost, volatility factors databases traditionally stored in disks.
• Data brought to main memory for processing from disks
• Many ways to interface memory with disk resident data

Virtual memory:

• VM size limited to max address generated by CPU
• Existing VM does not support durability

File system:

• provides a more powerful mapping between memory and disk storage
• A bunch of tricks used ensure that high latency of secondary storage does not impact application response time and system throughput (access disks asynchronously with active applications; prefetch data before application needs it; intelligent caching techniques)

Functional Abstraction of a Simplistic DBMS

beginT

SQL

SQL

endT

beginT

SQL

SQL

endT

Query Processor

optimizer

Record-oriented file system

Basic file system

Buffer manager

Hardware

SQL statements

Read write records, scan relations

Get page containing tuples

Read/write file pages

Access plan

Basic File System

• Provides the abstraction of a file where a file is an array of fixed size blocks
• Hides the disk geometry -- cylinders, tracks, sectors, slots and other functional components like arms, head, etc. such that the programs do not need to deal with these complexities
• Operations supported:
• create a file,, delete a file, open a file, close a file, extend a file
• read (set of) file blocks into buffers in memory
• write (set of) file blocks

​

Basic File System Design Issues

• File allocation: how to allocate blocks on disk to a file.
• Contiguous allocation: file stored in contiguous disk blocks. Blocks for storing file found using either of best-fit, worst-fit or first-fit policies.
• +ve: provides fast sequential scan of file
• -ve: fragmentation, difficult to enlarge files
• Linked allocation: file is a linked list of disk blocks
• +ve: prevents fragmentation, easy to enlarge files
• -ve: slow for both sequential and random access
• Index allocation: file implemented using fixed size blocks pointed to by an index (e.g., B-tree). Popularized by Unix
• +ve: good random access, easy enlargement, no fragmentation.
• -ve: poor sequential access performance
• Extent based allocation: file is a collection of clusters of consecutive disk blocks (extents) where collection maintained using linked lists or index
• Most popular approach with vendors.
• Free space management: information about which blocks are free

​

Buffer Management

• Makes file pages addressable in memory and coordinates writing of pages to disk with other components to guarantee transactional properties

​

• Acts as a mediator between basic file system and record-oriented file system

​

• Buffer frames maintained in main memory. When a request for file page access comes, check if page in buffer. Else get a free frame and load file page into buffer

Database Buffer Management Design Issues

• DBMS buffer manager returns pointer to frame containing data instead of returning copy of requested page to caller.
• Efficiency: prevents unnecessary copying of data
• Allows sharing of data at finer granularity than a page
• 2 transactions T1 and T2.
• T1 and T2 update records r1 and r2 on same page
• if buffer manager allowed applications to copy data to their address space and rewrite updated versions, updates might be lost
• Novel page replacement strategies:
• Traditional LRU strategy used in OS works well only under the assumption of locality of reference which may not hold for DBMSs
• Since DBMS query language are declarative, system has much more information about reference patterns which it can exploit to improve caching performance of buffer manager

​

• Participates in protocols to implement consistency and reliability

Record-Oriented File System

• Provides the abstraction of a file as a collection of records.
• Records can be:
• fixed size or variable length
• short, long, or very long
• attributes can be fixed length or variable length
• simple or complex (e.g., containing set valued attributes)
• Operations supported:
• create, delete, open, close, alter, drop
• read, insert, update, delete record
• scan all records in a file
• Issues Involved:
• mapping records to pages
• file organization: organization of records in a file.
• Where to insert new records
• what mechanism can be used to retrieve records
• ​

Mapping Records to Pages

Page header

Tuple 1

Tuple 2

Tuple 3

Tu

ple 4

records grow this way

Directory grows this way

To access a record on a page, access record directory on page to get address of record on page

Mapping Records to Pages

• Fixed Length Records with fixed length attributes:
• to access an attribute, compute offset of beginning of record and add to it offset from beginning of record.
• Efficient: address computation done at compile time
• Rigid: records cannot span pages, or be extended with more fields, or change size of field
• Self Identifying attributes stored along with length:
• to access an attribute go to beginning of record and search for attribute name.
• Flexible: attribute length can be changed, more fields can be added.
• Expensive: address computation done at run time
• Two approaches represent two points on spectrum. Approaches used fall in between.

​

Evolution of Traditional Row Stores

• To appreciate how storage in databases evolved, we need to understand how database systems evolved.

​

83

Traditional Record Storage

Traditionally, storage was targeted towards On-Line Transaction Processing (OLTP)

• ATM, POS in supermarkets

Characteristics of OLTP applications:

• Transactions that involve small numbers of records (or tuples)
• Frequent updates
• Many users
• Fast response times
• Row stores designed as write-optimized storage for OLTP
• All columns of a record stored together contiguously on disk.
• Insert and delete a record in one physical write
• Easy to add new record

​

​

84

We could further improve write performance using log-structured merge tree

In traditional databases: In-place storage

1234, John Smith

3434, Mary Bla

…

Sailors Table file

1234, John Smith

2344, Peter Che

3434, Mary Bla

…

Sailors Table file

INSERT INTO Sailors VALUES(2344, Peter Che)

Expensive: random disk access for each INSERT (or UPDATE or DELETE)

�Log Structured Merge (LSM) Tree

1234, John Smith

4445, Jay Bla

…

1234, John Smit

3434, Mary Fu

…

…

4353, May Wilson

9879, Ray Smith

2344, Peter Che

INSERT INTO Sailors VALUES(2344, Peter Che)

RAM

HDD/SSD

Insert into memory storage

Periodically Merged (Compacted)

1234, John Smith

434, Mary Fu

4445, Jay Bla

…

Pushed to disk when chunk full

LSM Storage

• Facilitates high write throughput, i.e. many writes per second, e.g., Twitter
• Complicates reads: first read memory chunk, then all the chunks in disk… until we find the record
• Compactions: Merge multiple chunks into 1; handle deletes/overwrites

While LSM trees improved write performance and OLTP workloads, Column stores were designed for OLAP applications

Row and Column Stores

Suited for OLTP.

Insert/delete requires one physical write

​

Suited for OLAP.

Minimizes reading unnecc. data

Column Stores

​

• Key Intuition:
• Only read relevant columns (Example: Ad-hoc queries read 2 columns out of 20)
• Compression – single column can be highly compressed
• Column stores have better cache performance.

​

• Examples
• C-store, SAP Hana, DB2 BLU, Oracle 12c, …

​

• Only read necessary data, but might need multiple seeks

File Organization

• Entry Sequenced
• records inserted at the end of file
• requires reorganization to reclaim space freed by deletion
• supports scan of file in the order records inserted
• needs additional mechanisms to find particular record
• System sequenced
• system decides the order in which records stored
• space freed by deletion either reused immediately or reclaimed during reorganization
• Sorted on an Attribute
• keeps records sorted on one or more attributes
• fast to scan in sorted order
• insertion is expensive
• requires additional data structure to find particular records
• Indexed Organization
• file organized as an index using hashing or B-trees

​

Index Management and Associative Access

• Associative access: accessing records based on their attribute values.

​

• Index Files
• an index file declared over a (set of) attribute of the data file provides associative access to records in the data file.
• Index file contains pointers to disk blocks where the record corresponding to the value appear

Need for Indexing

• Consider a table with 100 million records
• E.g., each record contains information about sale of an item to a customer
• Let us assume size of each record is 1K bytes.
• Thus, size of table is 100 Gbytes
• Now imagine searching to records of sales of “ipad 5”.
• At 250 Mbytes/sec, it will take 400 seconds to perform the search!

​

• Indexes will help make such searches fast …
• They can help in many other ways as we will learn later.

​

Let us see how…..

92

How indexes help!

• Create an index file that contains for each record r in the data file, a record that contains value of product-name (e.g., ipad5) in r and pointer to r in data file.
• Each record in index file == 12 byte product name + 4 byte pointer = 16 bytes.
• Size of index file 1.6 GB.
• Time to search for ipad5 records in index @250MB/sec approx. 6 seconds.
• Say there are 100 records of ipad 5. Cost of following 100 records to read from data file ~ 20ms * 100 == 2sec.
• Total time to find ipad 5 query --- 6 + 2 = 8 seconds.
• Order of magnitude better compared to searching data file directly!

Much more on indexing later and how it helps ….

93

…

…

<ipad 5, John ,…..$399, 22 Main Sreet.>

<ipad pro, Bob ,…..$999, 22 1st Sreet.>

<ipad 5, Tim ,…..$399, 22 1st Sreet.>

​

…

…

<ipad 5,ptr.>

<ipad 5,ptr.>

<ipad 10,ptr.>

Index File on product-name

Data File

Large Records – each 1K, 100M records

Large file – 100GB

Small Record – each 16 B, 100M records

small file – 1.6GB

Types of Indices

• Let indexing attribute be A

​

• Clustered index: data file is sorted on attribute A on which the index is created.

​

​

• secondary index: data file is not sorted on the attribute A on which the index is created

​

• Clustered index incurs overhead during insertion/deletion but can help significantly during retrieval (we will see soon).

Organization of Index File

• B-tree Index: index file is organized as a B-tree
• Advantages:
• Supports range searches efficiently.
• E.g., retrieve all employees with salary between 100K and 200K
• Guaranteed good storage utilization
• Disadvantages:
• searching for a given record could take around 3-4 disk I/Os

​

Organization of Index File

​

• Hash Index: index file maintained as a hash file.
• Advantages:
• Looking for a specific record very efficient -- 1 disk I/O
• Disadvantages:
• cannot support range searches
• Exotics:
• modern databases are beginning to support novel data structures like R-trees, grid files, inverted lists to better serve emerging application requirements

​

​

B+ Tree Indexes

97

• Leaf pages contain data entries, and are chained (prev & next)
• Non-leaf pages have index entries; only used to direct searches:

P

0

K

1

P

1

K

2

P

2

K

m

P

m

index entry

Non-leaf

Pages

Pages

(Sorted by search key)

Leaf

Example B+ Tree

• Find 28*? 29*? All > 15* and < 30*
• Insert/delete: Find data entry in leaf, then change it. Need to adjust parent sometimes.
• And change sometimes bubbles up the tree

98

2*

3*

Root

17

30

14*

16*

33*

34*

38*

39*

13

5

7*

5*

8*

22*

24*

27

27*

29*

Entries < 17

Entries >= 17

Note how data entries

in leaf level are sorted

Hash-Based Indexes

​

• Good for equality selections.
• Index is a collection of buckets.
• Bucket = primary page plus zero or more overflow pages.
• Buckets contain data entries.
• Hashing function h: h(r) = bucket in which (data entry for) record r belongs. h looks at the search key fields of r.

​

99

Static Hashing

• # primary pages fixed, allocated sequentially, never de-allocated; overflow pages if needed.
• h(k) mod M = bucket to which data entry with key k belongs. (M = # of buckets)

100

h(key) mod N

h

key

Primary bucket pages

Overflow pages

2

0

N-1

Using an Index for Selections

• Cost depends on #qualifying tuples, and clustering.
• Cost of finding qualifying data entries (typically small) plus cost of retrieving records (could be large w/o clustering).
• In example, assuming uniform distribution of names, about 10% of tuples qualify (100 pages, 10000 tuples). With a clustered index, cost is little more than 100 I/Os; if unclustered, upto 10000 I/Os!

SELECT *

FROM Reserves R

WHERE R.rname < ‘C%’

Query Processing in DBMSs

Parsing and Translation

optimizer

Evaluation engine

Statistics about data

Select …

From …

Where ...

Internal relational algebra based representation of query

Optimized execution plan

Data and index

Sally 4000

Dick 9000

…

…

...

Query results

Need for Query Optimization

• Consider two tables
• Employee(ename, salary, department)
• say 1000 entries
• Manager(mname, department)
• say 10 entries
• Query:
• List the names of employees for the department of which Sharad is the manager

​

Strategy 1

• For each entry M in Manager
• read record M
• For each entry E in employees
• read Entry E

If (E.department == M.department) and (M.mname = “sharad”)

print E.ename

• Cost Analysis:
• Outer loop 10 iterations. 1 read operation each time.
• Inner loop 1000 iterations. 1 entry read each time.
• total number of reads = 10 + 1000*10 = 10,010.

​

Strategy 2

• For each entry M in Manager
• If M.mname = “sharad”

temp = M.department

• For each entry E in Employees
• If E.department == temp

print E.ename

• Cost Analysis:
• first loop 10 iterations. 1 read operation each time.
• Second loop 1000 iterations. 1 read operation each times.
• Total number of reads = 1010.

Strategy 2 is 10 times better compared to 1.

​

Optimizer’s Goal: Often “bad” plans can be orders of magnitude worse compared to “good” ones. The optimizer Chooses a ”good” plan from an exponential number of them with the goal to ensure that the chosen plan is ”good” 🡪 might not be the best!

Query Optimization

• Goals: to find the cheapest evaluation strategy for a query
• Stages of Optimization:
• algebraic manipulations: heuristics used to convert query tree into an equivalent but more efficient representation.
• perform selections and projections as early as possible.
• combine selections with cartesian products to make a join
• combine sequence of unary operations (selections and projections).
• look for common subexpressions in an expression.
• Cost based Analysis: given optimized representation produced after algebraic manipulation:
• generate all possible query plans and estimate their costs based on the statistical information and costs of each unary and binary operations.
• Best possible query plan chosen as an execution strategy.
• Number of plans considered even after heuristic are applied is exponential in the number of operators in query tree. It is important to choose a good plan since cost of generating plan amortized over multiple query executions.

Cost of Query Execution

• Access to disk: cost of reading, writing, searching data blocks. (i/o cost)
• Storage Costs: cost of storing intermediate files generated during query execution. (i/o cost)
• Computation cost: cost of in memory execution of operations. (cpu cost)
• Communication cost: cost of shipping the query and results from site to site or terminal where query originated. (communication cost)
• Total cost = I/O cost + w1* CPU cost + w2 *Communication cost
• Traditionally I/O cost considered most important

Databases Support the Transaction Concept

• Atomicity:
• all or nothing execution.
• Consistency:
• execution of a transaction leaves system state as well as the state of the real world consistent.
• Isolation:
• partial effects of a transaction are hidden from each other.
• Durability:
• a successful transactions effects survives future system malfunctions.

Example of Transaction

• Withdraw $100 checking account using an ATM.
• Atomicity:
• account debited if and only if t user gets money from the ATM
• Consistency:
• balance of account is always positive.
• Isolation:
• concurrent execution of withdraw, deposit, transfers does not result in an incorrect balance of account.
• Durability:
• After withdraw terminates, and the ATM dispenses money account reflects that $100 withdrawn despite failures.

Importance of the Transactions

• Transaction concept supports:
• simple failure semantics -- either all the effects of the transaction appear or none do-- all or nothing
• an isolated view of the world -- protection from partial effects of concurrently executing transactions
• Makes application development easy
• complex, possibly distributed applications that share data and resources can be developed without explicitly dealing with synchronization and fault-tolerance.

​

Transactions versus Other Concurrent Programming Environments

• concurrent programs prevalent in a variety of other areas in CS
• operating systems, parallel programming, distributed systems.
• support Powerful Language Constructs:
• to specify concurrent behavior of applications (programmers responsibility to deal with failures and concurrency issues).
• In contrast transactions relieve the application programmers of these tasks.

Concurrency Control

• Concurrent execution of user programs is essential for good DBMS performance.
• Because disk accesses are frequent, and relatively slow, it is important to keep the cpu humming by working on several user programs concurrently.

​

• Interleaving actions of different user programs can lead to inconsistency: (example next slide).

​

• DBMS ensures such problems don’t arise: users can pretend they are using a single-user system.

112

Consistency Challenge due to Concurrency

• Consider two applications-
• read account A, debit the value by $100 and write the new value to A.
• read account A, credit the value by $200 and write the new value to A.

​

• Let initial value of A be $1000.

​

• Final value should be $1100.

​

• Consider the following execution if concurrency is permitted:
• read1(A,1000) read2(A,1000) write2(A,1200) write1(A,900)
• for the above execution the value of A is 900!

Scheduling Concurrent Transactions

• DBMS ensures that execution of {T1, ... , Tn} is equivalent to some serial execution T1’ ... Tn’.
• Before reading/writing an object, a transaction requests a lock on the object, and waits till the DBMS gives it the lock. All locks are released at the end of the transaction. (Strict 2PL locking protocol.)

​

• Idea: If an action of Ti (say, writing X) affects Tj (which perhaps reads X), one of them, say Ti, will obtain the lock on X first and Tj is forced to wait until Ti completes; this effectively orders the transactions.

​

• What if Tj already has a lock on Y and Ti later requests a lock on Y? (Deadlock!) Ti or Tj is aborted and restarted!

114

Ensuring Atomicity

• DBMS ensures atomicity (all-or-nothing property) even if system crashes in the middle of a Xact (transaction).
• Idea: Keep a log (history) of all actions carried out by the DBMS while executing a set of Xacts:
• Before a change is made to the database, the corresponding log entry is forced to a safe location. (WAL protocol; OS support for this is often inadequate.)
• After a crash, the effects of partially executed transactions are undone using the log. (Thanks to WAL, if log entry wasn’t saved before the crash, corresponding change was not applied to database!)

115

The Log

• Used for Durability and Atomicity

​

• The following actions are recorded in the log:
• Ti writes an object: The old value and the new value.
• Log record must go to disk before the changed page!
• Ti commits/aborts: A log record indicating this action.

​

• Log records chained together by Xact id, so it’s easy to undo a specific Xact (e.g., to resolve a deadlock).

​

• Log is often duplexed and archived on “stable” storage.

116

• Today – brief introduction to some data management components

​

• Next class – conceptual modeling of data

117