foundations of computational agents
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.
It may seem as though “” 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 . Some other modeler might decide on another mapping of the spectrum and use the terms , , , and , 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.
Suppose you decide that “red” is an appropriate category for classifying individuals. You could treat the name as a unary relation and write that parcel is red:
If you represent the color information in this way, then you can easily ask what is red:
The returned are the red individuals.
With this representation, it is hard to ask the question “What color is parcel ?” In the syntax of definite clauses, you cannot ask
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 , not just its color.
There are alternative representations that allow you to ask about the color of parcel . There is nothing in the world that forces you to make a predicate. You could just as easily say that colors are individuals too, and you could use the constant to denote the color red. Given that is a constant, you can use the predicate where means that physical individual has color . “Parcel is red” can now be written as
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 between physical individuals and colors. Under this new representation you can ask “What has color red?” with the query
and ask “What color is block ?” with the query
To make an abstract concept into an entity is to reify it. In the preceding example, the color is reified.
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 than , 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 predicate as for the predicate in Example 16.2. The representation with as a predicate does not allow you to ask the question “Which property of parcel has value ?” where the appropriate answer is “color.” Carrying out a similar transformation to that of Example 16.2, you can reify properties such as as individuals, and invent a relation and write “individual has the ” as
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 relation.
The individual–property–value representation is in terms of a single relation where
means that individual has value for property . 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:
meaning the atom
or written in functional notation as
The verb of a triple is a property. The domain of property is the set of individuals that can appear as the subject of a triple when is the verb. The range of a property is the set of values that can appear as the object of a triple that has 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:
Consider , which means that is a parcel; there are two ways to represent it using triples.
The first is to reify the concept parcel to say that is a parcel:
where is a property that relates an individual to a class. The constant denotes the class of all, real or potential, things that are parcels. This triple specifies that the individual is in the class . The property 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 “ is a parcel” as
In this representation, 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 , , where and are constant symbols in the language.
Some predicates may seem to be too complicated for the triple representation:
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 . It can be represented using triples by inventing a giving act, say , with the triples:
Here, is a reified entity denoting the action, and is the book given. The is the one carrying out the action, the is the object the action is carried out on, and the is the one receiving the patient. The properties , , and 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.
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).
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”).
You can interpret the 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
defines an arc with tail and head , labelled with . Such a graph is also called a semantic network.
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”, 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 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.