Troels' links: Relational database systems

—Focusing on the SQL-standard, hierarchical and temporal data, and open source software.

Related to SQL standards

Unfortunately, the SQL standard isn't freely available; it must be bought from ISO or INCITS. You may also be able to leaf through (and perhaps even borrow) it at your local standards organization. Freely available resources:

A late draft of the SQL:2011 standard.
About SQL:2011's new temporal features:
Standards information from Whitemarsh Information Systems Corporation. Most importantly: A rather final draft of the SQL:2008 standard: A big zip-file, containing 5CD2-02-Foundation-2006-01.pdf (and other documents).
JCC: Status for the standardization work.
Overview article by Andrew Eisenberg, Jim Melton, and others, covering the important news in SQL:2003.
Jonathan Leffler: Backus-Naur Form (BNF) grammars for SQL.
Of historical interest:
- Rather late draft of SQL:2003 standard: A big zip-file containing 5WD-02-Foundation-2003-09.pdf (and other documents).
  Also interesting: Also interesting: Comprehensive slide-set by Krishna Kulkarni: Overview of SQL:2003 (PDF file).
- A reasonably final draft of SQL-92 (large plain-text file).
SC32 WG3 (also called Database Languages): The group working on the SQL standard. Requires a login/password, sometimes.
SQL validators from Mimer Information Technology's web site.
Reserved words
- according to standard
- in common products
Barry & Associates, Inc: Database concepts and standards.
My own page about important SQL differences between different RDBMS products.

(See also the link to the book by Jim Melton and Alan Simon.)

Hierarchical data in RDBMSs

Original works:
- Vadim Tropashko introduces the Nested Intervals Model in Trees in SQL: Nested Sets and Materialized Path. The article has been followed up by articles discussing different numeric path encodings:
  - Binary rational number encoding—Relatively easy to understand, but hard to manage for the DBMS when the tree grows large:
    - Relocating Subtrees in Nested Intervals Model: How parts of hierarchies are moved in the Nested Intervals Model.
    - Integer Labeling in Nested Intervals Model.
  - Refined encodings—harder to understand(?), but better real-World performance:
    - Nested Intervals with Farey Fractions.
    - Nested Intervals Tree Encoding with Continued Fractions. See also: A discussion about errata in the article.
    See also a message where the author gives some reading-hints.
  - Review, and introduction of Path Matrices in the June '05 edition of SIGMOD Record.
  - In the second half of a usenet message, Mr Tropashko summarizes pros and cons of the different encoding systems.
- Joe Celko: Trees in SQL: Covers the Nested Set Model; mentions adjacency list model.
- Dan Hazel proposes an alternative to Celko's and Tropashko's encodings in Using rational numbers to key nested sets.
- Dong et al: Maintaining Transitive Closure of Graphs in SQL (see upper right corner for PDF-version).
Books:
- Vadim Tropashko's SQL Design Patterns includes good chapters about trees and digraphs in SQL databases. The book contains a few errors; unfortunately, the book's errata page is hard to find. Publicly available chapters:
  - Chapter 3: Exotic Operators in SQL
  - Chapter 3: Trees
- Joe Celko: Trees and Hierarchies in SQL for Smarties. Chapter 2, Adjacency List Model, is available at SQLSummit.
Articles and tutorials:
- Comparison of hierarchical query methods, by Vadim Tropashko.
- Aaron Mackey: Relational Modeling of Biological Data: Trees and Graphs (adjacency list, nested set, transitive closure tables). Mackey has also co-written a related slide-set about relational databases, aimed at biologists.
- Lennart Jonsson: Representing Trees in a relational DB (materialized path, transitive closure tables).
- Anirban Dutta: Trees in SQL: Nested Sets and Materialized Path
- Bill Karwin: Models for hierarchical data
- Joe Celko: Hierarchical SQL (at ONLamp). Covers two variants of the materialized path approach.
- Tom Haughey: Modeling Hierachies (adjacency lists, nested sets).
- Daniel Aioanei & Adi Malinaru: General trees persisted in relational databases.
- From c2: Doc Query In Sql.
- Gijs Van Tulder: Storing Hierarchical Data in a Database (adjacency model and nested set model in an PHP+MySQL context).
- Phillip J. Eby: The simplest(?) way to do tree-based queries in SQL; covers transitive closure tables.
- Stack Overflow overview-Q/A on the subject
Articles for PostgreSQL users:
- Michael Glaesemann: Static Hierarchies and Binary Fractions in PostgreSQL.
- Shawn Deleurme: A Nested Set Implementation in Java and PostgreSQL.
- Quassnoi:
  - Adjacency list vs. nested sets: PostgreSQL
  - PostgreSQL: nested sets and R-Tree
