CS 7575: A Seminar On Relational Language Design (Spring 2026)

Topics and approximate agenda

This schedule will be updated regularly as the class progresses. Check back frequently. I will post my lecture slides by the end of the day following a lecture (thus the *next* day). Reason is that I often walk away from lecture with ideas on how to improve the slides, and that takes time. Presentation slides by the students will likely be only posted on Piazza.

PART 1: Query Language Foundations

Introduces and compares the core relational languages: SQL, Domain and Tuple Relational Calculus, Relational Algebra, Datalog (including recursion with stratified negation). We also study Relational Diagrams, the semantic concept of Relational Patterns, and the Generalized Tuple Relational Calculus together with its Abstract Language Higraphs (a concept generalizing Abstract Syntax Trees). This part is led by the instructor and establishes a conceptual framework for studying new languages.

• Lecture 1 ()
  Course introduction | T1-U1 SQL | PostgreSQL setup | SQL Activities
• Lecture 2 ()
  P1-T1 SQL
• Lecture 3 ()
  P1-T1 SQL
• No class (Mon, Jan 19): Martin Luther King Day
• Lecture 4 ()
  P1-T2 Logic & Relational Calculus
• Lecture 5 ()
  P1-T2 Logic & Relational Calculus
• Lecture 6 ()
  P1-T2 Logic & Relational Calculus
• Lecture 7 ()
  P1-T3 Relational Algebra & Codd's Theorem
• Lecture 8 ()
  P1-T4 Datalog & recursion
• No class (Mon, Feb 16): Presidents' Day
• Lecture 9 ()
  P1-T4 Datalog & recursion
• Lecture 10 ()
  P1-T5 Relational Patterns & Relational Diagrams
• Lecture 11 ()
  P1-T5 Abstract Relational Query Languages & Generalized Tuple Relational Calculus

PART 2: New Proposals and Ongoing Debates

We discuss recent proposals for alternative languages and data abstractions (including graph query languages). Each student presents one or more papers, followed by an in-class discussion and comparative analysis of the language or proposal.

• Lecture 12 ()
  TBD (see list below)
• Lecture 13 ()
  TBD (see list below)
• No class (Mon, March 2): Spring break
• No class (Thu, March 5): Spring break
• Lecture 14 ()
  TBD (see list below)
• Lecture 15 ()
  TBD (see list below)
• Lecture 16 ()
  TBD (see list below)
• Lecture 17 ()
  TBD (see list below)
• Lecture 18 ()
  TBD (see list below)
• Lecture 19 ()
  TBD (see list below)
• Lecture 20 ()
  TBD (see list below)

PART 3: Beyond "traditional" Query Languages

We discuss extensions to the typical relational languages and language not traditionally considered "relational": Answer Set Programming, Disjunctive Logic programming, Integer Linear Programming, APL, J, Pandas, dplyr, SQL++. This part is again led by the instructor.

• Lecture 21 ()
  TBD
• Lecture 22 ()
  TBD
• Lecture 23 ()
  TBD

PART 4: Project presentations

• Lecture 24 (Mon, April 13): P4 Project presentations / P5 Final report
• Lecture 25 (Thu, April 16): P4 Project presentations / P5 Final report
• Lecture 26 (Thu, April 23): P4 Project presentations / P5 Final report

Literature list

PART 1: Query Language Foundations

