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 | P1-T1 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 (): Remote class via Zoom
  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
• Lecture 9 () / S1 Project ideas
  P1-T4 Datalog & recursion
• Lecture 10 ()
  P1-T5 Relational Patterns & Relational Diagrams
• No class (Mon, Feb 16): Presidents' Day
• 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 () / S2 Project proposal
  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 () / S3 Project intermediate report
  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): S4 Project presentations / S5 Final report
• Lecture 25 (Thu, April 16): S4 Project presentations / S5 Final report
• Lecture 26 (Thu, April 23): S4 Project presentations / S5 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.
• 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 Patterns, Abstract Relational Calculus
• [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, Project web page.
• [Gatterbauer,Dunne'25] Relational Diagrams and the Pattern Expressiveness of Relational Languages, SIGMOD record 2025.
• [Gatterbauer,Sabale'26] Database Research Needs and Abstract Relational Query Language, CIDR 2026.
• [Gatterbauer'26] A Principled Solution to the Disjunction Problem of Diagrammatic Query Representations, SIGMOD 2026 (to appear).

PART 2: Old Proposals, New Proposals, and Ongoing Debates

• General debates about SQL and alternatives
  • [Chamberlin'24] 50 years of queries, CACM 2024. Video of SIGMOD 2023 keynote.
  • [Stonebraker,Hellerstein'05] 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.
  • [Atzeni+'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.
  • [Date'84] A Critique of the SQL Database Language, SIGMOD Record 1984.
  • [Welty, Stemple'81] Human factors comparison of a procedural and a nonprocedural query language, TODS 1981.
  • [Chamberlin'82] On "Human Factors Comparison of a Procedural and a Nonprocedural Query Language", TODS 1982 Technical Correspondence.
  • [Reisner'81] Human Factors Studies of Database Query Languages: A Survey and Assessment, ACM Computing Surveys 1981.
• QUEL
  • QUEL query language, Wikipedia
  • [Stonebraker+'76] Stonebraker, Held, Wong, Kreps. The Design and Implementation of INGRES, TODS 1976.
  • [Stonebraker,Rowe'86] The Design of POSTGRES, SIGMOD Record 1986.
• GoogleSQL, Pipe Syntax
  • [Shute+'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. YouTube video
  • [Shute+'26] Shute, Zheng, Kudtarkar. Semantic Data Modeling, Graph Query, and SQL, Together at Last? CIDR 2026
• SaneQL
  • [Neumann,Leis'24] A Critique of Modern SQL and a Proposal Towards a Simple and Expressive Query Language, CIDR 2024. YouTube video
• Various other Pipe syntax / dataflow suggestions
  • [FunSQL'21]: FunSQL: a Julia library for compositional construction of SQL queries.
  • [RPQL'22]: RPQL: a simple, powerful, pipelined SQL replacement. PRQL ("Pipelined Relational QL" = "Prequel"). YouTube video
  • [Malloy'22]: Malloy: A modern open source language for analyzing, transforming, and modeling data. YouTube video
  • [Olston+'08]: Olston, Reed, Srivastava, Kumar, Tomkins. Pig Latin: a not-so-foreign language for data processing, SIGMOD 2008.
• Graph Query Languages
  • [Gheerbrant+'25] Gheerbrant, Libkin, Peterfreund, Rogova. GQL and SQL/PGQ: Theoretical Models and Expressive Power, PVLDB 2025.
  • [Francis+'23] Francis, Gheerbrant, Guagliardo, Libkin, Marsault, Martens, Murlak, Peterfreund, Rogova, Vrgoc. A researcher's digest of GQL, ICDT 2023.
• Rel from RelationalAI
  • [Aref+'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.
• SQL++ and the nested relational model
  • [Carey+'24] Carey, Chamberlin, Goo, Ong, Papakonstantinou, Suver, Vemulapalli, Westmann.SQL++: We Can Finally Relax!, ICDE 2024
  • [Chamberlin+'18] SQL++ For SQL Users: A TUTORIAL, Couchbase 2018.
• Dataframes
  • ...
• [Desphande'25] Beyond Relations: A Case for Elevating to the Entity-Relationship Abstraction, CIDR 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.
• [Shaikhha+'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.
• ...

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.
• miniKanren
• [miniKanren] miniKanren project website
• [Byrd'09] Relational programming in miniKanren- Techniques, applications, and implementations, PhD thesis 2009.
• [Byrd+'12] Byrd, Holk, Friedman. miniKanren, live and untagged: Quine generation via relational interpreters (programming pearl), Scheme 2012.
• [Byrd+'17] Byrd, Ballantyne, Rosenblatt, Might. A Unified Approach to Solving Seven Programming Problems (Functional Pearl) (interactive paper), ICFP 2017.
• [Friedman+'18] Friedman, Byrd, Kiselyov, Hemann. The Reasoned Schemer, MIT press 2018.
• ...

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.