INFS 766

Object-Oriented Databases

Traditional database models:

  1. hierarchical
  2. network
  3. relational (since 1970, commercially since 1982, works!)

Object-Oriented data models started mid-1990s

  1. we wanted more complex apps (storing more than numbers and text)
  2. we wanted more data modeling features
  3. increased OOPL use sparked OO database desire

Commercial OODb products came up in 1990s, didn’t really hit mainstream: relational model works well enough, very entrenched

OOPLs: Simula, Smalltalk, C++, Java

Experimental OODb systems: Postgres, IRIS Orion, OPen-OODB

Commercial OODB products: Onotos, Gemstone,…

OODB about maintaining direct correspondence between real-world objects and database objects so objects do not lose their integrity and identity and can easily be identified and operated upon.

Object has state (value: what the object knows) and behavior (operations: what the object knows how to do)

OO captures complex structures in simpler abstract containers or names or nouns.

OODB has objects of arbitrary complexity; traditional database can scatter data about a gievn object across numerous records/tables or records.

OOPL defines instance variables (data members in C++) which hold the values that define the object in a given state.

Two parts of operation:

  1. Signature/Interface of operation specifies operation name and arguments (or parameters)
  2. Method/Body specifies implementation of operation — that’s the instructions.

Polymorphism here refers to the ability of an operation to be applied to different types of objects; a.k.a. operator overloading

Every object has a unique object identifier, the OID. This is tricky if you have a big system with multiple machines/users creating multiple objects simultaneously. However you do it, OID should not change (like in real world: individuals don’t change identity! You are always Bob!).

Every object is a triple: (OID, type, value)

Object types:

  1. atom: single value
  2. set: several values
  3. tuple: like line in database
  4. list: ordered set
  5. bag: collection of objects
  6. set: bag with no duplicates

OODB market growing very slowly; OO ideas being used in many apps but not going to full-tilt OODB.

Ultimately, making the computer’s representation of reality match ours does not matter: databases are a matter of efficient and effective storage. If the computer thinks in terms of relational tables and I think in terms of objects, it doesn’t matter, as long as I get the data I want.

Chapter 22: Object-Relational and Extended Relational DBS

SQL3 added object-relational capacity

We usually don’t see the O in the object-relational database systems; vendors just slap on some object capabilities and don’t sweat calling it a whole different system.

The big push for object capabilities is new media, using audio, video, images, BLOBs. But these big files didn’t really drive the development/adoption effort. RDB folks were already finding ways to deal with those big chunks of data. ODB thinking came about because folks were using OO thinking for other problems (programming, which itself went OO because developers were using OO thinking in planning/design!).


Last word: Database administration is a service industry! We and the stuff we are in charge of have no intrinsic value! We are valuable only to the extent we help out clients figure out what they need and optimize what they do. We serve our clients.

Disk Storage

Primary file organization: how files are physically stored on disk; where the read/write head has to go to read the file. You want to mess with this as little as possible! Find your data a good home and leave it there. There’s only one way to do this per file: you will store/arrange your records by one particular field (ID, SSN, LName, etc.)

Secondary file organization: auxiliary means of accessing data; indices! You can do all of these you want! Index by City, index by SSN… you basically list the records and their physical locations in order of whatever field suits your needs.

Primary file organization (Chapter 13!)

