• Ch. 8 (except for 8.7.1): RA, RC, Datalog, recursion

• Ch. 9.7, pp. 229-230): recursive SQL

• Ch. 10.1, pp. 235-236: the closed-world assumption

• Ch, 11 (except for 11.2.1): indexing and text retrieval

• Ch. 12 (except for 12.4): multimedia indexing and similarity querying

for on-line handouts, consult the "Handouts" and "Resources" sections of the course web site

• Elements of Relational DB Theory (Kanellakis, pp. 1079-1082 of Theory Handbook)

• Handout on predicate calculus & relational calculus (from Ullman's database textbook)

• Two SQL 3 papers for standards committee (by Hamid and Pirahesh, for SQL3 standards committee)

• Aggregation paper (Klug, 1982)

• O2 data model and query language (from Bancilhon's O2 book)

• Illustra as an object-relational system (from O'Neil's database textbook)

• Flexible and Efficient Similarity Querying for Time-series Data (Goldin paper)

• Solutions for midterm and homework 2

Syllabus

1. Relational DB Theory

• Introduction: Database systems vs. file systems; conceptual vs. logical vs. physical levels;

• Review of relational databases; attributes and their domains;

• Set-theoretic view of relations; finiteness of DB models;

• Queries as mappings; query equivalence;

• Relational algebra (RA): syntax and semantics; Proving correctness of RA output; Relation between RA and SQL;'

• Relational calculus (RC): its roots in Predicate Calculus; syntax and semantics;

• Flavors of RC: tuple vs. domain RC; named vs. numbered attributes;

• Translating between TRC and DRC;

• Domain independence and query safety; translating RA to safe DRC

• Non-recursive Datalog; translating Datalog to safe DRC

• Equivalence of RA, RC, and non-recursive Datalog

• The relation between RA and SQL

2. Recursion and Aggregation

• Reachability, transitive closure: typical non-relational query (not expressible in first-order logic); examples of applications needing Reachability/TC

• Recursion in Datalog and RC: combining predicate use with predicate definition; minimal fixpoint semantics

• Analyzing recursive Datalog programs: predicate dependency graphs;

• Combining recursion w/negation: stratification to assure existence of fixpoint;

• Types of recursion: direct / mutual, linear / non-linear;

• Extending RA for recursion: "loop until" construct

• The SQL3 effort at adding recursion: on the usefulness of DB theory

• Aggregation: syntax and semantics

• Klug's aggregation paper: an example of a well-written DB theory paper

3. Object-relation and Object-Oriented DBs

• Complex values: extending value structure beyond relational.

• OODB properties: hybridizing object-oriented systems and complex-value databases

• Objects vs. values: the role of object identity and data sharing

• Encapsulation, inheritance hierarchy

• O2: an example of an OODB

• Object-relational systems: between OODB and RDB; Illustra as an ORDB

4. Semistructured data and XML

• XML introduction (xml_intro.ppt): relation to HTML, syntax

• XML data model (data_model.ppt): tree-based, originally semistructured data model

• XML path expressions (xpath.ppt): building blocks for XML querying

• XML query language (xquery.ppt): FLWR syntax

• Publishing relational data in XML (xpublishing.ppt): raw mode, auto mode, explicit model

• Semantics of semistructured data (semantics.ppt): bisimulation as equivalence notion

• The QUIP system for XML querying (http://developer.softwareag.com/tamino/quip/)

5. Similarity Querying and Text Retrieval

• Ch, 11 (except for 11.2.1)

• Ch. 12 (except for 12.4)

• Querying time-series data with scaling and shifting: using normalization technique (Goldin paper)