Articles for users of Microsoft's SQL Server:
- MSSQL 2008's new hierarchyid data type, for implementing efficient materialized path hierarchy encodings. More on the subject.
- Quassnoi: Adjacency list vs. nested sets: SQL Server
- Eugene Lepekhin: Trees in SQL databases.
- Dennis W. Forbes: Versatile High Performance Hierarchies in SQL Server: How to implement the Nested Set Model.
- Kendall Willets: SQL Graph Algorithms.
- From sqlteam.com: More Trees & Hierarchies in SQL (adjacency list, materialized path).
- Pure Performance, Inc: Managing Hierarchical Data in SQL
Articles for Oracle users
- Philip Greenspun: Trees in Oracle SQL.
- Rene Nyffenegger: START WITH and CONNECT BY in Oracle SQL.
- Quassnoi: Adjacency list vs. nested sets: Oracle
Articles for MySQL users
- Quassnoi: Hierarchical queries in MySQL
- Mike Hillyer: Managing Hierarchical Data in MySQL (adjacency list, nested set).
Articles/libraries for Python programmers
- The Django Treebeard project.
Michael M. David has written several articles and a book about modelling hierarchical structures—including XML—in standard SQL, using outer joins.
- Advanced Data Access Technologies, Mr. David's company site; contains several articles about modeling hierarchical structures in standard SQL, including a general tutorial on the subject.
- TDAN articles:
  - Part 1, In XML: Using SQL to Link Below the Root
  - Part 2, In SQL: Processing XML's Complex Hierarchical Structures
- SIGMOD article: ANSI SQL Hierarchical Processing Can Fully Integrate Native XML
- Mr. David has also written a book about the subject: Advanced ANSI SQL Data Modeling and Structure Processing.
  The book's site has a sample chapter named Data Structure Extraction (DSE) Technology. — And at Amazon, you may browse another (small) part of the book.
XML in RDBMSs:
- InfoWorld special report: Relational databases get a grip on XML.
- Cohen et al: Labeling Dynamic XML Trees (postscript document).
- Ronald Bourrets site about XML and databases.
LDAP-related:
- From OpenLDAP's FAQ: Directories vs. Relational Database Management Systems.
- An IBM paper about the challenges which arise when using DB2 as an LDAP backend (requires IEEE Xplore subscription).
Implementations:
- developerWorks: Migrating Recursive SQL from Oracle to DB2 UDB (note: DB2's recursive SQL feature is close to SQL:1999, while Oracle's CONNECT BY is non-standard).
- Dan Sullivan: Heirarchical Queries in SQL Server 2005.
- Oracle's built-in facilities for hierarchical queries
- ltree PostgreSQL module for materialized path trees.
- Not an RDBMS, but still interesting: OpenLDAP.

Temporal databases

Online book (thesis) by Christian S. Jensen: Temporal Database Management.
The web-site of Richard T. Snodgrass contains multiple relevant resources, including an online book (see first paragraph in the publications page).
From Steve Barker's excellent lecture notes: Temporal and Active Databases (gzipped postscript document).
Temporal Access for Users (TAU): Somewhat experimental software products that implement ideas from temporal database theories.
TimeCenter, an international center for the support of temporal database applications on traditional and emerging DBMS technologies.
Temporal Database Glossary.
Book by Date, Darwen and Lorentzos: Temporal Data & the Relational Model. A number of summary slide sets related to the book exist online.
Darwen & Date: An Overview and Analysis of TSQL2 (TSQL2 was a proposed addition to SQL, but never made it into the standard).
The Chorochronos research network.
On persistent B-trees (AKA multiversion B-trees), a data storage structure which may be used to implement temporal database software:
- Lars Arge's External Memory Data Structures mentions partially persistent B-trees (AKA multiversion B-trees).
- Becker, Geschwind, Ohler, Seeger, Widmayer: An asymptotically optimal multiversion B-tree. An expanded version (also featuring a more readable layout) is available if you have access to The VLDB Journal.
- TPIE ("Transparent Parallel I/O Environment") has been used by some to implement persistent B-trees (and many other storage structures) in C++.
The Nykredit Center for Database Research has spun off software and several (online) theses.

Various important subjects

Normalization

William Kent: A Simple Guide to Five Normal Forms in Relational Database Theory
Tony Marston: The Relational Data Model, Normalisation and effective Database Design
Tore Bostrup: Introduction to Relational Databases - Part 1: Theoretical Foundation
Ronald Wyllys Steps in Normalization

Key types

Joe Celko: Keys and History

Books about relational database systems

Online books

Neeraj Sharma et al: Database Fundamentals
Bruce Momjian: PostgreSQL: Introduction and Concepts
Worsley, Drake: Practical PostgreSQL
Philip Greenspun: SQL for Web Nerds (assumes access to an Oracle 8 system)
IBM: SQL Getting Started
Graeme Birchall: DB2 SQL Cookbook

Books with online resources

Focus on general relational database topics

