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