• Topic 1: SQL
• [SAMS'19] SAMS: Teach yourself SQL in 10min by Forta. 5th ed. 2019. It is available for free for Northeastern students from Safari books eBook (you may have to first login from our library website, then try again the previous link). If the book is checked out online, you can use the 4th edition (there is almost no difference between 4th and 5th ed) as Safari books eBook, or as EBSCOhost eBook.
• [CS 3200] PostgreSQL setup, PgAdmin 4 tutorial. Files to follow along our SQL lectures: SQL Activities, CS 3200 web pages with more detailed slides on SQL.
• [Cow'03] Ramakrishnan, Gehrke. Database Management Systems. 3rd ed 2003. Ch 5: SQL.
• [Complete'08] Garcia-Molina, Ullman, Widom. Database Systems. 2nd ed 2008. Ch 6: SQL.
• [Elmasri, Navathe'15] Fundamentals of Database Systems. 7th ed 2015. Ch 6: SQL
• [Silberschatz+'20] Silberschatz, Korth, Sudarshan. Database system concepts. 7th ed 2020. Ch 3.8: Nested subqueries.
• Topic 2: Logic & Relational Calculus
• [Barland+'08] Barland, Kolaitis, Vardi, Felleisen, Greiner. Intro to Logic, (alternative PDF version). 4.1.2 First-Order Logic: bound variables, free variables, 4.2.1 First-Order Logic: equivalences, 4.4 Exercises for First-Order Logic.
• [Genesereth+] Genesereth et al. Introduction to logics. Ch 6: Relational Logic.
• [Halpern+'01] Halpern, Harper, Immerman, Kolaitis, Vardi, Vianu. On the Unusual Effectiveness of Logic in Computer Science. Bulletin of Symbolic Logic 2001.
• [Cow'03] Ramakrishnan, Gehrke. Database Management Systems. 3rd ed 2003. Ch 4.3: Relational calculus, Ch 4.4: Safety.
• [Elmasri, Navathe'15] Fundamentals of Database Systems. 7th ed 2015. Ch 8.6: Tuple relational calculus, Ch 8.7: Domain relational calculus, Ch 8.6.8: Safe expressions.
• [Silberschatz+'20] Silberschatz, Korth, Sudarshan. Database system concepts. 7th ed 2020. Ch 27.1: Tuple relational calculus, Ch 27.2: Domain relational calculus, Ch 27.1.3 & 27.2.3: Safe expressions.
• [Alice'95] Abiteboul, Hull, Vianu. Foundations of Databases. 1995. Ch 3.1: Structure of the relational model, Ch 3.2: Named vs. unnamed perspective, Ch 3.3: Conventional vs. logic programming perspective, Ch 4.2: Logic-based perspective, Ch 5.3: Relational calculus, domain independence, Ch 5.4: Syntactic Restrictions for Domain Independence.
• [Barker-Plummer+'11] Barker-Plummer, Barwise, Etchemendy. Language, Proof and Logic. 2nd ed. 2011. Ch 11: Multiple Quantifiers.
• [Vardi'13] A Logical Revolution (slides), 2013. [Video @ MSR (1h 15min)]
• Topic 3: Relational Algebra & Codd's theorem
• [Cow'03] Ramakrishnan, Gehrke. Database Management Systems. 3rd ed 2003. Ch 4.2: Relational algebra.
• [Complete'08] Garcia-Molina, Ullman, Widom. Database Systems. 2nd ed 2008. Ch 2.4: Relational algebra, Ch 5.1-5.2: Relational Algebra and bags.
• [Elmasri, Navathe'15] Fundamentals of Database Systems. 7th ed 2015. Ch 8: Relational Algebra.
• [Silberschatz+'20] Silberschatz, Korth, Sudarshan. Database system concepts. 7th ed 2020. Ch 2.6: Relational algebra.
• [Alice'95] Abiteboul, Hull, Vianu. Foundations of Databases. 1995. Ch 4.4: Algebraic perspectives, Ch 5.3-5.4: Codd's theorem: Equivalence of algebra and calculus.
• Topic 4: Datalog & Recursion
• [Complete'08] Garcia-Molina, Ullman, Widom. Database Systems. 2nd ed. 2008. Ch 5.3-5.4: Datalog and bags, Ch 10.2: Recursion in SQL.
• [Cow'03] Ramakrishnan, Gehrke. Database Management Systems. 3rd ed 2003. Ch 24.1-24.2: Datalog.
• [Alice'95] Abiteboul, Hull, Vianu. Foundations of Databases. 1995. Ch 12.2: Datalog and model-theoretic semantics, Ch 12.3: Fixpoint semantics, Ch 13.1: Semi-naive evaluation, Ch 15.2: Stratified semantics and precedence graphs
• [Koutris'19] Lecture notes from CS784 Wisconsin 2019. L9: Datalog evaluation, L10: Datalog negation
• [Gatterbauer, Suciu'10] Stable models: Gatterbauer, Suciu. Data conflict resolution using trust mappings. SIGMOD 2010. [PPTX slides], [PDF slides], [video (24min)]
• [x775'19] x775 blog post: A surprisingly nice introduction to Datalog
• [Soufflé] Soufflé is an open-source Datalog engine. Also see Soufflé tutorial and Soufflé installation. Soufflé files to follow along our lectures on Datalog with stratified negation: Souffle Activities
• [clingo] Postassco/Clingo is an is a disjunctive logic programming system, implementing the stable model semantics under the Answer Set Programming (ASP) paradigm. Download. Running clingo in the browser, More clingo resources. Clingo files to follow along our lectures on ASP: Clingo Activities. Clingo user guide.
• [Eiter+'09] Eiter, Ianni, Krennwallner. Answer Set Programming: A Primer. Reasoning Web International Summer School 2009.
• Topic 5: Relational Pattern & Abstract Relational Query Languages
• [Gatterbauer,Dunne'24] On the Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages, SIGMOD 2024. Slides, Youtube
• [Gatterbauer,Dunne'24] Relational Diagrams and the Pattern Expressiveness of Relational Languages , SIGMOD record 2025.
• [Gatterbauer,Sabale'25] Database Research Needs and Abstract Relational Query Langauge, CIDR 2026 (to appear).

PART 2: New Proposals and Ongoing Debates

• [Chamberlin'24] 50 Years of Queries, CACM 2024.
• [Neumann,Leis'24] A Critique of Modern SQL and a Proposal Towards a Simple and Expressive Query Language, CIDR 2024.
• [Shute et al.'24] Shute, Bales, Brown, Browne, Dolphin, Kudtarkar, Litvinov, Ma, Morcos, Shen, Wilhite, Wu, Yu. SQL Has Problems. We Can Fix Them: Pipe Syntax In SQL, VLDB 2024.
• [Desphande'25] Beyond Relations: A Case for Elevating to the Entity-Relationship Abstraction, CIDR 2025.
• [Aref et al.'25] Aref, Guagliardo, Kastrinis, Libkin, Marsault, Martens, McGrath, Murlak, Nystrom, Peterfreund, Rogers, Sirangelo, Vrgoč, Zhao, Zreika. Rel: A Programming Language for Relational Data, SIGMOD 2025.
• [Dittrich'25] A Functional Data Model and Query Language is All You Need, arXiv 2025.
• [Dittrich'25] How to get Rid of SQL, Relational Algebra, the Relational Model, ERM, and ORMs in a Single Paper -- A Thought Experiment, arXiv 2025.
• [Carey et al.'24] Carey, Chamberlin, Goo, Ong, Papakonstantinou, Suver, Vemulapalli, Westmann.SQL++: We Can Finally Relax!, ICDE 2024
• [Shaikhha et al.'22] Shaikhha, Huot, Smith, Olteanu. Functional collection programming with semi-ring dictionaries. OOPSLA, 2022.
• [Nix,Dittrich'25]. Extending SQL to Return a Subdatabase, SIGMOD 2025.
• [Gatterbauer,Sabale'25] Database Research Needs and Abstract Relational Query Langauge, CIDR 2026 (to appear).
• [Gheerbrant et al.'25] Gheerbrant, Libkin, Peterfreund, Rogova. GQL and SQL/PGQ: Theoretical Models and Expressive Power, PVLDB 2025.
• [Francis et al.'23] Francis, Gheerbrant, Guagliardo, Libkin, Marsault, Martens, Murlak, Peterfreund, Rogova, Vrgoc. A researcher's digest of GQL, ICDT 2023.
• [Atzeni et al.'13] Atzeni, Jensen, Orsi, Ram, Tanca, Torlone. The relational model is dead, SQL is dead, and I don't feel so good myself, SIGMOD record 2013.
• [Stonebraker,Hellerstein'13] What goes around comes around, Intro chapter to readings in database systems, 4th ed, 2005.
• [Stonebraker,Pavlo'24] What goes around comes around... and around..., SIGMOD record 2024.
• ...

PART 3: Beyond "traditional" Query Languages

• ASP & Disjunctive Logic Programming
• [clingo] Postassco/Clingo is an is a disjunctive logic programming system, implementing the stable model semantics under the Answer Set Programming (ASP) paradigm. Download. Running clingo in the browser, More clingo resources. Clingo files to follow along our lectures on ASP: Clingo Activities. Clingo user guide.
• [Eiter+'09] Eiter, Ianni, Krennwallner. Answer Set Programming: A Primer. Reasoning Web International Summer School 2009.
• ...

Research best practice

• [Azuma'19] Everything I wanted to know about C.S. graduate school at the beginning but didn’t learn until later. 1997-2019
• [Dalio'17] Principles by Ray Dalio. Also see Youtubue videos.
• [MIT'20] Version control (git)
• [LaTeX'03] Indian Tex User group Latex Tutorial. An old but still nice comprehensive quick intro to LaTeX
• [Oetiker'21] The Not So Short Introduction to LaTeX.
• [Trettin, Fenn'07] An essential guide to LaTeX usage: Obsolete commands and packages.
• [Kurose'09] 15 pieces of advice I wish my PhD advisor had given me.