The Database Training course is structured into five sections.

[Entire course notes PDF 1.87Mb]

This is the Data models course theme. In this section we introduce concepts for modelling data and language for communicating those models.
[Complete set of notes PDF 870Kb].

Databases are pervasive in modern society. So many of our actions and attributes are logged and stored in organised information repositories, or Databases
[Section notes PDF 227Kb].

• Where do we come into contact with databases?
• Supermarket inventories/EPOS
• Supplies, shopping habits, store locations, accounts
• Films (iMDB)
• Cast lists, shooting schedules, histories, budgets
• Department
• Students, courses, staff, payroll

These are all examples of relatively simple databases. All of the information is textual or referential.

• Not just traditional, numeric/textual
• Research 70s biased
• Digital media
• Video servers (atom/bbc/youtube)
• Multimedia databases
• Web site, collection of diverse data types
• Google, AltaVista
• Stock Exchange
• Futures, Currency markets, trends
• Databases comprising not only data, but modelling algortihms
• Microsoft's WinFS

Databases don't have to store just text. Increasingly Database servers are storing, indexing and delivering rich-media content, explicitly images, audio and video.

Microsoft's next generation File storage system (WinFS) is a relational database. From a user perspective, searching (the process of indexing content by keyword) is already mainstream. Users are moving away from rigid directory structures (files and folders) and towards keyword-tagged content.

• Not only in role
• Size
• Video server example
• Complexity
• Ford Puma™ example
• Ford staff organised by production line and car
• e.g. Each staff member answers to a 'part' manager (engines, bodyshell, chassis) and a 'car' manager (Puma, Mondeo, Ka)
• Expense
• User profiles and demands

We've seen that databases are used in a variety of contexts. Those roles imply properties of each of the systems. An interlinked text-only database (such as Unix/Linux's MAN pages) will require much less storage than a video archive.

Some databases are perceptually more complex. Ford's staff management model would be represented as a matrix (in this case 2 dimensional). Computers are very good at organising multi-dimensional space.

• Embrace diversity
• Data and semantic
• Database: related data, implicit meaning
• Sample/subset of real world
• real world with bounds
• Miniworld/Universe of Discourse

A single definition of a database is hard to come by. Dictionary.com defines a database as: a comprehensive collection of related data organized for convenient access, generally in a computer. The Wikipedia definition runs for several pages.

• Previous lab exercises
• Problem: reading data from a file
• Abstraction theme
• Basis of good OOP and further good P
• from encapsulation to software component analysis
• Layering, splitting data from design
• Solution: grammar (language guide) and data

In some of your previous lab assignments, or practical experience, you may have been faced with the problem of caching information persistently in a file, later to be reloaded.

When writing the data into the file, we are storing more than just that information. We are storing implicitly a design/grammar for that data. That implicit design is evident when accessing the file with a naive interface. If you try to read the data out in a different order, it fails.

A better solution is to split the way the information is stored from the actually information stored.

• DataBase
• Management
• System
• Collection of programs that enable users to:
• Define - patterns, boundaries, design
• Construct - populate to go live
• Manipulate - runtime changes
• data in a structured, organised store.

• Properties
• Data models and independence
• Requirements
• Categorisation of Database users
• DBMS components
• Architecture

When considering the database systems as a whole, we need to look at all the components, including elements that interact with the DBMS (users, whom we categorise for simplicity).

This course will contain a discussion of the components that make up the system and the way they interact (system architecture).

• Data models
• Relational data model (Oracle)
• Object data model (ObjectStore)
• Legacy systems
• Hierarchical data model
• Network data model

A data model is an invention. It is a construct that allows us to share an understanding of how the system works. As with all good constructs, it's an abstraction; a simplification; a story.

In this course we're going to look at the Relational model, where the database is organised into tables (relationals) and each row (tuple) within that relation is coded (keyed) to allow referencing between the relationals.

The Relational model, inspite of being innovated in the 1970s is still the most popular, underpining mainstream modern databases such as Oracle 10i and MySQL 5.0

As programming languages are becoming increasingly Object orientated, programmers require a means of persistently storing their Objects. Object Orientated Databases (OODBs) exist to fulfil this purpose. OODBs may ultimately replace relational databases, but it's not clear at this stage when.

• Beside Data model
• Number of users
• Number of sites
• Cost
• Types of access paths
• Generality, or inversely specificity

MySQL is a highly general database system, in that it supports many different designs. My mobile phone address book is a highly specific database system and as such is not easily extensible.

• Based on File processing
• Data definition implicit in
• Data
• Application program
• Example of one specific database
• Structure embedded into access program
• Coursework code re-use example

Earlier I made mention of this problem. Databases tie into the wider Software Engineering field. Within Software Engineering, post-development issues of code re-use, maintenance, future evolution etc. necessitate a logical flexible approach to program design. Databases are such an approach. In order to store information in a database you invest a small amount of time in explicitly structuring it, however you then get things like flexibility (data independence etc.) for free.

• General databases
• Separate Data definition and data
• Catalog/meta-data & tuples
• Data format/structure stored separately
• Program-data independence (e.g. Y2K)
• Changes in data format
• Alter data (tuples)
• Alter grammar (catalog/meta-data)
• We actually split program-data independence into:
• Logical
• Physical
• ...more in a second

• In object-orientated databases
• Objects consist of attributes and operations
• Operation defined by
• Header/Interface/Prototype or Signature
• Implementation
• Program-operation independence
• Implementation change hidden from user
• Collectively data abstraction

• Three tier data-model diagram
• Mappings, Data independence
• Logical
• between conceptual and external
• changes to conceptual without changing
• external schemas or application programs
• Physical
• between internal and conceptual
• changes to internal without changing
• conceptual or external schemas

• DataBase Management System
• Abstraction (i.e. program-data independence)
• Conceptual representation (data models)
• Multiple views and User Interfaces
• Data sharing and transaction processing
• Access restriction
• Redundancy removal/optimisation
• Persistent storage (Program objects) & Integrity
• Relationship management & Inference
• Backup and recovery

Here's a summary of what we need from a DBMS

• Database as 1y resource, DBMS as 2y
• Database administrators (DBA)
• Database designers
• End users
• Naïve - canned transactions e.g. bank/airline
• Sophisticated - engineers, scientists, query editors
• Stand-alone (personal databases/MS Access)

• Knock-on effects of database approach
• Enforcing standards
• Reduced Development time
• Adaptive to change (design changes)
• Up-to-date information (live database)
• Economies of scale
• centralising commonly required resources

...and this is what you get for free. These are the consequences, largely positive, of adopting a database approach to an information storage problem.

• Data, under the column heading
• Less easy to look at (volume issue)
• Fundamentally less interesting (more specific)
• Variety of tools for looking at it:
  • HeidiSQL, PhpMyAdmin, Sword
• Here's what a snapshot looks like:

• Data model
• Structure of the database
• Collection of basic operations
• Collection of behaviours/user defined operations
• Dependent on level of abstraction
• Tier diagram
• External (user views)
• Conceptual*
• Internal

• Entity
• Relationship
• Attributes
• Keys

What follows here is an introduction to the terms which make up the language that we use to describe data models.

• Data type, domain
• Simple or composite
• Single or multivalued
• Stored or derived
• Null

• Mechanism for unique identification
• Uniqueness constraint
• Strong and weak entities
• Key attribute
• Composite keys
• Multiple keys

• Structured Query Language (SQL or SEQUEL)
• Success of relational databases
• Developed for SystemR at IBM
• ANSI standardised
• SQL1 or SQL-86, ongoing extension
• SQL2 or SQL-92, current version
• SQL3 (1999), SQL2003
• DDL, DML(low-level) and VDL

A data model is a model that describes in an abstract way how data are represented in a business organization, an information system or a database management system - Wikipedia
[Section notes PDF 310Kb].

• Relational model
• Abstract operations on relations
• Set theoretic operations
• Relational-specific operations
• Basic algebra operations
• Union, Intersection, Difference
• Cross product

• Table as relation
• Row as tuple
• real world entity or relationship
• fact
• Column as attribute
• Domain

The concept of a relation is abstract, therefore we have a number of different ways of visualising it.

• Relation schema R(A₁, A₂, A₃.. A_n)
• Design side
• Assertion/declaration
• Relation state
• Data side
• set of n-tuples
• each one an ordered list of values
• 1NF: each value is atomic, no composite/multivalue

All the operations described in the next few sections are abstract. We're going to see how valuable they can be in processing real world data later.

