SQL is a Programming Language

Seminar  INFO4663

---

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.

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 (pro-)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.

In a 25-minute presentation, each participant will talk about the problem he/she has worked on and present a SQL-based solution. Short demos during the presentation are ideal.

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. Your slide material and the paper of the problem and its solution will be in English.

Meetings and Presentation Dates

In the preliminary meeting we will talk about

• the possible programming problems and
• further dates in the semester.

The preliminary meeting will be held during the first week of the semester:
Friday, October 18, 2024 at 10:15 (10ct), room B305.1 (Sand 13).

We will have more obligatory meetings on Sand throughout the semester. Participation is mandatory. Please make sure you are available on all dates before signing up.

The following list includes all mandatory group meetings:

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

Presentations

There are three talks per date and the sessions usually take about 120 minutes. The talks should consist of at least:

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

Focus on the SQL-specific features relevant to your solution — a complete presentation of the code is not appropriate. A live demo with visualization is helpful in order to present the results clearly and visually appealing.

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.

Attendance to all sessions is mandatory as this is a seminar.

General notes for our seminar presentations can be found here.

Seminar Papers

After you first handin your papers, each student will receive two peer papers to read and review. You will handin the review report two weeks later and then find some more time to apply suggestions from your received reviews to your own paper.

Please, consult our general notes on seminar papers here.

Deadlines:

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.