CS 848: Graph Data Management

(Fall 2018)

Semih Salihoglu
firname [dot] lastname [at] uwaterloo [dot] ca
DC 3351
Meeting times: Tue 10:00am-1:00pm
Meeting location: DC 2568

Announcements

Overview

This seminar covers topic in graph data management and processing, starting from the very early graph data models and systems to the current day research on these topics. The most widespread data model underlying existing systems is the relational model, originally invented by Edgar F. Codd in 1970. At a high-level, data in the relational model is modeled as tuples in structured tables and data manipulation and retrieval is expressed using relation operators, such as selection, joins, and projection. In contrast, in graph-based models (at a high-level) data is often represented as a set of nodes or objects and pointers between the nodes. Data manipulation and retrieval is expressed as path finding in the underlying graph or traversals through the nodes. Although systems with graph-based models are not as in widespread use as relational systems in today's world, they have existed since the birth of data management systems. Many people have heard of Edgar Codd and the relational model. Yet, fewer people have heard of Charles Bachman, who is credited as the "inventor of database systems" for leading the development of the first data management system IDS that is based on a graph-based model called the network model.

Through the years, driven by different popular applications in different eras, graph-based systems have become popular. The first half of the seminar will cover the historical waves that made graph data models popular, such as the web and semantic web. The second half of the seminar will cover recent topics about graph data management & processing that are particularly popular in the database research community. Example topics include modern graph databases, graph data processing software based on Hadoop and Spark-like software, knowledge graphs, and example machine learning applications on graphs. The seminar is project-based and each student will do a term-long mini research project preferably on existing systems.

Prerequisites

Students are expected to have taken a course covering the fundamentals of databases at the level of an introductory course. If you are not familiar with database systems, it will be very difficult to enjoy the readings. Having systems background is not necessary but helpful in appreciating the material too.

Workload & Mark Breakdown

The main workload will consist of a term-long project that students will do related to one of the topics covered in the seminar. The other workload includes paper reviews and one presentation. Detailed information for each piece is below. Typically, I will be lecturing or giving a presentation, and leading a discussion in the first half of the seminar. The latter half will have a 25 minute presentation by a student followed by a discussion. This is a seminar, so your participation in the class is very critical to everyone's learning. That is why it will be a significant part of your grade. Please ask questions and make comments throughout the discussions. The workload pieces and mark breakdown is as follows:

• Class Participation: 25%
• Paper Reviews: 15%
• Presentation: 10%
• Project: 50%

Projects

Project Deliverables

• Project Paper: The project papers will be 6 pages. You can have extra pages for the references. They will be written in the two-column ACM proceedings format, using one of the ACM SIG Proceedings Templates. Essentially they should be similar in structure to the papers we read in the seminar.
• Project Source Code: Please put your source code into github and include a link in your project writeup. On the github page, please document exactly how to run your source code.
• Refereeing Papers: You will read three of your peers' papers and write a review for them. Part of the goal is for you to see how the refereeing is done and the discussions that go between members of PCs of workshops and conferences.

Paper Reviews

For each class we will be writing two reviews for two of the papers assigned to that day (except the first seminar). If there are more than two papers assigned, you can pick either one. You are allowed to skip 2 reviews throughout the term. The reviews will be at most 1 page long and roughly 2 paragraphs. You have to finish your review with one question to start a discussion in the seminar. The reviews are due the Monday at 6pm before the seminar. You are expected to (very very) briefly answer the following 6 questions and finish your reviews with a question that can start a discussion in class:

• What is the problem?
• Why is it important?
• Why is it hard? Why don't previous methods work?
• What is the solution to the problem the authors propose?
• What interesting research questions does the paper raise?
• (If related) How does the paper relate to other papers we have read?

Presentations

Each student will be doing 1 presentation in the term. The presentation will be about 25 minutes long. Here are the important points summarizing what you have to do for your presentations.

• You must present with slides. The content in your slides should be your own but you can use others' materials, e.g., figures from the paper we are reading, when necessary and by crediting your source on your slide.
• Please have a separate slide for each of 6 questions about the paper outlined above in the Paper Review section.
• It is very helpful to demonstrate the ideas in the paper through examples. So try to have examples in your presentation, e.g., a simulation of some code or system component.

Schedule and Papers