Usually, we are confronted with sets at a very early period of our education. Depending on the respective nationality, it is approximately at the age of 10 or 11 years. Thus we carry with us quite a burden of concepts concerning sets. At least in Germany, Mengenlehre as taught in elementary schools will raise bad memories on discussing it with parents of school children. All too often, one will be reminded of Georg Cantor, the inventor of set theory, who became mentally ill. At a more advanced level, we encounter a number of paradoxes making set theory problematic, when treated in a naïve way. One has to avoid colloquial formulations completely and should confine oneself to an adequately restricted formal treatment.

The situation does not improve when addressing logicians. Most of them think in just one universe of discourse containing numbers, letters, pairs of numbers, etc., altogether rendering themselves susceptible to numerous semantic problems. While these, in principle, can be overcome, ideally they should nevertheless be avoided from the beginning.

In our work with relations, we will mostly be restricted to finite situations, which are much easier to work with and to which most practical work is necessarily confined. A basic decision for this text is that a (finite) set is always introduced together with a linear ordering of its elements. Only then we will have a well-defined way of presenting a relation as a Boolean matrix.

Already in the previous chapters, relations have shown up in a more or less naïve form, for example as permutation matrices or as (partial) identity relations. Here, we provide ideas for more stringent data types for relations. Not least, these will serve to model graph situations, like graphs on a set, bipartitioned graphs, or hypergraphs.

What is even more important at this point is the question of denotation. We have developed some scrutiny when denoting basesets, elements of these, and subsets; all the more will we now be careful in denoting relations. Since we restrict ourselves mostly to binary relations, this will mean denoting the source of the relation as well as its target and then denoting the relation proper. It is this seemingly trivial point which will be stressed here, namely from which set to which set the relation actually leads.

Relation representation

We aim mainly at relations over finite sets. Then a relation R between sets V, W is announced as R : V → W.

— as a set of pairs {(x, y),…} with x ∈ V, y ∈ W

— as a list of pairs [(x,y),…] with x∷V,y∷W

— in predicate form {(x, y) ∈ V × W ∣ p(x, y)} with a binary predicate p

Lattices penetrate all our life. Early in school we learn about divisibility and look for the greatest common divisor as well as for the least common multiple. Later we learn about Boolean lattices and use union and intersection “∪,∩” for sets as well as disjunction and conjunction “⋁,⋀” for predicates. Concept lattices give us orientation in all our techniques of discourse in everyday life - usually without coming to our attention. Nevertheless, lattices completely dominate our imagination. Mincut lattices originate from flow optimization, assignment problems, and further optimization tasks. It is well known that an ordering can always be embedded into a complete lattice. Several embedding constructions are conceivable: examples are cut completion and ideal completion.

We introduce all this step by step, concentrating first on order-theoretic functionals. Then we give several examples determining the maximal, minimal, greatest, and least elements of subsets. Thus we learn to work with orderings and compute with them.

Maxima and minima

Whenever an ordering is presented, one will be interested in finding maximal and minimal elements of subsets. Of course, we do not think of linear orderings only. It is a pity that many people – even educated people – colloquially identify the maximal element with the greatest. What makes this even worse is that the two concepts often indeed coincide. However, the definitions and meanings become different in nature as soon as orderings are not just finite and linear.

Since the development of lattice theory, it became more and more evident that concepts of upper and lower bounds, suprema and infima did not require orderings to be linear. Nevertheless, fuzziness was mainly studied along the linear order of IR and only later began to be generalized to the ordinal level: numbers indicate the relative positions of items, but no longer the magnitude of difference. Then we moved to the interval level: numbers indicate the magnitude of difference between items, but there is no absolute zero point. Examples are attitude scales and opinion scales. We proceed even further and introduce relational measures with values in a lattice. Measures traditionally provide a basis for integration. Astonishingly, this holds true for these relational measures so that it becomes possible to introduce a concept of relational integration.

With De Morgan triples, we then touch yet another closely related concept of relational methods of preference aggregation.

Modelling preferences

Anyone who is about to make important decisions will usually base these on carefully selected basic information and clean lines of reasoning. In general, it is not too dificult to apply just one criterion and to operate according to this criterion. If several criteria must be taken into consideration, one has also to consider the all too common situation that these provide contradictory information: ‘This car looks nicer, but it is much more expensive’.

A full account of relation algebra cannot be given here, just enough to enable us to work with it. This will be accompanied by examples showing the effects. When relations are studied in practice, they are conceived as subsets R ⊆ X × Y of the Cartesian product of the two sets X, Y between which they are defined to hold. Already in Chapter 3, we have given enough examples of relations between sets together with a diversity of ways to represent them. We will now present the operations on relations in a way that is both algebraically sound and suficiently underpinned with examples.

