In the contexts of database quertying and constraint satisfaction problems (CSPs), the hypertree decomposition method can be used query optimization and for faster CSP solving and for, whereby problem instances having a low hypertree width (i.e., a low degree of cyclicity) can be recognized and decomposed automatically, and efficiently evaluated. Queries and CSPs having bounded hypertree width are also highly parallelizable. The notion of Hypertree decomposition was introduced in 1999. This talk reviews - in form of questions and answers - the main relevant concepts and algorithms and surveys selected related work including applications and more recent results.

In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work in probability theory in the 1960s and in relational database theory in the 1980s produced characterizations of when local consistency implies global consistency. We will discuss two different generalizations of these results: the first considers K-relations over an arbitrary positive semiring K, while the second considers K-relations over an arbitrary positive monoid K. In each of these two settings, we explore when a database schema has the property that every pairwise consistent collection of K-relations over that schema is globally consistent; special cases include the earlier results about local vs. global consistency in relational database theory and more recent results about local vs. global consistency of bags.

This is joint work with Albert Atserias at UPC Barcelona.

Structural recursion is arguably the most important definitional principle in theoretical computer science. Traditionally, one defines (or programs) functions over an inductive datatype by structural recursion over the datatype's constructors. This amounts to writing clauses indicating how the to-be-defined function is supposed to interact with the constructors. For example, to define the length of a list we can write: length Nil = 0, and length (Cons x xs) = length xs + 1. However, this works out of the box only if the datatype is freely generated by the constructors, in that the constructors are injective and non-overlapping. On the other hand, for non-free datypes such as finite sets, bags, and terms with bindings under the nominal representation, mathematicians and computer scientists have devised mechanisms for making structural recursion work with the help of verifying certain conditions.

In this talk, I will distill the ideas underlying recursion on non-free datatypes into the notion of epi-recursor. This is a simple piece of categorical logic that separates the constructor layer from a layer that "sits on top" of it, consisting of operators and properties that further support recursion. I will show how this abstract view can shed light on the relative expressiveness of different recursors. Finally, I will look at the dual problem of supporting corecursion via epi-corecursion, and its applications to defining functions that manipulate infinitary structures with bindings such as Boehm trees.

(Co)-authoring, (re)using, and maintaining complex artifacts such as knowledge bases, ontologies, or software are complex tasks that are supported by a range of powerful tools and for which best practice/methodologies have been developed. Some of these relate to modularity and patterns: the former has been investigated for ontology engineering with some interesting results related to re-use and also to automated reasoning and optimisation. (Design) patterns have been hailed as a reusable engineering solution that supports high quality design, reuse, and comprehension in a number of disciplines including software and ontology engineering. For ontologies, a lot of effort has been spent on identifying, collecting, and classifying patterns - with seemingly little effect on ontology engineering practice. SNOMED CT is an interesting case in point as it is increasingly built using modelling templates as well as tools designed to support the usage of these templates, but the resulting OWL ontology has no signs of the usage of these templates. Recently, we developed a generic framework for identifying regularities in formal languages and investigated various variants of the problem of finding minimal rewritings of a given language using macros. We have developed related algorithms and applied these to existing, large OWL ontologies including SNOMET C; we found that we can find minimal rewritings of these in less than a minute. An interesting point of this application relates to the rather unusual syntax of OWL that poses some non-trivial problems due to the presence of a mixture of ranked and unranked symbols such as “SubClassOf” being binary whereas “DisjointClasses” taking basically any number of symbols. In this talk, I will provide a general overview of the (ontology) engineering challenges mentioned above around modularity and patterns/regularities, and discuss various related solutions and insights gained.