SQL is a Programming Language

Seminar  INFO4663
Degree  Master

---

Readers

Torsten Grust • Louisa Lambrecht • Denis Hirn • Tim Fischer • Björn Bamberg

Prerequisites

Advanced SQL

Participants

6

⚠️ Signup

To apply for enrollment in this seminar, send an email to db-lehre@cs.uni-tuebingen.de by Tuesday, October 15th, 8:00 am with the name of the seminar in the subject line and the following content:

• matriculation number
• course of study
• intended degree
• number of semesters
• Which courses in the (wider) field of database systems have you already attended?
• preferred 2 topics you could imagine working on (see Topics) There is a limited number of places. Writing an email does not guarantee one. Acceptance/rejection emails will be sent later that day.

Topic

SQL is the query language for the relational data model, which can be used to merge, group, and filter data from different tables. But SQL can do more than that. SQL’s history dates back to the 1970s, and since then the language has steadily evolved, transformed, and extended. Today’s modern SQL is declarative, expressive, often very compact and also elegant. Since the introduction of recursion in SQL, the language is also computationally complete: there is no problem that cannot be cracked with SQL.

In this seminar, participants each work on a self-contained programming problem and construct a solution exclusively in SQL (PL/SQL is not allowed). We advise using PostgreSQL or DuckDB. For this, we choose problems that lead to (1) an interesting algorithm, (2) solve puzzles of different types, (3) perform simulations, (4) can be visualized in an appealing way, etc. fun and eureka moments are in the foreground.

In any case, the problems will not be “typical relational” and will not lead to SELECT * FROM table;: SQL has a lot more to offer and in this seminar you will provide numerous proofs.

If you encounter a problem “hitch” in solving/implementing the problem, this is not a show stopper: you will be given tips on how to do this – no one has to fail this seminar because of this.

Meetings

We will have weekly meetings

• at Sand 13, 72076 Tübingen in room B305.1
• on Fridays, 10-12 am.

Participation is obligatory (attendance is not optional like in lectures). If you do not attend the first appointment (October 18, 2024), you will unfortunately not be able to take part in the seminar.

Contact

If you have any questions, feel free to contact Louisa Lambrecht .

Exam

The seminar examination consists of a presentation and a paper. Your slide material and your paper of the problem and its solution will be in English.

Each participant will talk and write about the problem he/she has worked on and present their SQL-based solution. Focus on the SQL-specific features relevant to your solution — a complete presentation of the code is not appropriate (neither in the presentation nor the paper). Make sure to include visually appealing graphics and/or terminal output and/or simple ui visualisation of your problem/relevant steps in between.

Presentations

There is a time limit of 25 minutes per talk. Do not overrun. Afterwards there will be a short Q&A session of about 5 minutes. Prepare your code editor to be able to answer questions about the code.

The talks should consist of at least:

• the problem description,
• an explanation of the implementation
• and of a live demo.

General notes for our seminar presentations can be found here.

Paper

On 5-6 pages, each student will have the opportunity to present their solution in form of a scientific paper. We will use the ACM template that is common for many conferences in the database community.

In a review cycle, students will receive their fellow students’ papers and provide peer feedback in form of a written review. After writing reviews for others and receiving the reviews for their own paper, each participant will have about two weeks to incorporate the feedback into their final submission.

Please, consult our general notes on seminar papers here.

Presentation Dates and Paper Deadlines

The student presentations (part 1 of the seminar examination) will be on

• Friday, December 6, 2024 at 9:30 and
• Friday, December 13, 2024 at 9:30

The submission deadlines for the student papers (part 2 of the seminar examination) are:

Topics

Below you will find a list of the tasks that will be realized in this seminar using SQL. You will receive the exact details (e.g. which format the inputs are) and hints for the implementation from your supervisor.

• Visibility in 3D-Terrain

  Which points of a hilly terrain are visible from a given viewer position? While nearby hills block the view of points behind them, higher peaks may still be visible, even if they are far away. This visibility problem can be solved with so-called max scans, which you will use in this task.

• Generation of Pixel Graphics from Braille Characters

  The Unicdode character set contains all Braille characters, which were originally designed to give blind people access to printed materials by tactile recognition. These characters arrange 2 × 4 pixels rectangularly (examples of braille characters are ⠝ ⡞ ⡿ ⣠ ⣿). Since Unicode contains all 2⁸ pixel combinations as characters, you can represent any pixel graphics in plain text form this way, see also the Drawille project. This seminar topic replicates this conversion of pixel graphics into Braille text form in SQL.

• Distance-Vector Routing

  If the connections in a network of hosts differ strongly (in terms of throughput, performance), Distance-Vector Routing can still efficiently compute routes of good quality. The hosts use the so-called Distance-Vector Routing tables. This seminar topic accomplishes the construction (and maybe even dynamic updates?) of these routing tables in SQL and based on this calculates efficient routes through a network based on them. berechnet darauf basierend effiziente Routen durch ein Netzwerk.

• Pathfinding with the A*-Algorithm in a 2D-Grid

  To find the shortest path between two points in a timely manner on a 2D grid, there are many ways. One possible way is to calculate this path with the help of the A*-algorithm. Your task is to to implement this algorithm.

• Dynamic Time Warping

  DTW allows to detect similarities between two time measurements. The larger the DTW value, the more different the data. For example, if a slow runner and a fast runner were to run the same path, measuring different elevation positions at the same times, DTW would still recognize that these two measurements are very similar.

• Handwriting Recognition

  Letters are drawn in handwriting on a tablet. How can the corresponding letters be determined from the resulting lines? A simple procedure is to simplify them to such an degree that certain characteristics can be determined and compared with known letter patterns. This task impressively demonstrates how, with the help of simple methods, handwriting and other drawings can be recognized and used as input for computer programs. Find more information here.

• Waterfall of Sand

  Advent of Code 2022, Day 14: Sand drizzles into a cave. How much sand do you need to fill up the cave?

• Tunnel your way out

  Advent of Code 2022, Day 16: You are inside a volcano with a network of pipes and valves. Find a way to free the elephants from the volcano before it erupts.

• Avoiding Snow Blizzards

  Advent of Code 2022, Day 24: In front of you there is a valley you have to cross. Snow blizzards with sharp pieces of ice make straightforward crossing impossible. Find a way through the valley without getting hurt by the dangerous snow blizzards.