In this chapter we deal with the way in which RDF descriptions are stored, processed and queried as well as the applications and languages involved in the process.

In Section 3.1 we describe how to make RDF meta-information on the web available for search engines. Next, in Section 3.2, we give an overview of development tools which can be used to parse and manage RDF-based sources. In Section 3.3 we describe RDF query languages and show why XML query languages are not suitable for this purpose. Subsequently, in Section 3.4, we discuss the possible reasoning tasks involved in answering RDF queries. Finally, in Section 3.5, we describe problems which arise in the course of optimising RDF queries and outline possible solutions.

RDF descriptions on the web

The RDF language is a generic framework that helps to associate meta-information with resources in a uniform way. RDF is by no means limited to the web, because anything that is identified by a URI can be used in RDF statements. However, as we saw in the previous chapter, practically anything can have a URI: a person, a rucksack, a house etc. This allows us to use RDF in environments other than the web, for example, traditional databases, information integration and other knowledge-intensive systems.

Sets and functions are ubiquitous in mathematics. You might have the impression that they are most strongly connected with the pure end of the subject, but this is an illusion: think of probability density functions in statistics, data sets in experimental science, planetary motion in astronomy, or flow in fluid dynamics.

Category theory is often used to shed light on common constructions and patterns in mathematics. If we hope to do this in an advanced context, we must begin by settling the basic notions of set and function. That is the purpose of the first section of this chapter.

The definition of category mentions a ‘collection’ of objects and ‘collections’ of maps. We will see in the second section that some collections are too big to be sets, which leads to a distinction between ‘small’ and ‘large’ collections. This distinction will be needed later, most prominently for the adjoint functor theorems (Chapter 6).

The final section takes a historical look at set theory. It also explains why the approach to sets taken in this chapter is more relevant to most of mathematics than the traditional approach is. None of this section is logically necessary for anything that follows, but it may provide useful perspective.

I do not assume that you have encountered axiomatic set theory of any kind.

Limits, and the dual concept, colimits, provide our third approach to the idea of universal property.

Adjointness is about the relationships between categories. Representability is a property of set-valued functors. Limits are about what goes on inside a category.

The concept of limit unifies many familiar constructions in mathematics. Whenever you meet a method for taking some objects and maps in a category and constructing a new object out of them, there is a good chance that you are looking at either a limit or a colimit. For instance, in group theory, we can take a homomorphism between two groups and form its kernel, which is a new group. This construction is an example of a limit in the category of groups. Or, we might take two natural numbers and form their lowest common multiple. This is an example of a colimit in the poset of natural numbers, ordered by divisibility.

Limits: definition and examples

The definition of limit is very general. We build up to it by first examining some particularly useful types of limit: products, equalizers, and pullbacks.

Products

Let X and Y be sets. The familiar cartesian product X χ Y is characterized by the property that an element of X χ Y is an element of X together with an element of Y.

We have approached the idea of universal property from three different angles, producing three different formalisms: adjointness, representability, and limits. In this final chapter, we work out the connections between them.

In principle, anything that can be described in one of the three formalisms can also be described in the others. The situation is similar to that of cartesian and polar coordinates: anything that can be done in polar coordinates can in principle be done in cartesian coordinates, and vice versa, but some things are more gracefully done in one system than the other.

In comparing the three approaches, we will discover many of the fundamental results of category theory. Here are some highlights.

1. • Limits and colimits in functor categories work in the simplest possible way.

2. • The embedding of a category A into its presheaf category [Aop, Set] preserves limits (but not colimits).

3. • The representables are the prime numbers of presheaves: every presheaf can be expressed canonically as a colimit of representables.

4. • A functor with a left adjoint preserves limits. Under suitable hypotheses, the converse holds too.

5. • Categories of presheaves [Aop, Set] behave very much like the category of sets, the beginning of an incredible story that brings together the subjects of logic and geometry.

A category is a system of related objects. The objects do not live in isolation: there is some notion of map between objects, binding them together.

Typical examples of what ‘object’ might mean are ‘group’ and ‘topological space’, and typical examples of what ‘map’ might mean are ‘homomorphism’ and ‘continuous map’, respectively. We will see many examples, and we will also learn that some categories have a very different flavour from the two just mentioned. In fact, the ‘maps’ of category theory need not be anything like maps in the sense that you are most likely to be familiar with.

Categories are themselves mathematical objects, and with that in mind, it is unsurprising that there is a good notion of ‘map between categories’. Such maps are called functors. More surprising, perhaps, is the existence of a third level: we can talk about maps between functors, which are called natural transformations. These, then, are maps between maps between categories.

In fact, it was the desire to formalize the notion of natural transformation that led to the birth of category theory. By the early 1940s, researchers in algebraic topology had started to use the phrase ‘natural transformation’, but only in an informal way. Two mathematicians, Samuel Eilenberg and Saunders Mac Lane, saw that a precise definition was needed. But before they could define natural transformation, they had to define functor; and before they could define functor, they had to define category. And so the subject was born.