Stefan Klinger

email mail at stefan dash klinger dot de
I prefer receiving plain text messages, no HTML, not exceeding 32kB in size.
github s5k6
location southwest of Munich (OpenStreetMap)

Current Job

Currently I'm employed with GSOC, evaluating and working on software in the ground segment, i.e., related to mission control.

Teaching (before 2017)

I'll keep links to some of my lecture materials for reference. Most of this material has evolved over a couple of years (i.e., has proven successful in many lectures).

Publications (before 2011)

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 2021-03-20.