• Two categories
• Set theoretic operations
• Union, Intersection etc.
• Relational specific
• Select, project and join

At this stage we're talking about set theoretical operators on the Relational model, not SQL instructions which confusingly have identical names and only similar behaviour.

• SELECT a subset of tuples from a relation
• Uses selection condition
• Evaluate each tuple to true of false
• False tuples discarded
• Sigma (s)
• output = s_(cond)(input_relation)
• Relation schema: R(output) = R(input_relation)
• Commutative

• PROJECT a subset of attributes for all tuples from a relation
• Pi (p)
• p_{<attribute list>}(R)
• If sublist is only non-key attributes
• might get duplicates
• Removes duplicates
• Attribute list:sublist example

The result set of the operation is itself a relational. That output relation will contain the same number of rows as the input, however it may contain a different number of columns; fewer if a subset of attributes is projected; more if derived or aggregated attributes are included.

• Select followed by projection
• Area clipping: rows then columns
• p_{<attr list>}
  (s_{(select_cond)}(R))
• Rename operation (r)
• Renames attributes list2 from list1
• r_{(new_attr_names)}(R)

• Attribute renaming only
• Cannot alter domain, or add/remove attr
• Rename operation (r)
• Renames attributes list2 from list1
• r_{(new_attr_names)}(R)
• Implicit renaming
• Order dictated by relational schema

• Binary operation: two relations
• Sets of tuples
• Union compatibility (same attributes)
• Union (R u S)
• Intersection (R n S)
• Commutative (R u (S u T) = (R u S) u T)

• Set difference
• Non-commutative (R-S != S-R)

• Cartesian product of two relations
• R x S
• Also known as
• Cross product
• Cross join
• Cross product diagram
• Introduction to complexity
• Computationally explosive

• Relational schema R(A₁, A₂,…,A_n)
• Relation state r or r(R)
• Set of unordered tuples
• r = {t₁, t₂,…,t_n}
• Each n-tuple is an ordered list of values
• t = <v₁, v₂,…,v_n>
• i^th value in t = v_i called t[A_i]
• r(R) subset of (dom(A₁) x dom(A₂)... x dom(A_n))

• Domain constraint
• For all v in t of r(R)
  v_i is an element of dom(A_i)
• Entity constraint
• K = SK_min
• t[K] != null
• Key constraint
• Superkey SK as identifying subset of attributes
• t₁[SK] != t₂[SK]

• Given two relations R₁ and R₂
• R₁ contains a foreign key (FK) that references
• A primary key (PK) in R₂
• R₁ referencing relation, R₂ referenced relation
• Shared domains: dom(FK) = dom(PK)
• Foreign exists: t₁ in r(R₁), t₂ in r(R₂)
• t₁[FK] = t₂[PK] || NULL

In this lecture we look at...
[Section notes PDF 233Kb].

• Recap: pulling data out of individual relations
• By row, by column
• Select and project
• Access across multiple relations
• Miniworld approximation
• Fragmenting entities by cardinality
• Tuples as entity fragments
• Relationships within relations
• Joins
• Join types (condition and unmatched)

• Relational model allows multiple relations to exist within one database schema
• Relations can be accessed individually or together (joins).
• Referential integrity
• Relations relating
• Pulling data out of single relations
• Select and project
• Pulling related data out of
• Multiple relations using Join

• Universe of Discourse, or Miniworld
• Miniworld is an incomplete model of the real world
• The relational data model as a model for the miniworld
• Approximation
• Separate and distinct entities
• Single complex entities
• Separate related entities
• Cardinality of relationships
• Each relation made up of attributes
• Values can be used as references

• Relation has a Primary key
• Tuple contains Primary key value
• Foreign keys
• Tuples can contain a reference to another relation's Primary key
• Just numbers

One number identifies a single tuple in one relation (local), one number identifies a single tuple in another relation (foreign).

• C programming language
• Memory addresses, or pointers
  

  int a=0;
  int b=0;
  a = &b;
  

• a points to b

In databases, typically done with unique identifiers (IDs) rather than memory addresses.

• Foreign key importing
  

  typedef struct car
  {
    int ID;
    char[] make;
    char[] model;
    char[] derivative;
    int optionID;
  } car;
  
  typedef struct option
  {
    int ID;
    char[] name;
    int price;
  } option;
  
  car c;
  option o;
  //...data structure populating
  c.optionID = o.ID;
  

• 1:0 relationships
• Single entity
• Uniquely indentifiable
• Candidate keys
• Primary Key
• 1:1 relationships
• Two entities, A and B
• 1 A relates to 1 B and vice versa
• 1:N relationships
• M:N relationships

• Two relations, A and B
• A side, B side, 1 side, N side
• 1:1 relationships
• Key can go on either side

• 1:N relationships
• Key cannot go on 1 side
• Has to go on N side

• M:N relationships
• Nowhere obvious for the key to go
• Create new pairing relation

• Phase change, different point in lifecycle
• Join operation
• Combines related tuples, conditionally
• From two relations
• Into single tuples
• Allows processing of relationships
• Among multiple relations

• Conditional (on join condition)
• Only combines tuples where true
• Cartesian product (conditionless)
• example of conditionless join
• all tuples combined
• R ⋈_true S
• ⋈, Binary operator
  e.g. R ⋈_{<join_condition>} S

• Equivalent to sequence
• Cartesian product (X)
• followed by Selection (s)
• ACTUAL_DEPENDENTS =
  s_SSN=ESSN(EMPNAMES X DEPENDENT)
• or
• ACTUAL_DEPENDENTS =
  EMPNAMES ⋈ _SSN=ESSN(DEPENDENT)

• Theta: A_i q B_j
  (A from R, B from S)
• q is comparison operator
  =,<,>,!=,>=
• A_i and B_j share the same domain
• Equi: A_i = B_j
• Theta join where q is =
• Natural: A_i and B_j are the same attribute
• in two separate relations (name and domain)
• * denotes natural join
• e.g. EMPNAMES * DEPENDENTS

• Inner joins
• not the only joins
• eliminate tuples without a matching counterpart
• i.e. tuples with a null value for the join attribute are discarded

• Outer joins control what's discarded
• Keep unmatched tuples in either
• Left, right, or both relations
• Left, right of full outer join correspondingly

In this lecture we look at...
[Section notes PDF 75Kb].

• Design communication techniques
• ER diagrams
• ER to relational mapping
• Entities to Objects
• Type Inheritance
• EER diagrams
• UML
• Web DB Integration

• Team based development
• Documentation
• Value of design over description
• DB sketching (left hand side)
• Concept more important than perfection
• Design iteration
• Mini-world as approximation
• Categorisation to create entities
• Verb’ing to create actions/relationships

• Design
• Catalog, Meta-data, Intension, or Database schema
• Entity type
• Relationship type
• State
• Set of occurences/instances, Extension, snapshot
• Entity set
• Relationship set

• Typically part of a system
• (Strong) Entities
• Product
• Customer
• Payment
• Relationships
• Sale

• Intuitive mapping
• Entities as tables
• Attributes as columns
• Relationships are more difficult
• Key sharing mechanism
• Foreign key references primary key
• Where to put the foreign key forms the intuitive guide to the rest of
  the mapping

• Step-by-step approach

1. Strong entities
• Create relation including (simplified) attributes
2. Weak entities
• Create relation inc. attr, foreign/pri key of owner
3. Binary relationship S:T, 1:1
• Choose relation, say S (with total participation) and inc. foreign/pri
  key of T
• inc. relationship attributes

• Specifies number of relationship instances a single entity can participate in
• S:T (1:1)
• An entity from table S can is related to one, and only one entity from table T
• 1:1, 1:N, N:M
• DEPARTMENT : EMPLOYEE
• EMPLOYEE : EMPLOYEE
• PROJECT : EMPLOYEE

5. Binary relationship 1:N
• Choose relation T (N-side) inc. foreign/pri key of S
6. Binary relationship M:N
• Create relation, inc. foreign/pri keys of S&T
7. Multivalued
• For each mv_attr, create new relation, inc. foreign/pri key of parent
8. n-ary relationship
• Create new relation, inc. all foreign/pri keys of participating
  entities

