16.1 Knowledge Graphs

16.1.1 Triples

Given a logical representation language, such as the one developed in the previous chapter, and a world to reason about, people designing databases and knowledge bases have to choose which individuals and relations to represent. It may seem that a modeler can just refer to the individuals and relations that exist in the world. However, the world does not determine which individuals there are. How the world is divided into individuals is invented by whomever is modeling the world. The modeler divides the world up into things so that the agent can refer to parts of the world that make sense for the task at hand.

Example 16.1.

It may seem as though “red” is a reasonable property to ascribe to things in the world. You may do this because you want to tell the delivery robot to go and get the red parcel. In the world, there are surfaces absorbing some frequencies and reflecting other frequencies of light. Some user may have decided that, for some application, some particular set of reflectance properties should be called red. Some other modeler might decide on another mapping of the spectrum and use the terms pink, scarlet, ruby, and crimson, and yet another modeler may divide the spectrum into regions that do not correspond to words in any language but are those regions most useful to distinguish different categories of individuals.

Just as modelers choose which individuals to represent, they also choose which relations to use. There are, however, some guiding principles that are useful for choosing relations and individuals. These will be demonstrated through a sequence of examples.

Example 16.2.

Suppose you decide that “red” is an appropriate category for classifying individuals. You could treat the name red as a unary relation and write that parcel a is red:

red(a).

If you represent the color information in this way, then you can easily ask what is red:

ask red(X).

The X returned are the red individuals.

With this representation, it is hard to ask the question “What color is parcel a?” In the syntax of definite clauses, you cannot ask

ask X(a).

because, in languages based on first-order logic, predicate names cannot be variables. In second-order or higher-order logic, this may return any property of a, not just its color.

There are alternative representations that allow you to ask about the color of parcel a. There is nothing in the world that forces you to make red a predicate. You could just as easily say that colors are individuals too, and you could use the constant red to denote the color red. Given that red is a constant, you can use the predicate color where color(Ind,Val) means that physical individual Ind has color Val. “Parcel a is red” can now be written as

color(a,red).

What you have done is reconceive the world: the world now consists of colors as individuals that you can name. There is now a new binary relation color between physical individuals and colors. Under this new representation you can ask “What has color red?” with the query

ask color(X,red).

and ask “What color is block a?” with the query

ask color(a,C).

To make an abstract concept into an entity is to reify it. In the preceding example, the color red is reified.

Example 16.3.

It seems as though there is no disadvantage to the new representation of colors in the previous example. Everything that could be done before can be done now. It is not much more difficult to write color(X,red) than red(X), but you can now ask about the color of things. So the question arises of whether you can do this to every relation, and what do you end up with?

You can do a similar analysis for the color predicate as for the red predicate in Example 16.2. The representation with color as a predicate does not allow you to ask the question “Which property of parcel a has value red?” where the appropriate answer is “color.” Carrying out a similar transformation to that of Example 16.2, you can reify properties such as color as individuals, and invent a relation prop and write “individual a has the color red” as

prop(a,color,red).

This representation allows for all of the queries of this and the previous example. You do not have to do this again, because you can write all relations in terms of the prop relation.

The individual–property–value representation is in terms of a single relation prop where

prop(Ind,Prop,Val)

means that individual Ind has value Val for property Prop. This is also called the triple representation because all of the relations are represented as triples. The first element of the triple is called the subject, the second is the verb, and the third is the object, using the analogy that a triple is a simple three-word sentence.

A triple is sometimes written as a three-word sentence:

subjectverbobject.

meaning the atom

prop(subject,verb,object).

or written in functional notation as

verb(subject,object).

The verb of a triple is a property. The domain of property p is the set of individuals that can appear as the subject of a triple when p is the verb. The range of a property p is the set of values that can appear as the object of a triple that has p as the verb.

An attribute is a property–value pair. For example, an attribute of a parcel may be that its color is red.

There are some predicates that may seem to be too simple for the triple representation:

Example 16.4.

Consider parcel(a), which means that a is a parcel; there are two ways to represent it using triples.

The first is to reify the concept parcel to say that a is a parcel:

prop(a,type,parcel).

where type is a property that relates an individual to a class. The constant parcel denotes the class of all, real or potential, things that are parcels. This triple specifies that the individual a is in the class parcel. The property type is sometimes written as is_a, in which case the triple represents “a is_a parcel”.

The second is to make parcel a property and write “a is a parcel” as

prop(a,parcel,true).

In this representation, parcel is a Boolean property which is true of things that are parcels. The property corresponds to an indicator variable used in CSPs and in machine learning.

A Boolean property is a property whose range is {true, false}, where true and false are constant symbols in the language.

Some predicates may seem to be too complicated for the triple representation:

Example 16.5.

The verb “give” requires three participants: an agent giving, a recipient, and a patient (the item being given). The sentence “Alex gave Chris a book” loses information if only two of the entities involved are specified in a relation. It could be represented by gave(alex,chris,book). It can be represented using triples by inventing a giving act, say ga3545, with the triples:

prop(ga3545,type,giving_act).
prop(ga3545,agent,alex).
prop(ga3545,patient,b342).
prop(ga3545,recipient,chris).
prop(b342,type,book).