C.J. Date's An Introduction to Database Systems is a classic. In addition to the sample chapters on the book's page at Addison Wesley, Appendix D—Storage Structures and Access Methods—is available on the publisher's ftp-site.
Raghu Ramakrishnan and Johannes Gehrke's Database Management Systems is recommendable. On it's page with supporting material, a chapter from the book—Query-by-Example—is online.

Focus on SQL

Melton, Simon: SQL:1999—Understanding Relational Language Components.
Chris Fehily: SQL: Visual QuickStart Guide; teaches SQL by first describing the standard-based approach, and then how to adjust to the real World, using MS Access, MS SQL Server, Oracle, MySQL, PostgreSQL and DB2. A sample chapter—Retrieving Data from a Table —is available online at the publisher's website. Full disclosure: I was technical editor on the second edition of the book.
Kevin E. Kline's nice SQL in a Nutshell has recently been updated with a 3rd edition.
Gulutzan, Pelzer: SQL Performance Tuning. Introduction chapter online.
Bowman, Emerson, Darnovsky: The Practical SQL Handbook—Using SQL Variants (online sample chapter: Selecting Data from the Database).

Focus on performance

Sasha, Bonnet: Database Tuning: Principles, Experiments, and Troubleshooting Techniques covers performance tuning topics in general, and in several specific RDBMS products (chapter 6—Case Studies From Wall Street—is online). See also: Its website.

Other books

Abiteboul, Hull, Vianu: Foundations of Databases (the "Alice book").
Garcia-Molina, Ullman, Widom: Database Systems: The Complete Book is a good, general textbook about (R)DBMSes.
Gulutzan, Pelzer: SQL-99 Complete, Really is said to be a good.
Celko, Joe: SQL for Smarties is a great resource for advanced SQL.

Free online magazines

ACM's SIGMOD Record
DBAzine.com
SQLSummit is regularly updated with new interviews and (links to) articles
Database-related articles in informIT
The Data Administration Newsletter
Rudy Limeback's Ask the Experts—SQL column
Database Journal
A. Elein Mustain's General Bits about PostgreSQL
Intelligent Enterprise—database information center

Tutorials and documents

SQL tutorials and documents

Gordon Russell: Database eLearning
From the web-site of FirstSQL: SQL Tutorial (should be implementation-neutral dispite hosted by a DBMS vendor)
James Hoffman's widely referenced tutorial
André Müller: SQL - Tutorial and Reference
SQLCourse.com
Andrew Cumming: A Gentle Introduction to SQL, an interactive SQL tutorial
Database Answers features a number of data modelling recipes and a modelling tutorial
A basic SQL tutorial at W3Schools
Larry Truett: SQL Reference and Example Site
Wikipedia's SQL page

Link collections

IT Information: Database Resources by Employee Computer Online IT Training is a collection of hand-picked links to introductions to database subjects.
Christopher Browne's RDBMS-links, focusing on solutions for Linux
John Lim's DB page
Ocelot—Peter Gulutzan and Trudy Pelzer's site

Interesting DBMS products

Open source

PostgreSQL—my favorite, because of the nice feature set.
Drawbacks:
- Default configuration often has to be adjusted to get good speed. In addition to the manual, two handy configuration guides exist: One for generation 7.4 and one for generation 8.0.
- No built-in replication support (the community seems to be gathering around Slony as the de facto standard for asynchronous replication solution, though).
- Bad collation sequence support.
- Limited OLAP features.
- Views only updatable if you write special rules (but once you learn the rule system, updatability is limited only by your sanity).
Documentation.
MySQL: Runs fast on all systems, easy to administer, well-defined replication features for simple replication setups.
Drawbacks: In its default configuration, it has some strange and serious SQL standards violations (example: a totally redefined meaning of the concatenation-operator). MySQL also has limited OLAP functionality.
Certainly, MySQL is relevant in some situations, but make sure you have read about the many serious MySQL gotchas before you consider it.
MySQL's interpretation of the GNU General Public License is very strict; this means that in some commercial contexts, MySQL is not free of charge.
Firebird/Interbase Less widely used than PostgreSQL and MySQL, but are said to provide good features.
I haven't had the time to try it yet, but MonetDB sounds interesting.

Closed source

Mimer SQL: Very good SQL-standards support (close to 100% core, but few non-core features). Runs on many platforms. Unclear pricing.
FirstSQL: Claims extensive SQL standard support. Seems to have interesting facilities to soften the object-relational "impedance mismatch" often encountered when wanting to store/retrieve Java objects.

DBMS rebels

Darwen & Date: The Third Manifesto—proposed foundation for future database systems.
Database Debunkings: Persistent Prevailing Database Fallacies Dispelled. Contains a fair share of—probably justified—critique of the DBMS industry.
Rel—An Implementation of Date and Darwen's "Tutorial D".