With this algebraic approach we start in full contrast to such texts as, for example, [125], where relations are also presented in extensu. There, however, everything is based on point-wise reasoning.

Typing relations

In many cases, we are interested in solving just one problem. More often, however, we want to find out how a whole class of problems may be solved. While in the first case, we may use the given objects directly, we must work with constants and variables for relations in the latter case. These variables will be instantiated when the concrete problem is presented.

Let us consider timetabling as an example. It may be the case that a timetable has to be constructed at a given school. However, it would not be wise to write a timetabling program just for this school with the present set of teachers and classrooms. If it is intended to sell the program several times so that it may be applied also to other schools, one must allow for the possibility of different sets of teachers, different sets of classrooms, etc.

At this point of the book, a major break in style may be observed. So far we have used free-hand formulations, not least in HASKELL, and have presented the basics of set theory stressing how to represent sets, subsets, elements, relations, and mappings. However, so far we have not used relations in an algebraic form.

From now on, we shall mainly concentrate on topics that inherently require some algebraic treatment. We cannot start immediately with formal algebraic proofs and with the relational language TituRel in which all this has been tested. Rather, we first present Part II, which is full of examples that demonstrate the basics of algebraic rules. Whenever one of these early rules needs a proof, this proof will be very simple, but nevertheless omitted at this point. The postponed proofs can be found in Appendix B.

We will, however, often show how point-free versions, i.e., those hiding quantifiers and individual variables, are derived from a predicate-logic form. These deductions are definitely not an aim of this book. However, they seem necessary for many researchers who are not well trained in expressing themselves in a point-free algebraic manner. These deductions are by no means executed in a strictly formal way. Rather, they are included so as to convince the reader that there is a reason to use the respective point-free construct.

Beyond what has been shown so far, there exist further fascinating areas. One of these is concerned with relational specification. While standard relation algebra formulates what has to be related, here only a region is circumscribed within which the relation envisaged is confined. Although this area has attracted considerable interest from researchers, we omit the presentation of demonic operators used for it.

We continue by mentioning what we cannot present here. With relational grammar applied to natural languages, it has been shown that the translation of relations of time, possession, or modality, for example, can be handled when translating to another natural language. Spatial reasoning has long used relation algebra in order to reason about the relative situatedness of items. This is directed at real-time scanning of TV scenes.

One of the application areas that we present may not be seen as an application in the first place. We also use relations to review parts of standard mathematics, the homomorphism and isomorphism theorems. Additional results may be reported and deeper insights gained when using relations. This area seems particularly promising because many other such reconsiderations may be hoped for. We show possible directions to encourage further research with the Farkas Lemma, topology, projective geometry, etc.

Implication structures study long-range implications, preferably with only a few alternatives; they are helpful in investigating dependency situations. This makes the examples of Sudoku and timetables interesting.

In this chapter we present the third approach to subtree extraction, namely, firstorder (predicate) logic, and its extension, monadic second-order logic (MSO). An advantage of using logic-based queries is that this allows a direct way of expressing retrieval conditions. That is, we do not need to specify the structure of a whole tree (as for patterns in Chapter 5) nor to navigate around the tree (as for path expressions in Chapter 12); we simply need to specify the logical relationships among relevant nodes. Furthermore MSO can express any regular queries, that is, it is at least as powerful as marking tree automata (and thus patterns). However, MSO can express no more than regular queries; indeed, any MSO formula can be translated to a marking tree automaton (Chapter 6). It does mean, however, that we can use efficient on-the-fly algorithms (Chapter 8).

First-order logic

When we consider a logical framework, we usually think of models on which logic formulas are interpreted. In our setting, the models are XML documents; for simplicity, we consider here the binary tree format. Then we can talk about whether a given (binary) tree satisfies a given logic formula.

While in Chapter 5 we defined patterns as an approach to subtree extraction, in this chapter we introduce an alternative approach called path expressions. While patterns use structural constraints for matching subtrees, path expressions use “navigation,” which specifies a sequence of movements on the tree and makes checks on the visited nodes. In practice, path expressions tend to be more concise since they do not require conditions to be specified for the nodes not on the path. In theory, however, path expressions are strictly less expressive (i.e., they cannot express all regular tree languages) unless sufficient extensions are made. In this chapter we first review path expressions used in actual XML processing and then consider a refinement called caterpillar expressions. After this, we study the corresponding automata formalism, called tree-walking automata, and compare their expressiveness with tree automata.

Path expressions

Although there are various styles of path expression, the basic idea is to find a node to which there is a “path” from the “current” node obeying the given path expression. When multiple such nodes are found, usually all are returned.

The main differences between the styles lie in which paths are allowed. A path is, roughly, a sequence consisting of either movements between or tests on nodes. In each movement we specify in which direction to go; we call this axis.