Here, ga3545 is a reified entity denoting the action, and b342 is the book given. The agent is the one carrying out the action, the patient is the object the action is carried out on, and the recipient is the one receiving the patient. The properties agent, patient, and recipient are thematic relations or semantic roles used for giving meaning to sentences. The reification allows for other properties of the giving act, such as the date or perhaps the price paid.

Words and numbers that represent reified relations are very common. For example, a booking, a reservation, a marriage, a flight number, a purchase order all denote a relation and have properties such as the participants and a start time.

16.1.2 Individuals and Identifiers

Individuals are denoted by unique identifiers. For example, in a university, a student number is an identifier used to denote a student. The name is not adequate as there might be multiple students with the same name, and some students change their name.

A uniform resource identifier (URI), or its unicode extension, an internationalized resource identifier (IRI), is a unique name that can be used to identify anything. A resource is anything that can be named. An IRI typically has the form of a uniform resource locator (URL), a web address, typically staring with http:// or https://, because URLs are unique. The IRI denotes the entity, not the website. The idea is that if someone uses the IRI, they mean the individual denoted by the IRI. A IRI has meaning because people use it with that meaning. There need not be a formal definition; it just has to be used consistently.

Wikidata (https://www.wikidata.org) is a free, collaborative knowledge graph with around 1.25 billion triples describing 100 million entities (as of 2022).

Example 16.6.

Christine Sinclair is a Canadian association football (soccer) player, who has scored more goals than any other player in international play. In Wikidata [2021], Christine Sinclair is represented using the identifier “http://www.wikidata.org/entity/Q262802”, which we shorten to “Q262802”. Wikidata uses this to disambiguate the footballer from any other person called Christine Sinclair. The identifier “http://www.wikidata.org/entity/Q262802” denotes the footballer, not the web page (which doesn’t play football).

Wikidata uses unique identifiers for properties. For example, it uses the identifier “http://schema.org/name” for the property that gives the name of the subject. We use “name”, but remember that it is an abbreviation for the property defined by schema.org. If you don’t want that meaning, you should use another identifier. The value of a triple with “name” as the property is the pair of a string and a language, such as (“Christine Sinclair”,en).

Wikidata uses “http://www.wikidata.org/prop/direct/P27” for the property “country of citizenship”, where the subject is a person and the object is a country they are a citizen of. Canada is “http://www.wikidata.org/entity/Q16”, so “Christine Sinclair is a citizen of Canada” is represented using the triple

/entity/Q262802   /prop/direct/P27   /entity/Q16

but using the full IRIs (including “http://www.wikidata.org”).

16.1.3 Graphical Representations

You can interpret the prop relation in terms of a knowledge graph, a directed labelled graph, where nodes are entities (and other values such as strings and numbers). The relation

prop(Ind,Prop,Val)

defines an arc with tail Ind and head Val, labelled with Prop. Such a graph is also called a semantic network.

Refer to caption
Figure 16.1: Part of the Wikidata knowledge graph about Christine Sinclair. The English names, not the IRIs, of the properties are shown
Example 16.7.

Figure 16.1 shows part of the Wikidata knowledge graph about Christine Sinclair (Q262802). Wikidata provides over 3400 triples about her, including her name in 47 languages (as of August 2022); her name in English and Korean is shown.

Christine Sinclair is a citizen of Canada. Instead of the Wikidata name, “http://www.wikidata.org/prop/direct/P27”, country_of_citizenship is shown.

She has played 319 games since 2000 for the Canada women’s national soccer team (identifier Q499946), scoring 190 goals. The relationship between her and the team is reified using the identifier Q262802-9c5c267f (the actual identifier is longer than this), connected to her with the property “http://www.wikidata.org/prop/P54” (member of sports team). The property between the reified entity and Q499946 is “http://www.wikidata.org/prop/statement/P54”, also shown as member_of_sports_team.

She has played 161 games for Portland Thorns (identifier Q1446672) since 2013, scoring 65 goals.

Apart from the flexibility outlined earlier, the graphical notation has a number of advantages:

  • It is easy for a human to see the relationships without being required to learn the syntax of a particular logic. The graphical notation helps the builders of knowledge bases to organize their knowledge. There are many tools for creating knowledge graphs where users just draw nodes and arcs (sometimes called knowledge maps or mind maps).

  • A person browsing the knowledge graph can ignore the labels of nodes that just have meaningless names – for example, the name ga3545 in Example 16.5, or Q262802-9c5c267f in Figure 16.1. A representation and visualization can just leave these nodes blank and make up an arbitrary name if they must be mapped to explicit triples.

  • Triples can be stored efficiently in a triple store. In a relational database, the designer needs to specify the keys used to index into the database; given a key, the associated tuples can be found efficiently. A triple store needs eight indexes to be able to find the tuples associated with any combination of given positions. One extreme is where the subject, verb, and object are given and the query is to determine if a particular triple is in the store. At the other extreme, no positions are specified, and the aim is to enumerate the triples. In between these, for example, just the subject and object could be given and the aim is to enumerate the verbs that link them, or just the subject and verb are given and the aim is to enumerate the objects. Eight indexes are required because each of the subject, verb, and object could be given or not. With these indexes, the designer does not need to define keys to access the triples efficiently.