CSE 291: Data Models in the Big Data Science Era
Spring 2019

IMPORTANT ANNOUNCEMENT: The June 13 final exam slot listed on TritonLink with NOT be used. Instead of a written final exam, we will have in-class presentations. Do not worry about clashes with your other final exam slots.

The course surveys a wide range of data models, high-level query languages and models of computation that have achieved prominence with the advent of the (Big) Data Science revolution. The course emphasizes the universal principles and ideas underlying these models and languages, connecting them to their common roots in object-oriented and SQL databases.

The topics are presented in a unifying framework and include:

key-value pairs as data model, as used in Google's Big Table;
Object- Oriented Data Model, with its practical support in relational databases via the Object-Relational Mapping (involves ODMG standards ODL and OQL, and recent systems such as Ruby on Rails);
semi-structured databases (a.k.a. graph databases). Data are organized as graph with labels on nodes and edges), with query languages based on reachability constraints between nodes: conjunctive regular path queries);
XML databases, as special case of graph databases in which the graph is a tree (this involves associated standards such as XML Schema, XPath and XQuery);
RDF databases (with associated OWL and SPARQL standard), also as special case of graph databases
JSON databases (also as special case of graph databases)

Announcements and Discussion Forum Please sign up for the course's Piazza page for regular announcements and a discussion board.

Prerequisites Prior exposure to SQL (either in an introductory db class or programming experience)

Textbook There is no required or recommended textbook. The class Web site offers all necessary reading material (slides/papers/book chapters). If interested in delving deeper, contact Alin for relevant (text)book recommendations.

Topics Covered

Relational (Very quick recap, to contrast and compare)

Entity/Relationship Model (slides)
Relational Data Model (slides)
The standard query language SQL (slides)
A query language based on pattern matching: QBE (Query by Example) (slides, textbook chapter, practice, solutions)

Beyond relational

Object-oriented and object-relational databases
- Object-oriented Data Model
- OO Databases
- The ODMG standard's Object Definition Language (ODL) and Object Query Language (OQL): (slides, practice)
Graph Databases (a.k.a. Semi-structured Data Model)
- Query languages based on regular path expressions (slides)
- Semantic web data and query languages (RDF, RDFS & SPARQL , OWL-S, Description Logics)
- JSON databases and query languages (e.g. AsterixDB, Couchbase, MongoDB, SparkSQL)
- Neo4J's Cypher graph query language (Neo4j tutorial, Cypher tutorial, Cypher short reference)
- XML (data model, XPath/XQuery query language standards)
Text Databases
- Keyword search languages
- Full-Text search languages and indexing (SOLR/Lucene)
The Key-Value Pairs model and Representative Systems (Google BigTable, Redis, Voldemort, etc.)
Programming Paradigms for Parallel Computing (time permitting)
- Map-Reduce programming for arbitary data collections (emphasis on high-level languages such as SparkSQL, HiveQL and PigLatin that are compiled to map-reduce jobs)
- Parallel Graph Processing based on Valiant's Bulk Synchronous Parallel model of computation (a la Pregel, Giraph, GPS, GraphLab)
Grading There are two grading options.
- HW+presentation There will be 4 homeworks (programming assignments, each worth 20% of the grade) and a final in-class presentation of a research paper (20%).
- Research project You may instead submit a research-oriented project (topic to be approved by instructor beforehand).
Papers you may present in class
- Minimization of Tree Pattern Queries. S. Amer-Yahia et al.
- Efficient Algorithms for Tree Pattern Minimization P. Ramanan
More XPath Optimization