Things to remember when working with disks :

  1. Disks offer random access, read by block (LBA: Logical Block Address — usu. starts at 0, goes to n-1, where n = # blocks on disk)
  2. We still use tape backup because tape is the cheapest storage per bit!
  3. reading by bits or records is inefficient! We read by blocks!
  4. seek time: time to move head to block
  5. latency (a.k.a. rotation delay): time to spin disk to right positiontion under head
  6. block transfer time: time to move block from disk to head to memory (or back, for write) — usually takes the most time
  7. placing blocks contiguously reduces seek time and latency, but that’s beyond scope of this course, so we will concentrate on reducing the number of block reads and writes
  8. Double buffering allows us to read Block 1, let CPU start beating on it while we load Block 2 into the other buffer. Then the moment CPU gets done beating on #1, it turns to the other buffer and beats on #2, no waiting! This speeds up the total process by allowing processing to happen simultaneously with some data transfer
  9. Non-spanning: records can’t be broken up across blocks. This wastes some block space
  10. Blocking factor: how many records we can fit per block
  11. Fixed-length records waste space, but they are much more efficient to process and are what we will usually use.
  12. Read takes one block transfer; write usually requires two transfers, unless we luck out and the block we want is sitting in memory. Systems may allow pegging: we designate certain blocks as worth keeping around in the buffer.
  13. Choose your primary file organization to make most efficient the operations most important to you (search, insert, update, delete)
    1. Heap: unordered! INSERT by APPEND, records ordered by time created.
      1. Inserting takes 1-2 block reads (find last block, see if there’s room, write here or create new block to write).
      2. Searching is a pain, requires b/2 block reads on average; requires reading all b blocks on search of non-existent file.
      3. DELETE: must first search (avg. b/2). Then must decide what to do with the empty space! Instead of physically deleting the record and either Swiss-cheesing the disk or having to haul records in to backfill, you can just flag the record with a deletion bit. Odds are we’ll use downtime to compress the disk to fill the holes (garbage collection).
    2. Physical sort: ordered on some oft-used field (like EmpID, SSN, ZIP…)
      1. INSERT: pain! You’ve got to move everyone over to make room for new records… or you create overflow file in heap, deal with searching the whole overflow until we have time to do garbage collection during downtime.
      2. search: easier on the sort field (so you use this method when you do a lot of searches on that particular field)
      3. DELETE: again, sped up. Leave flag on DELETEd record. Note that DELETE could allow us to stick in INSERTs if there’s room… but making the computer consider that possibility usually eats more time than just sending every INSERT to the overflow.
      4. Note that physical sort allows binary search! Go to the middle, check whether we need to go below or above, keep halving until we hit target! Binary search will take average log2(b) block reads.
  14. Hashing: way of mapping things on disk, reducing the range of numbers; mod of primary key often used;  good academic topic that we’re not spending a lot of time on!

Secondary File Structures (Indexing! Chapter 14!)

  1. Making index will save time in most cases
  2. Primary Index: built on primary (unique) key
  3. Clustering index: orders in chunks (all the Bobs, all the Marys, etc.)
  4. Primary Index is another table, a separate file, with two fields: the primary (candidate) key and the block number in which the record with that primary key value is stored. Primary key may be the ordering key for the primary storage; doing a binary search on this index is still shorter than doing a binary search on the disk itself (fewer blocks to church through).
  5. Primary index allows binary search! Zoom! Searches now take log2(#blocks in Primary Index) + one more block read from disk.
  6. Remember, the primary index may still be huge (imagine Blogger’s primary index on usernames), but it won’t be as huge (use as many blocks) as the actual database
  7. Dense index: every record in database gets entry in index.
  8. Sparse index: not dense!
  9. A primary index can be sparse: since it uses the primary key, it can simply list the first or last key value (the anchor value) of each block on disk. This is good!
  10. Secondary index uses some key other than the ordering field of the primary file organization. Since the value of the key in this index has nothing to do with the block number, we need to have an index entry for every record.
  11. If search matters, create an index!
  12. You probably still have to read the index from disk. If you can keep the index in memory for lots of opeations, you really speed things up.
  13. Binary search tree: every child to left smaller, every child to right larger; efficiency comes from minimizing the depth of the roots (number of levels necessary = ROUNDUP((log2(n)+1)) where n = # records)
  14. B-tree: index scheme based on binary search tree: idea is that since we live in the world of disks and have to read entire blocks, we might as well pack as much into the block as we can
  15. B+-tree: internal nodes do not store pointer to the data block, which means there’s room for more index values and thus larger fan-out; only the leaf nodes have records paired with block pointers, so every search must go to the bottom of the tree. But the B+-tree’s bigger fan-out gives an advantage!
  16. So, B-tree, you probably need to go to the bottom leaf, but you might get lucky. B+-tree always goes to the bottom leaf. (Somewhere there’s a forumla for this!)
  17. B+-tree also has the advantage that you can sequentially read the bottom row and get every record! B-tree, you’ve got to jump all over to get that complete list.

Next Time: Optimization!

Chapter 6: Relational Algebra (yum!)

plan: expect midterm posted Monday or Tuesday; due Monday following spring break. Open note, open Net….

SQL is based on relational calculus, which asks for results but doesn’t specify an order of operations. Relational algebra is the basic set of operations for the relational model, more prescriptive, spelling out the steps. We’re looking at RA here because that’s what query optimizers (Chapter 15) use to perform the transformations necessary.

All objects in RA are relations: no duplicate tuples (records)! SQL doesn’t mind duplicates, eliminates them with UNIQUE or DISTINCT. Sorting to removing duplicates is expensive! In the old days, we didn’t want to incur that expense, so the guys who came up with SQL let duplicates slide.

sigma σ = SELECT

  • subscript like WHERE clause
  • horizontal partition: selects rows
  • results always have fewer or same number of tuples as original R
  • commutative

PROJECT = pi π

  • vertical partition: selects columns
  • note! this is like a straight SQL SELECT, without WHERE
  • results must be set of tuples, no duplicates
  • results always have fewer or same number of tuples as original R
  • not commutative

You can write RA ops in a big nested expression, or you can step it and name the intermediate results

RENAME = rho ρ

  • renames table and/or columns

UNION ( ∪ )

  • the two relations we unite must be “type compatible”: same number of attributes, and each pair of corresponding attributes must be type compatible (have same or compatible domains: strings, CHARS, integers, etc…. it’s the datatype that matters, not the field name: default is to take on the field name of the first table)
  • Note that usually what you’ll do is PROJECT two disparate tables, then UNION the results, since we don’t leave a bunch of type-compatible tables sitting around in the database

Type compatibility is a requirement for all three set operations, UNION, INTERSECTION ( ∩ ), and DIFFERENCE ( – )

UNION and INTERSECTION are commutative


  • has lots of tuples: multiply tuple count from each relation
  • add attribute count from each relation
  • usually not a meaningful relation in itself!

THETA JOIN, EQUIJOIN, NATURAL JOIN (NJ removes duplicate attributes)


We used to use rule-based query optimization, rules of thumb; now we use statistics-based query optimization: we have stats on the tables that inform our choices (see Chaper 15).

Relational databases took off because we can mathematically prove that stuff will work, using relational algebra! It is not the most efficient model (JOINs take time!), but that’s outweighed by the formal definitions that make stuff work.

Chapter 17 (Elmasri & Navathe): Transaction Processing

Assume transactions are correct: we aren’t worrying in this class about bad programming.

Remember that CPUs sit idle during I/O (secondary process, not central process). We are greedy: we want to use those extra CPU cycles. We thus interleave transactions, letting T2 get some CPU time while T1 dinks around elsewhere. So remember: we caused the problems we are trying to solve. :-)

Classic transaction concurrency problems:

  1. Lost Update: T2 writes over results of T1
  2. Temporary Update (a.k.a. Dirty Read): T1 reads X, modifies i; T2 reads X; T1 has error and aborts. T2 operates on dirty data, a value that shouldn’t have existed and got undone by T1’s abort
  3. Incorrect Summary (accountants hate this): I seek aggregate data, down a column/field, for each record. I count 100,000 records. I get to record 50,000, but while I’m still counting, someone updates record #1-100. Or while I’m counting #1-100, someone changes #50,000-51,000. My data is meaningless, unpinnable in time (well, no moer problematic than the U.S. Census
  4. Unrepeatable Read: T1 reads X, gets value, continues, then reads X again, gets different value due to operation of T2. Note that having to read X again probably happens because of memory constraints: you read it, then had to dump buffer, have to go back and get data.

Remember, you don’t get to control interleaving order. The system fits concurrent transactions wherever it can.

Corruption of data due to concurrency is huge problem. When your business relies on data (everybody’s business relies on data), you can’t let this corruption happen! If your database has bad data, it will cause mistakes. And if your users see they’re getting bad data, they will stop using the database. Then you have two problems! If you give your people a data tool that they have to double-check, you’ve given them crap. You and your database are the double-check!

Transaction states:

  1. begin
  2. active
  3. partially committed
  4. committed
  5. terminate

Note that a transaction can abort to the fail state at the active and partially committed state. We create a system log on non-volatile memory (i.e., pull the plug, that info persists) to recover database after transactions fail. System log records transaction starts, reads, writes, commits, and aborts.

Commit point: all operations executed successfully and effect of all operations recorded in system log.

Remember: transactions usually write to buffer, rarely to disk. When transaction commits, its effects may still be only in buffer, not on disk! System may crash before we write the buffer to disk. That’s why the log matters! The log records that info so we can REDO after a crash and fix things with the least possible re-input of data from users.

ACID Properties of Transactions

  1. Atomicity: all or nothing — a transaction happens completely or not at all. If it aborts, you better have a routine that undoes what it managed to do before abort.
  2. Consistency Preservation: transaction takes database from one consistent state to another. (Business rules, program logic… programmers and end users handle this!)
  3. Isolation: transaction acts as if it is the only thing happening, independent of other transactions.
  4. Durability: if transaction commits, it should stick, surviving any failure.

The system (i.e., what we design) has to handle #1, 2, and 4.

Four levels of isolation:

  • Level 0: doesn’t allow dirty reads
  • Level 1: no lost updates
  • Level 2: no dirty reads, no lost updates (level 0 + level 1)
  • Level 3: no dirty reads, no lost updates, no unrepeatable reads (0 + 1 + 2)

Conflicting operations must (1) be in different transactions, (2) access the same data item, and (3) involve at least one write.

Levels of Recoverability (exam: be able to identify schedules by these levels!):

  1. Recoverable: If T2 reads from data written by T1, T1 must commit before T2 commits. If T1 is committed, it never gets rolled back. But note that if T1 aborts, T2 must abort… cascading rollback! Lots of work!
  2. Avoid Cascading Rollback: T2 only reads from T1 if T1 has committed. Only read from committed transactions!
  3. Strict: T2 cannot read or write X until the last transaction that read X has committed or aborted.

Strict is easiest: all you have to do to recover is UNDO. Your log records old value and new value for each write. you then work backward through the log and replace new value with old value.

Transactions done in serial schedule (no interleaving) are by definition correct.

Serializability: equivalence to a serial schedule of the same transactions. We never serialize schedules; we need to know, though, that we could if we (and our CPU) had all the time in the world. Equivalent means more than just result equivalent (p. 628), since you can get the same results from two different schedules given particular data. View equivalence is stronger, says every read operation reads the same value across schedules. We use conflict equivalence, which says conflicting operations happen in the same order.

Remember: there’s overhead for serializability. It takes away interleaving options and slows us down. But it also keeps our data clean. Doing things right takes time!

Chapter 18: Concurrency Control Techniques

Chapter 17 gives the mathematical basis. Chapter 18 tells us how to get stuff done. (Mathematicians can prove the transition.)

Read locks are sharable; write locks are exclusive.

2 Phase Locking:

  • Basic 2PL: growing phase (more locks), the shrinking phase (fewer locks). Once you give up a lock, you can’t ask for any more (it’s all downhill from here). Enforce this rule, and your schedule is serializable and strict recoverable. Unfortunately, gradual growing phases allow deadlocks: T1 locks Y, T2 locks X, T1 asks for X, T2 asks for Y — neither can proceed.
  • Conservative 2PL: growing phase vertical — grab all locks at once! shrinking phase gradual. No deadlocks, but starvation possible: you have to grab all locks at once, and there’s much more chance that at least one of those locks is already taken.
  • Strict 2PL: gradual growing phase, then gradual shrinking phase for read locks but vertical shrinking phase for write locks (drop all write locks at end). Deadlocks back, but strict recoverable, better than basic.
  • Rigorous 2PL: gradual growing phase, then drop all locks at end: guarantees strict recoverable.

Timestamp ordering: bigger numbers mean younger (20100127 > 20091225). Timestamp ordering gets rid of locks.

Chapter 19: Database Recovery Techniques

When you write to the log, it records the old value and the new value. This allows idempotent UNDO: you can do it over and over and getting the same result as if you had done it just once. If the log recorded an operation (“add 5, multiply by 104%”) instead of the old value, your UNDO process could really goof things up! Record the effect, not the cause.

Checkpoint: suspend operations, flush buffers, add checkpoint. This gives us a chance to guarantee that a certain string of data really has been written to the hard drive. When the system crashes, we need recover and UNDO/REDO only as far back as the checkpoint. We need not REDO any transaction that committed pre-checkpoint, because we know its commit made it to the disk. A transaction that committed post-checkpoint definitely wrote to the buffer, but it may or may not have reached the disk, so we should REDO. A transaction that starts and writes some data before the checkpoint does indeed hit the disk! The transaction may continue and hit commit after the checkpoint, but the chekpoint flushes the buffer, including writes from partially complete transactions, so we should only need to REDO the writes between the checkpoint and the commit.

Immediate Update: each operation writes straight to the buffer. This makes more UNDO!

Deferred Update: we collect writes, really write them all at once at the end of the transaction. This is nice for recovery: if a crash hits before a transaction commits, that transaction hasn’t had a chance to change the database. No UNDO or REDO necessary.

Deferred Update with Forced Write: Commit doesn’t happen until we write to disk. Do this, and you UNDO/REDO no committed transactions.

Always record your write of X to disk before you write to disk! Otherwise, you might lose your history of what you did! Checkpoints work backwards: flush buffer, then record checkpoint upon success. If system crashes between flush and checkpoint, you just go back to the previous checkpoint.

Note: MySQL doesn’t have concurrency control. Not everyone needs concurrency control.

Dr. Stephen Krebsbach introduces us to the course. This is a capstone course. Interestingly, this course is a theoretical response to the practical nature of the preceding database courses in this track. We’re going to talk about the why.

Want to know how advanced we are? We’re starting in Chapter 17. :-)

Get your money’s worth: ask questions! Read the book! Communicate!

First assignment: read Chapters 17-19, watch the videos for each chapter, and come up with good questions for next class period! Watch for homework assignment, probably coming out next week.

And remember: the videos were recorded last year: ignore any references to dates, other assignments, etc.! Admin info will come by e-mail, not video!