• Participation constraints
• Existence of an entity dependant upon
• being related to another entity
• via relationship type (left hand/design)
• Total (")/Existence
  dependency (double line)
• Every student must be in a faculty
• For every entity in the total set of students
• Partial ($) (single line)
• Some students are student_representatives
• There exists some entity(s) within the set of all…

• Library example
• Entities: Person, Book, Librarian
• Time-perspective implications

In this lecture we look at...
[Section notes PDF 86Kb].

• Not just one type of diagram
• ER Entities -> UML objects
• Adds scope to include methods

• Classes
• Attributes
• Methods
• Relationships
• Participation
• Cardinality
• Roles

• Notion of inheritance
• Java parallel
• 'is a' relationships
• Database Student
• is a Computer Science Student
• is an Engineering Faculty Student
• • is a Student
  • is a Person
• Inheritance hierarchies
• UML diagrams can be used to show inheritance

• Classes
• Relationships
• Inheritance

This is the DBMS Systems course theme.
[Complete set of notes PDF 625Kb]

In this lecture we look at...
[Section notes PDF 319Kb]

• Methods of getting data out
• The need for queries
• QBE
• SQL (design side)
• History
• Schemas and relations (CREATE)
• Data types and domains
• DROP and ALTER

• High (view) level
• Query-By-Example (QBE)
• Alternative to SQL
• Table driven (visually similar to relations)
• Rather than script driven, hence intuitive over learned
• Visual or text based
• User fills in templates
• Microsoft Access approach

• Record advancing
• Query designing
• Finite domain attributes
• Web search parallel

• P. print, I. insert, D. delete, U. update
• _VARNAME, copy field value into variable

• Structured Query Language
• (SQL or SEQUEL)
• Wikipedia reference
• Success of relational databases
• Developed for SystemR at IBM
• ANSI standardised
• SQL-1986 (SQL1), ongoing extension
• SQL-1992 (SQL2), current version (Oracle 9i)
• SQL-1999 (SQL3), regular expression matching, recursive queries
• SQL-2003, XML features, auto-generated columns

• Where follows here is a brief summary
• Oracle syntax
• Similar but not identical to MySQL/MSSQL
• General familiarity
• Query writing best learnt by doing it
• Lecture live-example
• Coursework 1 will be SQL
• Oracle (9i) SQL reference
• MySQL (5.0) SQL reference

• Keyword oriented language
• Keywords not congruous with Relational model
• Lots of different ways to write SQL
• Analogous to C/Java formatting
• if (b==2) { a=1; } else { a=0; }
• Recommend using case to differentiate attributes and keywords
• SELECT colour, size, shape FROM fruit WHERE weight>22;
• Oracle user accounts on Teaching database
• Namespace references, e.g. shared.cars

• Data definition commands
• CREATE
• SCHEMA <schema_name> AUTHORIZATION <a>
• or workspace
• Beware of names
• Name collisions produce odd behaviours
• SQL Schema embraces Tables (relations), constraints, views, domains, authorizations

• CREATE TABLE
• <schema_name>.<relation_name>
• (
• <attribute_definitions>
• <key>
• <constraints>
• )
• CREATE TABLE example (Oracle)
• Tables can (and should) be indexed by user
• e.g. <username>.<tablename>
• Normal login implies username
• Non-local table access

• Numeric
• ENUM
• NUMBER, NUMBER(i), NUMBER(i,j)
• Formatted numbers, i precision, j scale
• (number of digits total, after decimal point)
• Character-string
• CHAR(n) - n is length
• VARCHAR2(n) - n is max
• DESCRIBE output example
• Multi-database comparison of Datatypes
• Database legacy: limited storage necessitated efficient storage
• Does it need to be efficient anymore?

You might consider all SQL types as being conceptually similar to attribute types in the relational model, although in reality the implementation of these types in a DBMS only approximates the mathematical purity of unordered domain sets etc.

• Numeric
• TINYINT, INT, INT UNSIGNED
• FLOAT, DOUBLE, DECIMAL
• ENUM
• Character-string
• CHAR(n) - n is length
• VARCHAR(n) - n is max
• TINYTEXT, TEXT
• Beware different default/maximum lengths to Oracle
• BLOB
• Multi-database comparison of Datatypes

• Date and Time
• DATE
• Ten positions, components YYYY-MM-DD
• TIME
• Eight positions, components HH:MM:SS
• TIME(i)
• Time fractional seconds precision
• Adds i+1 positions
• TIMESTAMP
• optionally WITH TIME ZONE
• Very sensitive to syntactical ambiguities
• day/month/year/hour/minute separators

• DROP <object> <obj_name> <flags>
• DROP SCHEMA <schema_name> CASCADE
• drops all workspace tables, domains
• DROP TABLE <relation_name> RESTRICT
• only drops table if
• not referenced in any constraints/views
• Notion of cascading
• Table links

• Schema evolution
• Design side
• ALTER TABLE <schema_name>.<relation_name> ADD
  <var_name> <var_type>;
• Example
• ALTER TABLE uni.student ADD hall VARCHAR(32);
• Upper and lower case syntax
• Naming conventions

• Helper interfaces
• HeidiSQL/phpMyAdmin/Sword/SQLplus
• Design/perform a lot of routine queries for you
• Important to learn SQL, reinforcement
• Designing select queries is more difficult
• Visual interfaces still lacking in this area
• Select queries in SQL
• Basic singlets
• Renaming
• Queries with Joins
• Nested queries

• SELECT statement
• Similar to relational data model SELECT then PROJECT
• SELECT <attribute list>
• FROM <table list>
• WHERE <condition>;

• SELECT <attr_list>
• FROM R,S,T
• WHERE DNO = 10
• equivalent to
• p_{<attr_list>}(s_DNO=10 (R X S X T))
• True-false evaluation tuple by tuple
• WHERE clause as compound logical statement

• Produces a relation/set of tuples
• Can be used to extract a single tuple
• e.g. SELECT bday, age
• FROM student
• WHERE fname='Tim' AND lname='Smith'
• Result = (13-05-80, 20)
• Argument quoting (')
• SQL poisoning
• Not null
• Not numeric values
• MySQL Attribute quoting (`)
• Hypothetical attribute `all`, all, and ALL

SQL poisoning is a vulnerability exposed by inadequate escaping of arguments/variables used to compose SQL queries.

E.g. Tim in previous example, could be Tim'; DELETE FROM student;' SELECT * FROM student WHERE 1

• AS keyword
• (Partial) Attribute renaming in projection list
• SELECT fname AS firstName, minit, lname AS surname...
• Role names for relations
• SELECT S.FNAME, F.FNAME, S.LNAME
• FROM STUDENT AS S, STUDENT AS F
• WHERE S.LNAME=F.LNAME
• (Total) Attribute renaming in FROM
• SELECT s.firstName, s.surname
• FROM student AS s(firstName,surname,DOB,NINO,tutor)
• Wildcards (SELECT s.* FROM...)

• Relations are bags, not sets
• e.g. projection of non-key attributes
• Set cannot contain duplicate item/repetition
• Duplicates exist in bags and be:
• SELECT DISTINCT (eliminated)
• SELECT ALL (ignored/kept)

• Relational database allows inter-related data
• SQL select FROM gives Cartesian product
• WHERE clause defines join condition
• SELECT proj.pnum, mgr.ssn
• FROM project AS proj, employee AS mgr
• WHERE proj.mgrssn = mgr.ssn;
• Alternatively, explicitly define join (note type)
• SELECT project.pnum, employee.ssn
• FROM project INNER JOIN employee
• ON project.mgrssn = employee.ssn;

• Outer joins are crucial in the real-world
• Databases often contain NULLs (3VL)
• Analysis of where the crucial data is across a relationship
• Previous example, only get project data for managed projects
• SELECT project.*, employee.*
• FROM project INNER JOIN employee
• ON project.mgrssn = employee.ssn;

• SELECT project.*, employee.*
• FROM project LEFT OUTER JOIN employee
• ON project.mgrssn = employee.ssn;

• Queries can encapsulate any number of relations
• Even one relation many times (in different roles)
• Relationship chain
• Across many relations
• Tuples as Entities OR Relationships
• e.g. Employee -> Works_on -> Project -> Department ->
  Manager

• Can’t be done in SQL2
• Recursive relationships
• Unknown number of steps
• SQL2 can’t generalise in single query

• Essential one or more (inner) queries within an (outer) query
• Inner and outer query
• Not to be confused with inner and outer joins
• Inner query can go in three places
• SELECT clause (projection list)
• Must return a single value, then aliased as attribute in outer result
• FROM clause
• Inner query result used as standard table in FROM cross product
• WHERE clause

• Use of query result as comparator for other (outer) query
• SELECT DISTINCT course
• FROM dept WHERE course IN (
• SELECT d.course
• FROM dept AS d, faculty AS f, student AS s
• WHERE d.ownfac=f.id AND s.owndept=d.id
• AND f.name='Eng' AND s.year='3'
• ) OR course IN (
• SELECT course
• FROM dept
• WHERE code LIKE 'COMS3%');

• Three tier database design
• Changing role of DBMS
• Indices
• Aggregate functions (conceptual)
• Over bags and sub-bags
• Creating and updating views (ext)
• SQL embedding

In this subsection we look at the different roles SQL play across the three tiers of database design. We discuss the areas in which SQL is lacking and how those difficiencies can be complemented by embedding SQL in other languages.

• Low/Internal level
• Index by one attribute
• For queries selecting by that attribute:
• Faster tuple access (ordered tuples)
• Reduces database memory load
• Small cross product relation, only crosses requisites
• Accelerates query resolution time
• CREATE INDEX Index_Name ON RELATION(Attribute);

• Run over groups of tuples
• Takes a projected attribute list as an argument
• Produce relation with single tuple
• SUM, MAX, MIN, AVG, COUNT
• e.g. AggFunc over all tuples
• SELECT SUM(SALARY), MAX(SALARY), MIN(SALARY)
• FROM EMPLOYEE;
• Single attribute lists (distinct values)
• Multi-attribute lists (granularity of distinct values by pairing)

• Can run over subsets of tuples
• GROUP BY keyword
• Specifies the grouping attributes
• Need to also appear in projected attr_list
• Show result along side value for group attr
• e.g. AggFunc over subgroups
• SELECT dno, COUNT(*)
• FROM employee
• GROUP BY dno

Quick SQL check, do all attributes in the SELECT projection list appear in the GROUP BY projection list.

• Views are partial projections
• Virtual relations, or views of live relations
• Update synchronised
• CREATE VIEW <virtual_relname>
• AS <real_relation>
• Real relation could be a query result
• Clever bit is the change propagation
• UPDATEs made to the view dataset are flooded back to relations
• INSERT and DELETE behaviour needs to be defined
• Non-trivial as INSERT into view (virtual relation) may leave holes in real relation

• SQL (alone) can do lots of clever things in one expression
• But can only execute a single expression
• Can structure SQL commands into proper programming languages
• Java Database Connection (JDBC)
• javac, then java VM
• COBOL, C or PASCAL
• precompiled with PRO*COBOL or PRO*C
• Procedure Language (PL/SQL)
• Oracle/MySQL procedural language
• Stored procedures can take parameters

In this lecture we look at...
[Section notes PDF 180Kb]

• Database internals (base tier)
• RAID technology
• Reliability and performance improvement
• Record and field basics
• Headers to hashing
• Index structures

• Distance from chip determines minimum latency
• Speed of light is a constant
• Impact of bus frequencies
• IDE (66,100,133 Hz)
• PCI, PCI-X (66,100,133 Hz)
• PCI Express (1Ghz to 12Ghz)
• Impact of bus bandwidths
• PCI (32/64 bit/cycle, 133MB/s)
• PCI Express (x16 8.0GB/s)

Here's a link from Intel showing a machine architecture with signal bandwidths: Intel diagram

• Capacity increased with distance
• Staged architecture as compromise
• Speed, time/distance
• Also cost, heat, usage scale

• Stored as files of records (of data values)
• Auxiliary data structures/indices
• 1y and 2y storage
• memory hierarchy (pyramid diagram)
• volatility
• Online and offline devices
• Primary file organisation, records on disk
• Heap - unordered
• Sorted - ordered, sequential by sort key
• Hashed - ordered by hash key
• B-trees - more complex

• DBMS task
• linked to backup
• 1y, 2y and 3y
• e.g. DLT tape
• Changing face of current technology
• Impact of inexpensive harddisks
• Flash memory devices (CF, USB)
• Random versus sequential access
• Latency (rotational delay) and
• Bandwidth (data transfer rate)

• Redundant Array of Independent Disks
• Data striping
• Blocks (512 bytes), bits and transparency
• Reliability (1/n)
• Mirroring/shadowing
• Error correction codes/parity
• Performance (n)
• Mirroring (2x read access)
• Multiple parallel access

• 0 No redundant data
• 1 Disk mirrors (performance gain)
• 2 Hamming codes (also detect)
• 3 Single parity disk
• 4 Block level striping
• 5 and parity/data distribution
• 6 Reed-Soloman codes

• DBMS specific, generally
• Records (tuples) comprise fields (attributes)
• File is a sequence of records
• Variable length records
• Variable length fields
• Multi-valued attributes/repeating fields
• Optional fields
• Mixed file of different record types

• records -> files -> disks
• Fixed length for efficient access
• Networking issues
• Delimit variable length fields (max)
• Explicit record/field lengths
• Separators (,;,:,$,?,%)
• Record headers and footers
• Spanning
• block boundaries and redundancy

• Bias data manipulation to 1y memory
• Load record to 1y, write back
• Cache theorem
• Data storage investment, rapidity of access
• optimisations based on frequent algorithmic use
• Ordering, ordering field/key field
• Hashing

• Auxiliary structures/secondary access path
• Single level indexes (Key, Pointer)
• File of records
• Ordering key field
• Primary, Secondary and Clustering

• Primary index on simple table
• Ordering key field (primary key) is Integer
• Pointers as addresses
• Sparse, not dense

• Two fields <K(i),P(i)>
• Ordering key field and pointer to block
• Second example, indexing candidate key Surname
• K(1)="Barnes",P(1) -> block 1
• Barnes record is first/anchor entry in block 1
• K(2)="Smith",P(2) -> block 6
• K(3)="Zeta",P(3) -> block 8
• Dense (K(i) for every record), or Sparse
• Enforce key constraint

• Clustering index
• Ordering key field (OKF) is non-key
• Each entry points to multiple records

• Two fields <K(i),P(i)>
• Ordering non-key field and pointer to block
• Internal structure e.g. linked list of records
• Each block may contain multiple records
• K(1)="Barnes",P(1) -> block 1
• K(2)="Bates",P(2) -> block 2
• K(3)="Zeta",P(3) -> block 3
• K(i) not required to have
• a distinct value for each record
• non-dense, sparse

• Independent of primary ordering
• Can't use block anchors
• Needs to be dense

• Single level index
• ordered index file
• limited by binary search
• Multi level indices
• based on tree data structures (B+/B-trees)
• faster reduction of search space (log_fob_i)

• Database architecture
• Intension/extension
• Indexes separated from data file
• Created/disgraded dynamically
• Typically 2y to avoid reordering records on disk

• Faster query resolution
• improved performance
• lower load
• hardware cost:performance ratio
• Moore's law
• Query process chain
• Query optimisation

• Compile-track familiarity
• Scanner/tokeniser - break into tokens
• Parser - semantic understanding, grammar
• Validated - check attribute names
• Query tree
• Execution strategy, heuristic
• Query optimisation
• In (extended relational) canonical algebra form

• SQL query
• SELECT lname, fname
• FROM employee
• WHERE salary > (
• SELECT MAX(salary)
• FROM employee
• WHERE dno=5
• );
• Worst-case
• Process inner for each outer
• Best-base
• Canonical algrebraic form

• Indexing accelerates query resolution
• Closed comparison (intra-tuple)
• all variables/attributes within single tuple
• e.g. x < 100
• Open comparison (inter-tuple)
• variables span multiple tuples
• Essentially a sorting problem
• Internal sorting covered (pre-requisites)
• Need external sort for non-cached lists

• External sorting
• Stems from large disk (2y), small memory (1y)
• Sort-merge strategy
• Sort runs (small sets of total data file)
• Then merge runs back together
• Used in
• SELECT, to accelerate selection (by index)
• PROJECT, to eliminate duplicates
• JOIN, UNION and INTERSECTION

In this lecture we look at...
[Section notes PDF 159Kb]

• Used to implement Indicies
• O(n) access
• Ordering Key Field (K) as argument to Hash function H()
• Address H(K) maps to pointer

• Tree revision
• Node based
• Branching nodes/leaf nodes
• Parent/child nodes
• Root node
• Cardinality

• Multi-level indices
• One index indexes another
• Implemented by multiple hash-tables
• <H(k),P> pairs
• (data far right)

• Collapsing a single index
• Two columns become one
• <H(k),P> pairs sequentially stored
• Common in the Elmasri

• Paritioning structure
• Each node contains keys & pointers
• Pointers can be:
• Node pointers - to child nodes
• Data pointers - to records in heap
• Number of keys = Number of pointers - 1
• Every node in the tree is identical

• Similar to B-trees
• Different types of nodes
• Branching nodes
• Leaf nodes
• Each branching node has:
• At most U children (max U)
• At least L children (min L)
• U = 2L, or U = 2L-1

• Balanced
• All leaf nodes at same level
• Record search takes same time for every record
• Partitioning needs to be comprehensive
• B-tree: a₁ < x < a₂
• B+tree: a₁ <= x <= a₂
• Why?
• because all data for partition values must be in the lowest level of the tree

• Insert operation cascades from bottom
• Rules: node can contain U children (max)
• Node combine
• Legal if child nodes contain L children
• Parent loses one key/paritition value
• Node split
• Legal if node contains U children
• Parent node gains one key/partition value
• Can cause cascade up tree & rebalancing

This is the Database Design course theme.
[Complete set of notes PDF 300Kb].

In this lecture we look at...
[Section notes PDF 48Kb]

• What is relational design?
• Notion of attribute distribution
• Conceptual-level optimisation
• How do we asses the quality of a design?

• Allocated arbitrarily by DBD under ER/EER
• Goodness at
• Internal/storage level (base relations only)
• Reducing nulls - obvious storage benefits /frequent
• Reducing redundancy - for efficient storage/anomalies
• Conceptual level
• Semantics of the attributes /single entity:relation
• No spurious tuple generation /no match Attr,-PK/FK

• Database design
• Universal relation
• R = {A₁, A₂, …, A_n}
• Set of functional dependencies F
• Decompose R using F to
• D = {R₁, R₂, …, R_n}
• D is a decomposition of R under F

• Attribute preservation
• Union of all decomposed relations = original
• Lossless/non-additive join
• For every extension, total join of r(R_i) yeilds r(R)
• no spurious/erroneous tuples

• Dependency preservation
• Constraints on the database
• X -> Y in F of R, appears directly in R_i
• Attributes X and Y all contained in R_i
• Each relation R_i in 3NF
• But what's a dependency?

• Constraint between two sets of attributes
• Formal method for grouping attributes
• DB as one single universal relation/-literal
• R = {A₁,A₂,…,A_n}
• Two sets of attributes, X subset R,Y subset R
• Functional dependency (FD or f.d.) X -> Y
• If t₁[X] = t₂[X], then t₁[Y] = t₂[Y]
• Values of the Y attribute depend on value of X
• X functionally determines Y, not reverse necessarily

• Rules of inference
• reflexive: if X implies Y then X -> Y
• augment: {X -> Y} then XZ -> YZ
• transitive: {X -> Y,Y -> Z} then X -> Z
• Armstrong demonstrated complete for closures

• If X is a key (primary and/or candidate)
• All tuples t_i have a unique value for X
• No two tuples (t₁,t₂) share a value of X
• Therefore X -> Y
• For any subset of attributes Y
• Examples
• SSN -> {Fname, Minit, Lname}
• {Country of issue, Driving license no} -> SSN
• Mobile area code -> Mobile
  network (not anymore)

• Typically start with set of f.d., F
• determined from semantics of attributes
• Then use IR1,2,3 to infer additional f.d.s
• Determine left hand sides (Xs)
• Then determine all attributes dependent on X
• For each set of attributes X,
• determine X+ :the set of attributes f.d'ed by X on F

• Compute the closure of X under F: X+
• xplus = x;
• do
• oldxplus = xplus;
• for (each f.d. Y -> Z in F)
• if (xplus implies Y) then
• xplus = xplus union Z;
• while (xplus != oldxplus);

• Consider a relation schema R(A,B,C,D) and a set F of functional dependencies
• Aim to find all keys (minimal superkeys),
• by determining closures of all possible X subsets of R’s attributes, e.g.
• A+, B+, C+, D+,
• AB+, AC+, AD+, BC+, BD+, CD+
• ABC+, ABD+, BCD+
• ABCD+

• Let R be a relational schema R(A, B, C, D)
• Simple set of f.d.s
• AB -> C, C -> D, D -> A
• Calculate singletons
• A+, B+, C+, D+,
• Pairs
• AB+, AC+,…
• Triples
• and so on

• Compute sets of closures
• AB -> C, C -> D, D -> A
• 1.Singletons
• A+ -> A
• B+ -> B
• C+ -> CDA
• D+ -> AD
• Question: are any singletons superkeys?

• 2.Pairs (note commutative)
• AB+ -> ABCD
• AC+ -> ACD
• AD+ -> AD
• BC+ -> ABCD
• BD+ -> ABCD
• CD+ -> ACD
• Superkeys?

• 3.Triples
• ABC+ -> ABCD
• ABD+ -> ABCD
• BCD+ -> ABCD
• Superkeys? Minimal superkeys (keys)?
• 4.Quadruples
• ABCD+ -> ABCD

• Superkeys:
• AB, BC, BD, ABC, ABD, BCD, ABCD
• Minimal superkeys (keys)
• AB, BC, BD

In this lecture we look at...
[Section notes PDF 121Kb]

• Information Principle:
• The entire information content of the database is represented in one and only one way, namely as explicit values in column positions in tables
• Implies that two relations cannot have the same meaning
• unless they explicitly have the same design/attributes (including name)

• Reduced redundancy
• Organised data efficiently
• Improves data consistency
• Reduces chance of update anomalies
• Data duplicated, then updated in only one location
• Only duplicate primary key
• All non-key data stored only once
• Data spread across multiple tables, instead of one Universal relation R

• Depends on Application
• OLTP (Transaction processing)
• Lots of small transactions
• Need to execute updates quickly
• OLAP (Analytical processing/DSS)
• Largely Read-only
• Redundant data copies facilitate Business Intellegence applications, e.g. star schema (later)
• 3NF considered ‘normalised’
• save special cases

• First Normal form (1NF)
• Disallows multivalued attributes
• Part of the basic relational model
• Domain must include only atomic values
• simple, indivisible
• Value of attribute-tuple in extension of schema
• t[A_i] ∈ (A_i)

• Remove fields containing comma separated lists
• Multi-valued attribute (A_MV) of R_i
• Create new relation (R_NEW)
• with FK to R_i[PK]
• R_NEW(UID, A_MV, FK_I)

• A relation R_i is in 2NF if:
• Every nonprime attribute A in R_i is
• fully functionally dependent on 1y key of R
• If all keys are singletons, guaranteed
• If R_i has composite key are
• all non-key attributes fully functionally dependent
• on all attributes of composite key?

• Second normal form (2NF)
• Full functional dependency X → Y
• A ∈ X, (X - {A}) ¬→ Y
• If any attribute A is removed from X
• Then X → Y no longer holds
• Partial functional dependency
• A ∈ X, (X - {A}) → Y

• In context
• Not 2NF: AB → C, A → C
• AB → C is not in 2NF, because B can be removed
• Not 2NF: AB → CDE, B → DE
• because attributes D&E are dependent on part of the composite key (B of AB), not all of it

• Split attributes not depended on all of the primary key into separate relations

• Boyce-Codd Normal form (BCNF)
• Simpler, stricter 3NF
• BCNF → 3NF
• 3NF does not imply BCNF
• nontrivial functional dependency X → Y
• Then X must be a superkey

• Third Normal form (3NF)
• Derived/based on transitive dependency
• For all nontrivial functional dependencies
  X → A
• Either X must be a superkey
• Or A is a prime attribute
  (member of a key)

• AB → C, C → D, D → A
• In context
• 3NF? Yes
• Because AB is a superkey and
• D and A are prime attributes
• BCNF? No
• Because C and D are not superkeys
• (even though AB is)

• CarMakes not in 3NF because:
• singleton key A
• non-trivial fd B → C
• B not superkey, C not prime attribute

In this lecture we look at...
[Section notes PDF 34Kb]

• Database architectures, beyond
• Why OODBMS?
• ObjectStore
• CORBA object distribution standard

• Complex entity fragmentation
• across many relations
• Breaks the miniworld-realworld dichotomy
• Requires conceptual abstracting layer
• Difficult to retrieve all information for x
• Compounded by version control

• Object components (icv triples)
• Object Identity (OID), I
• replaces primary key
• Type constructor, c
• how the object state is constructed from sub-comp
• e.g. atom, tuple (struct), set, list, bag, array
• Object state, v
• Object behaviour/action

• Encapsulation
• Abstract data types
• Information hiding
• Object classes and behavior
• Defined by operations (methods)
• Inheritance and hierarchies
• Strong typing (no illegal casting)
• don’t think about inheritance just yet

• Persistence
• Objects exist after termination
• Naming and reachability mechanism
• Late binding in Java
• Performance
• user-def functions executed on server, not client
• Extension into relational model
• Domains of objects, not just values
• Domain hierarchies etc.

• Polymorphism
• aka. operator overloading
• same method name/symbol
• multiple implementations
• Easy link to Programming languages
• popular OO language like Java/C++
• Better than PL/SQL integration
• Much better than PL-JDBC integration!
• Highly suitable for multimedia data

• Object Ids
• Artificial Real-Mini, double edged sword
• Exposes inner workings (suspended abstraction)
• Lack of integrity constraints
• No concept of normalisation/forms
• Extreme encapsulation
• e.g. creation of many accessor/mutator methods
• Lack of (better) standardisation

• Originally no mechanism for specifying
• relationships between objects
• In RDBMS – relationships are tuples
• In OODBMS – relationships should be properties of objects

• Packages supporting Java or C++
• C++ package uses:
• C++ class definition for DDL
• insert(e), remove(e) and create collections, for DML
• Bidirectional relationship facility
• Persistency transparency
• Identical pointers to persistent and transient objects

• Common Object Request Broker Architecture
• Object communication (unifying paradigm)
• Distributed
• Heterogeneous
• Network, OS and language transparency
• Java implementation org.omg.CORBA
• Also C, C++, ADA, SMALLTALK

In this lecture we look at...
[Section notes PDF 117Kb]

• Design/schema side (Entity types)
• Object-orientated concepts
• Java, C++ or UML
• Sub/superclasses and inheritance
• EER diagrams
• EER to Relational mapping

• Inheritance concept
• Attributes (and methods)
• Subtypes and supertypes
• Specialisation and Generalisation
• ER diagrams
• show entities/entity sets
• EER diagrams
• show type inheritance
• additional 8^th step to ER→Relational mapping

• Basic guide to Java
• Object, classes as blueprints
• Object, collection of methods and attributes
• Miniworld model of real world things
• Object, entity in database terms

• Similar objects
• Car Park example
• Student example
• Shared properties/attributes
• Generalisation
• Reverse, specialisation

• Using English as model
• ‘Is a’ (inheritance)
• ‘Has a’ (containment)
• Nouns as objects
• Verbs as methods
• Adjectives as variables (sort of)

• Superclasses (Student)
• Subclasses (Engineer, Geographer, Medic)
• Inheritance
• Subclass inherits superclass attributes
• Union of specific/local and general attributes
• Inheritance chains
• Person → Student → Engineer → Computer Scientist

• Partial participation
• Disjoint subclasses
• A fruit may be either a pear or an apple or a banana, or none of them. A fruit may not be a pear and a banana, an apple and a banana, an apple and a pear …

• Total, disjoint
• Equivalent to Java Abstract classes
• A Wine has to be either Red, White or Rosé cannot be both more

• Specialisation lattices
• and Hierarchies
• Multiple inheritance
• Union of two superclasses (u in circle)
• In addition to basic ER notation

• Subset symbol to illustrate
• sub/superclass relationship
• direction of relationship
• Circle to link super to subclasses
• Disjoint
• Overlapping
• Union

• Disjointness (d in circle) – single honours
• Overlapping (o in circle) – joint honours/sports
• Membership condition on same attribute
• attribute-defined specialisation
• defining attribute
• implies disjointness
• versus user-defined
• each entity type specifically defined by user

• Total specialisation
• Every entity in the superclass must be a member of atleast 1 subclass
• Double line (as ER)
• Partial specialisation
• Some entites may belong to atleast 1 subclass, or none at all
• Single line
• Yields 4 possibilities
• (Total-Dis, Total-Over, Partial-Dis, Partial-Over)

• Total, overlapping
• A Chip may has to be at least one of FPA Unit, Reg Block, L1 Cache, and may be more than one type

• Type hierarchies
• Specialisation lattices
• Well, sir, the Supreme Court of the United States has determined that the tomato is for legal and commercial purposes both a fruit and a vegetable. So we can legally refer to tomato juice as 'vegetable' juice.
• Candice, General Foods

• Initially following 7 ER stages
• Stage 8
• 4 different options
• Optimal solution based on problem
• Let C be superclass, S_1..m subclasses

• Create relation for C, and relations for S_1..m each with a foreign key to C (primary key)
• Create relations for S_1..m each including all attributes of C and its primary key

• Create a single relation including all attributes of C ∪ S_1..m and a type/discriminating attribute
• only for disjoint subclasses
• Create a single relation as above, but include a boolean type flag for each subclass
• works for overlapping, and also disjoint

In this lecture we look at...
[Section notes PDF 64Kb]

• Where’s the data?
• Programmer driven future
• OODBMS limitations
• RDBMS longevity
• System design by
• Data store, delivery, interface
• Case study

• Previously covered distance from User to Data (and reason for it)
• Client-Server data model creates DBMS
• P2P alternative
• Accountability
• Distribution (BitTorrent, eDonkey)
• Caching

• Answer: everywhere
• But where is it meaningful?
• Answer: for whom?

• Large projects require large teams
• Team overhead (ref 2nd year)
• Code responsibilities
• Data/data model resp.
• Object responsibilities

• Web application programming
• Goal, dynamically produced XHTML
• Client side designer-programmer split
• CSS, XHTML
• Server side programmer-programmer split
• Old school: query design, integrator
• New school: MVC (Model-View-Controller)
• Controller – user input
• Model – modelling of external world
• View – visual feedback

• Content Management System
• part of other courses
• CMS is a DBMS
• Zope/Plone and ZODB
• e107, Drupal and Seagull
• Zend MVC Framework (pre-beta)

• Future unknown
• RDBMS supports
• Application data sharing
• Physical/logical data independence/views
• Concurrency control
• Constraints
• at inception these requirements not known
• RDBMS mathematical basis → extensible
• Crude Type Inheritance (see EER mapping)
• OODBMS as construction kit

• Data type support
• Unwieldy, created 3VL (nulls)
• Type Inheritance and Relationships
• Tuple:Entity fragmentation
• not to be confused with ‘fragmentation’
• Entity approximation requires joins

• Client specifications
• Variance amongst Mobile devices
• Rich-media Content delivery
• Where’s the data? (M – media database)
• Where’s it going? (C – mobile browser)
• How’s it going to get there? (query design)
• What’s it going to look like? (V – XHTML)

• The real world of databases
• Massive Excel spreadsheets
• Access Migration
• Normalisation
• Update implications
• Visual language of the Internet limitations
• Future of browser components

• Skillswap talk
• 28th May 2008

• Pace of talk
• Principals not query syntax
• Online notes
• Questions welcome anytime
• Prompt thought about the issues

• Tables/relations
• Rows/tuples
• Columns/attributes
• Joins
• Inner joins
• Outer joins
• Indexes
• B+ trees
• Multi-level implementation

• Domains
• Set of possible data
• 8-bit unsigned integer example
• Powersets
• Set
• Odd numbers less than 10
• (1,3,5,7,9)
• Powerset
• Set of sets
• 5 digit collection of non-repeating integers less than 10
• ((1,3,5,7,9),(2,3,5,7,9),(1,4,5,7,9),(1,3,6,7,9)...)

• Query + database snapshot returns one set of actual data
• but a query alone defines a powerset of possible data
• Load
• Metrics for query performance
• Time is easy to measure
• Load is better in the real world
• Query might be fast to execute, but require a lot of memory

• Query design needs context
• Hardware information
• L2, RAM, Disk : O(1), O(10), O(1000)
• Competition information (other Application Servers)
• MySQL, Apache, Tomcat, SVN
• Data information
• Likely number of rows, lifetime of information, interval distribution within domains
• Database design information
• Normalisation
• Database implementation information
• Transaction granularity
• Use information
• Balance between read (SELECT) and write (INSERT, UPDATE, DELETE) ops

• Ask MySQL what it's doing
• Query analysis with EXPLAIN
• Cache the query
• no free lunch, there's almost always a cost
• Simple
• Repetitive queries
• Rare since requires constant snapshot
• What's the point of the query

• Complex - Summary table
• Multiple queries drawing data from subset of DB data
• Cache subset
• Query subset rather than whole database
• Complex - Age analyses
• Webstats, meaningful even if not last 24 hours
• Run the heavyweight analysis queries during downtime
• Cache results

• Cache the object
• Higher level primitives
• Object persistence
• Get only the critical data
• What's critical now
• What's required in 10s, 1m, 5m

• Route/path to information
• Introduction
• Join is an arc, join time is arc length
• Table is a node
• Graph traversal problem
• Dijkstra's shortest path
• Heuristic
• Search for optimal
• General, each node defines a population of tuples

• Traversal of graph
• (aka. positive closure)
• gives intermediate relation
• Goal
• Intermediate relation minimisation
• Space (memory, disk triangle)
• Time (fast joins versus slow joins)
• Fewer relations
• Fewer active attributes (horizontal cropping)
• Fewer rows (vertical cropping)
• Role of single-relation WHERE statements

• Giving the Optimiser hints
• Indexing
• Simple - single attribute
• Index(A)
• Reduce sparse domains (e.g. text)
• Composite - multiple attributes (typically pairs)
• Index (A,B)
• Some subtleties in here

• Limit
• Valueable on sorts (0,10 faster than 0,1000!)
• Beware limit referencing
• Limit 1000,10 will fetch the first 1000, then give you the 10 you want
• Search engines
• Better to use WHERE restriction if possible

• SELECT FROM (SELECT id FROM ... LIMIT 0,10)
• Subqueries not the silver bullet
• Often not cached or indexed
• Views help manage complex relationships but not performance
• Changing picture
• Even between MySQL 5.0 and 5.1
• MySQL 6.0
• Falcon (transactional) Storage
• Better subquery optimisation

• External References for Section 3.6 only
• Shortest path
• http://en.wikipedia.org/wiki/Dijkstra's_algorithm
• CASO
• http://www.mysqlperformanceblog.com/
• MySQL 6
• http://dev.mysql.com/doc/refman/6.0/en/index.html

This is the Distributed systems course theme.

[Complete set of notes PDF 109Kb]

In this lecture we look at...
[Section notes PDF 86Kb]

• Transactions
• Unpredictable failure
• Commit and rollback
• Stored procedures
• Brief PL overview
• Cursors

• Real world database actions
• Rarely single step
• Flight reservation example
• Add passenger details to roster
• Charge passenger credit card
• Update seats available
• Order extra vegetarian meal

ACID test

• Atomicity
• transaction as smallest unit of processing
• transactions complete entirely or not at all
• consequences of partial completion in flight example
• Consistency
• complete execution preserves database constrained state/integrity
• e.g. Should a transaction create an entity with a foreign key then the reference entity must exist (see 4 constraints)

• Isolation
• not interfered with by any other concurrent transactions
• Durable (permanency)
• commited changes persist in the database, not vulernable to failure

• Notion of Commit (durability)
• Transaction failures
• From flight reservation example
• Add passenger details to roster
• Charge passenger credit card
• Update seats available: No seats remaining
• Order extra vegetarian meal
• Rollback

• Language format
• Declarations
• Execution
• Exceptions
• Handling I/O
• Functions
• Cursors

• Blocks broken into three parts
• Declaration
• Variables declared and initialised
• Execution
• Variables manipulated/actioned
• Exception
• Error raised and handled during exec
• 
  DECLARE
      ---declarations
  BEGIN
      ---statements
  EXCEPTION
      ---handlers
  END ;

• DECLARE
• age NUMBER;
• name VARCHAR(20);
• surname employee.fname%TYPE;
• addr student.termAddress%TYPE;

• BEGIN (not in order)
• /* sql_statements */
• UPDATE employee SET salary = salary+1;
• /* conditionals */
• IF (age < 0) THEN
• age: = 0;
• ELSE
• age: = age + 1;
• END IF;
• /* transaction processing */
• COMMIT; ROLLBACK;
• /* loops */ /* cursors */
• [END;] (if no exception handling)

• Beginnings of PL I/O
• CREATE TABLE temp (logmessage varchar(80));
• Can create transfer/bridge relation outside




• Within block (e.g. within exception handler)
• WHEN invalid_age THEN
• INSERT INTO temp VALUES( ‘Cannot have negative ages’);
• END;




• SELECT * FROM temp;
• To review error messages

• DECLARE
• invalid_age exception;
• BEGIN
• IF (age < 0) THEN
• RAISE invalid_age
• END IF;
• EXCEPTION
• WHEN invalid_age THEN
• INSERT INTO temp VALUES( ‘Cannot have negative ages’);
• END;

• Cursors
• Tuple by tuple processing of relations
• Three phases (two)
• Declare
• Use
• Exception (as per normal raise)

• PL blocks coherently change database state
• No runtime I/O
• Difficult to debug
• SQL tested independently

• DECLARE
• name_attr EMPLOYEE.NAME%TYPE;
• ssn_attr EMPLOYEE.SSN%TYPE;
• /* cursor declaration */
• CURSOR myEmployeeCursor IS
• SELECT NAME,SSN FROM EMPLOYEE
• WHERE DNO=1
• FOR UPDATE;
• emp_tuple myEmployeeCursor%ROWTYPE;

• BEGIN
• /* open cursor */
• OPEN myEmployeeCursor;
• /* can pull a tuple attributes into variables */
• FETCH myEmployeeCursor INTO name_attr,ssn_attr;
• /* or pull tuple into tuple variable */
• FETCH myEmployeeCursor INTO emp_tuple;
• CLOSE myEmployeeCursor;






• [LOOP…END LOOP example on handout]

• Concurrent transactions
• Distributed databases (DDB)
• Fragmentation
• Desirable transaction properties
• Concurrency control techniques
• Locking
• Timestamps

• Language
• PL too complex/long-winded
• Simplified database model
• Database as collection of named items
• Granularity, or size of data item
• Disk block based, each block X
• Basic transaction language (BTL)
• read_item(X);
• write_item(X);
• Basic algebra, X=X+N;

• DBMS Multiuser system
• Multiple terminals/clients
• Single processor, client side execution
• Single centralised database
• Multiprocessor, server
• Resolving many transactions simultaneously
• Concurrency issue
• Coverage by previous courses (e.g. COMS12100)
• PL/SQL scripts (Transactions) as processes
• Interleaved execution

• Two transactions, T₁ and T₂
• Overlapping read-sets and write-sets
• Interleaved execution
• Concurrency control required
• PL/SQL example
• Commit; and rollback;

• Three potential problems
• Lost update
• Dirty read
• Incorrect summary
• All exemplified using BTL
• Transaction diagrams to make clearer
• C-like syntax for familiarity
• Many possible examples of each problem

• T₁
• read_item(X);
• X=X-N;




• write_item(X);
• read_item(Y);




• Y=Y+N;
• write_item(Y);

• T₂




• read_item(X);
• X=X+M;




• write_item(X);

• T₁ X update overwritten

• T₁
• read_item(X);
• X=X-N;
• write_item(X);




• <T₁ fails>
• <T₁ rollback>




• read_item(X);
• X=X+N;
• write_item(X);

• T₂




• read_item(X);
• X=X+M;
• write_item(X);

• T₂ reads temporary incorrect value of X

• T₁




• read_item(X);
• X=X-N;
• write_item(X);




• read_item(Y);
• Y=Y-N;
• write_item(Y);

• T₂
• sum=0;
• read_item(A)
• sum=sum+A;




• read_item(X);
• sum=sum+X;
• read_item(Y);
• sum=sum+Y;

• T₂ sums after X-N and before Y-N

• Schedule S is a collection of transactions (T_i)
• Serial schedule S₁
• Transactions executed one after the other
• Performed in a serial order
• No interleaving
• Commit or abort of active transaction (T_i) triggers
  execution of the next (T_i+1)
• If transactions are independent
• all serial schedules are correct

• Serial schedules/histories
• No concurrency
• Unfair timeslicing
• Non-serial schedule S₂ of n transactions
• Serializable if
• equivalent to some serial schedule of the same n transactions
• correct
• n! serial schedules, more non-serial

• DDB, collection of
• multiple logically interrelated databases
• distributed over a computer network
• DDBMS
• Multiprocessor environments
• Shared memory
• Shared disk
• Shared nothing

• Distribution transparency
• Multiple transparency levels
• Network
• Location/dept autonomy
• Naming
• Replication
• Fragmentation
• Reliability and availability
• Performance, data localisation
• Expansion

• Breaking the database into
• logical units
• for distribution (DDB design)
• Global directory to keep track/abstract
• Fragmentation schema/allocation schema
• Relational
• Horizontal
• Derived (referential), complete (by union)
• Vertical
• Hybrid

• Multiple copies
• Failure of individual sites (hosts/servers)
• Failure of network/links
• Transaction processing
• Distributed commit
• Deadlock
• Primary/coordinator site - voting

• Coordinator elected
• Coordinator prepares
• writes log to disk, open sockets, sends out queries
• Process
• Coordinator sends ‘Ready-commit’ message
• Peers send back ‘Ready-OK’
• Coordinator sends ‘Commit’ message
• Peers send back ‘Commit-OK’ message

• Data transfer costs of query processing
• Local bias
• High remote access cost
• Vast data quantities to build intermediate relations
• Decomposition
• Subqueries resolved locally

• Must avoid 3+ problems
• Lost update, dirty read, incorrect summary
• Deadlock/livelock - dining example
• Data item granularity
• Solutions
• Protocols, validation
• Locking
• Timestamps

• Binary (two-state) locks
• locked, unlocked associated with item X
• Mutual exclusion
• Four requirements
• Must lock before access
• Must unlock after all access
• No relocking of already locked
• No unlocking of already unlocked

• Multiple mode locking
• Read/write locks
• aka. shared/exclusive locks
• Less restrictive (CREW)
• read_lock(X), write_lock(X), unlock(X)
• e.g. acquire read/write_lock
• not reading or writing the lock state

• Must hold read/write_lock to read
• Must hold write_lock to write
• Must unlock after all access
• Cannot upgrade/downgrade locks
• Cannot request new lock while holding one
• Upgrading permissable (read lock to write)
• if currently holding sole read access
• Downgrading permissable (write lock to read)
• if currently holding write lock

In this lecture we look at...
[Section notes PDF 37Kb]

• Concurrency control protocols
• Concurrency techniques
• Locks, Protocols, Timestamps
• Multimode locking with conversion
• Guarenteeing serializability
• Associated cost
• Timestamps and ordering

• Two phase locking protocol (2PL)
• Growing/expanding
• Acquisition of all locks
• Or upgrading of existing locks
• Shrinking
• Release of locks
• Or downgrading
• Guarentees serializability
• equivalency without checking schedules

• T₁




• read_lock(Y);
• read_item(Y);
• unlock(Y);




• write_lock(X);
• read_item(X);
• X=X+Y;
• write_item(X);
• unlock(X);

• T₂




• read_lock(X);
• read_item(X);
• unlock(X);




• write_lock(Y);
• read_item(Y);
• Y=X+Y;
• write_item(Y);
• unlock(Y);

• Violates rules of two phase locking
• unlock occurs during locking/expanding phase

• T₁




• read_lock(Y);
• read_item(Y);
• write_lock(X);
• unlock(Y);
• read_item(X);
• X=X+Y;
• write_item(X);
• unlock(X);

• T₂




• read_lock(X);
• read_item(X);
• write_lock(Y);
• unlock(X);
• read_item(Y);
• Y=X+Y;
• write_item(Y);
• unlock(Y);

• Less efficient (cost), but serializable

• T₂ ends up waiting for read access to X
• Either after T₁ finished
• T₁ cannot release X even though it has finished using it
• Incorrect phase (still expanding)
• Or before T₁ has used it
• T₁ has to claim X during expansion, even if it doesn’t use
  it until later
• Cost: limits the amount of concurrency

• Concurrency control
• Locks limit concurrency
• Busy waiting
• Timestamp ordering (TO)
• Order transaction execution
• for a particular equivalent serial schedule
• of transactions ordered by timestamp value
• Note: difference to lock serial equivalent
• No locks, no deadlock

• Unique identifier for transaction (T)
• Assigned in order of submission
• Time
• linear time, current date/sys clock - one per cycle
• Counter
• counter, finite bitspace, wrap-around issues
• Timestamp aka. Transaction start time
• TS(T)

• DBMS associates two TS with each item




• Read_TS(X): gets read timestamp of item X
• timestamp of most recent successful read on X
• = TS(T) where T is youngest read transaction






• Write_TS(X): gets write timestamp of item X
• as for read timestamp

• Transaction T issues read_item(X)
• TO algorithm compares TS(T) with Write_TS(X)
• Ensures transaction order execution not violated
• If successful,Write_TS(X) <= TS(T)
• Read_TS(X) = MAX_{TS(T), current Read_TS(X)}
• If fail,Write_TS(X) > TS(T)
• T aborted, rolled-back and resubmitted with new TS
• Cascading rollback

• Transaction T issues write_item(X)
• TO algorithm compares TS(T) with Read_TS(X) and compares TS(T) with Write_TS(X)
• If successful, op_TS(X) <= TS(T)
• Write_TS(X) = TS(T)
• If fail, op_TS(X) > TS(T)
• T aborted, cascade etc.
• All operations focus on not violating the execution order defined by the timestamp ordering

• Insertion
• 2PL: DBMS secures exclusive write-lock
• TOA: op_TS(X) set to TS(creating transaction)
• Deletion
• 2PL: as insert
• TOA: waits to ensure later transactions don’t access
• Phantom problem
• Record being inserted matches inclusion conditions
• of another transaction
  (e.g. selection by dno=5)
• Locking doesn’t guarantee inclusion
  
  (need index locking)

This is the Real world course theme.

[Complete set of notes PDF 206Kb]

In this lecture we look at...
[Section notes PDF 133Kb]

• Path from DB to User
• Information flow
• Data formats (OO)
• Format transitions
• Limitations/channel
  
• The Future

• Object orientated approach
• Consistent/optimised development model
• Good approximation of real world
• Closer link to mini-world
• Java and PHP
• DB persistence
• UML

• Java
• JSP (server-side)
• Javascript (client-side)
• PHP
• Server side only
• JSON or XML
• Object communication
• Ideal scenario
• Java – load times

• Homogenous data format/data model
• DB stores objects instead
• Objects transferred
• Robust
• Lightweight
• Fast
• Consistent (more later in Transactions)
• Caching

• Heterogenous data model
• Object translation/wrappers
• Different languages features at different layers
• Minimal subset of OO functionality available end-to-end
• Going to look at information flow/functionality provided

• Limitations of being human
• short term memory
• long term familiarity
• language of the Internet
• hypertext linking
• form filling
• Advantages of being human
• impatience, no waiting
• wants instant response

• Http requests
• Forms
• Post
• Get
• Form fields
• By name, by ID
• Hidden
• Javascript/DOM tree

• Communication medium
• Good for transferring data
• Not good for transforming data
• e.g. Light in air
• e.g. Signal over CAT5e/UTP cable

• Straight HTML pages
• Dynamic HTML pages
• PHP example
• JSP example
• As above with RDBMS integration
• PHP PDO example
• As above with Objects
• PHP DBDO example

• Protocol stack
• Basic up-down
• Shortcuts
• Browser cache
• Web server
• assembled page cache
• php object cache
• DB optimised queries

• Google Maps
• Car selector and Dealer locator

In this lecture we look at...
[Section notes PDF 85Kb]

• Decision support systems (DSS)
• Duplicates of live systems, historical archiving
• Primarily read-only
• Load and refresh operations
• Integrity
• Assumptions about initial data
• Large, indexed, redundancy

• Design
• Logical
• Temporal keys, required to distinquish historical data (since:to
  current & during:within interval)
• Physical (Hash indexes, Bitmap indexes)
• Controlled Redundancy
• Synchronisation/update propogation
• Synchronous (update driven)
• Asynchronous (query driven)

• Extract
• pulling from live database system(s)
• Cleansing
• Transformation and Consolidation
• migrating from live or legacy system design
  
  to DSS design
• Load (DSS live/query-able)
• Refresh (latest update)

• Boolean expression complexity
• heavy WHERE clauses
• Join complexity
• Normalised databases, many tables
• Facts distributed across tables
• Joins required to answer complex questions
• Function and Analytic complexity
• Often require non-DBMS functions
• Smaller queries with interleaved code

• Specific example of DSS
• Subject-orientated
• e.g. customers/products
• Non-volatile
• once inserted, items cannot be updated
• Time variant
• Temporal keys
• Accuracy and granularity issues

• By example

• Consider product, customer, sales data
• Each sale represents a specific event
• when a product was purchased
• when a customer bought something
• when a sale was recorded
• Each can be thought of as an axis
  
  or dimension (3D)
• Each occurred at a moment in time (4D)

• Data centralised in ‘fact’ table
• Referencing creates star pattern
• Dimensions as satellite tables
• Normalising creates snowflake schema

• Hypercube is also a multi-processor topology inspired by a 4D shape
• Used by Intel’s iPSC/2
• Good at certain database operations
• e.g. Duplicate removal
• MIMD