Stefan Klinger

Currently I'm employed as a researcher and lecturer with the Database and Information Systems group at the University of Konstanz.


email mail at stefan dash klinger dot de — Send plaintext messages only, no HTML, not exceeding 32kB in size.
phone +49 7531 88 2188
office PZ804
location 47.69106°N, 9.18656°E on OpenStreetMap


Upcoming — Summer'15

All lectures overview

Compiler Construction

Construction of a compiler translating Turner's FPL SASL into SK calculus, and of a “virtual machine” running the generated code.

Topics include: Parsing algorithms, parser generators, classes of context-free grammars. Basic λ-calculus, and SK-calculus. Desugaring, and compilation of a core language. Some simple optimisations in the target VM.

  1. Winter'10
Declarative Programming

Introduction to functional programming with Haskell.

Topics include: Untyped λ-calculus, referential transparency. Basics of the Haskell type system. Lists and other algebraic datatypes. Parametric polymophism, typeclasses, and ad-hoc polymophism. Type inference. Lazy evaluation, WHNF. Monadic computation and IO.

  1. Winter'09
  2. Summer'06
Operating Systems

Fundamental concepts of operating systems: Scheduling, inter process communication, file systems, memory management, ….

Introduction to the C programming language.

  1. Summer'09
Concepts of Programming

Introduction to programming concepts, with a strong focus on the functional paradigm (using Haskell). We learn how to program without side effects; evaluation strategies, data structures, polymorphism, and a simple type system are discussed. The λ-calculus provides a sound formal foundation. This lecture is linked with the Programmierkurs 2.

Programming Course 2

Introduction to functional programming. This lecture is linked with Konzepte der Programmierung, see there.

  1. Summer'14
  2. Summer'13
  3. Summer'11
Programmierung Course 3

The C programming language, and Linux system programming. Reviews operating systems concepts from a practical perspective.

Topics include: Introduction to C, pointer arithmetic, preprocessor, make. Low-level IO, process control, IPC via pipes, shared memory, sockets, and signals. Synchronisation with semaphores. Linking, relocation, static and shared libraries.

  1. Winter'14
  2. Winter'13
Key Competence in Computer Science

Introduction to fundamental tools in a Unix-like environment.

Topics include: First steps with the shell. How to hand in exercises with Subversion. Getting startet with Latex. Using secure shell. Editors vi and emacs. Advanced shell usage, pipelines, scripting. Regular expressions, grep, sed. File archives. Text encoding.

  1. Winter'14
  2. Summer'14
  3. Winter'13
  4. Summer'13


Pathfinder—Full Text

This work demonstrates the extension of the purely algebraic XQuery compiler Pathfinder with an infrastructure for implicit score propagation. This is used to implement a subset of XQuery Full Text, employing the PF/Tijah index for Full Text search.

It is shown that a flexible framework for implicit score propagation can be implemented easily —i.e., minimally invasive— on top of the Pathfinder compiler. The described prototype implementation can be parametrised with different scoring model functions, and should be adaptable to alternative database back-ends and Full Text engines.

At the same time, various systematic problems that arise from implicit score propagation are pointed out, rising the question whether such an approach is useful in general. Flaws in the design of the XQuery language are described that thwart more flexible extensions at the user level.

Stefan Klinger. Pathfinder—Full Text or Extending a Purely Relational XQuery Compiler with a Scoring Infrastructure for XQuery Full Text. PhD thesis, Department of Computer and Information Science, University of Konstanz, December 2010.

Sound ranking algorithms for XML search

Ranking algorithms for XML should reflect the actual combined content and structure constraints of queries, while at the same time producing equal rankings for queries that are semantically equal. Ranking algorithms that produce different rankings for queries that are semantically equal are easily detected by tests on large databases: We call such algorithms not sound. We report the behavior of different approaches to ranking content-and-structure queries on pairs of queries for which we expect equal ranking results from the query semantics. We show that most of these approaches are not sound. Of the remaining approaches, only 3 adhere to the W3C XQuery Full-Text standard.

Djoerd Hiemstra, Stefan Klinger, Henning Rode, Jan Flokstra, Peter M. G. Apers. Sound ranking algorithms for XML search. Proceedings of the 2nd SIGIR workshop on focused retrieval, Singapore, July 24, 2008.

The Haskell Programmer's Guide to the IO Monad — Don't Panic

Why do I need a monad for IO in Haskell? The standard explanation is, that the IO monad hides the non-functional IO actions —which do have side effects— from the functional world of Haskell. But how does this "hiding" work, apart from having IO actions disappearing beyond the borders of my knowledge?

This report scratches the surface of category theory, an abstract branch of algebra, just deep enough to find the monad structure. On the way we discuss the relations to the purely functional programming language Haskell. Finally it should become clear how the IO monad keeps Haskell pure.

This guide tries to fit exactly between the available theoretical literature about category theory on the one side and literature about how to program with monads on the other.

Stefan Klinger. The Haskell Programmer's Guide to the IO Monad — Don't Panic. Technical report, December 2005, no. 05-54, 33 pp., Centre for Telematics and Information Technology (CTIT), ISSN 1381-3625.

Schema Validation and Type Annotation for Encoded Trees

We argue that efficient support for schema validation and type annotation in XQuery processors deserves as much attention as efficient evaluation techniques for XPath queries have received in the past. To this end, we describe a validation procedure that operates on an encoding of trees that has already been successfully used for XPath location step evaluation.

The validation algorithm works without the construction of finite state automata and can exploit properties of the encoding to speed up the validation of already partially type-annotated trees. First experiments —carried out using the database back-end of the authors' XQuery compiler— indicate that this approach can indeed lead to high-throughput validation support.

Torsten Grust, Stefan Klinger. Schema Validation and Type Annotation for Encoded Trees. Proceedings of the ACM SIGMOD/PODS 1st International Workshop on XQuery Implementation, Experience and Perspectives XIME-P. Paris, June 17-18, 2004.

Streaming XML Schema Validation for Relational Tree Encodings

A new way of validating relationally encoded XML documents against XML Schema descriptions is proposed. An enumeration of the nodes of the XML document tree is used as relational tree encoding. An XML Schema description is considered to define a context free grammar.

The proposed algorithm is based on the concept of deriving a regular expression, hence, it is neither necessary to reconstruct the XML tree from its encoding, nor to build a finite state automaton from the XML Schema description. Moreover, the encoded tree is read as a stream, i.e., exactly once, sequentially in document order. This thesis introduces guards, an amelioration of regular expressions which integrates information about the hierarchical structure of trees. The concept of derivation is augmented to make use of the pre/post enumeration and the enriched regular expressions.

Stefan Klinger. Streaming XML Schema Validation for Relational Tree Encodings. Diploma Thesis. Konstanzer Online Publikations System KOPS. April 2004.

All contents © by me. Last updated 2015-Feb-22.