Terms
Purpose
The purpose of a term is to compute pairs that constitute a relation. We use operators to assemble terms from smaller terms, to express in formal language precisely what is meant in the natural language of the business. The smallest term is a single relation.
We noticed that our readers have different backgrounds. They have different preferences about the way we explain the operators in Ampersand. Some prefer an explanation in logic, others in algebra, and still others in set theory. So we decided to explain the operators in many different ways simultaneously, hoping that one of them suits your preference.
Description
A term is a combination of operators and relations. Its meaning is a set of pairs, which is in fact a newly created relation. The word "expression" may be used as a synonym for "term" in the context of Ampersand.
Examples
owner
r;s~
I /\ goalkeeper;goalkeeper~
destination;"Algarve" |- spoken;"Portugese"
Syntax
Every term is built out of relations, which are combined by operators. An term has one of the following 8 syntactic structures
<Term> <BinaryOperator> <Term>
<UnaryOpPre> <Term>
<Term> <UnaryOpPost>
<RelationRef> <type>?
I <type>?
V <type>?
<atom>
( <Term> )
Operators
The operators come in families. We advise novices to study only the rule operators, boolean operators and relational operators. There is a wealth of things you can express with just these operators. The residual operators seem harder to learn and the Kleene operators are not fully implemented yet. You can click the hyperlink to navigate to the semantics of each family.
Family | binary operators | binding power | unary operators | binding power |
---|---|---|---|---|
rules | and | 1 (weakest) | ||
boolean | , , and | 2 | prefix | |
relational | , , and | 4 | postfix | |
residual | , , and | 3 | ||
Kleene | and | postfix |
Brackets
Operators with different binding power may be used in the same term without brackets, because the binding power tells how it is interpreted. For example, means because has a higher binding power than .
Operators with the same binding power must be used unambiguously. For example: means something different than . In such cases Ampersand insists on the use of brackets, so readers without knowledge of the binding powers of the operators can read a term unambiguously.
Repeated uses of an associative operator does not require brackets. So is allowed because is associative.
Notation on the keyboard
When coding in Ampersand, these operators are typed with characters on the keyboard. The following table shows the operators in math and their equivalent in code:
operator name | code | math | remark |
---|---|---|---|
equivalence (equal) | = | use only in a rule | |
inclusion | \|- | use only in a rule | |
intersect | /\ | associative, commutative, idempotent | |
union | \/ | associative, commutative, idempotent | |
difference (minus) | - | ||
complement (of some relation r) | - | in code: Prefix; in math: Overline | |
compose | ; | associative | |
converse (flip) | ~ | postfix | |
left residual | / | ||
right residual | \ | ||
diamond | <> | ||
relational product | ! | associative | |
cartesian product | # | deprecated | |
reflexive transitive closure | * | ||
transitive closure | + |
Semantics
We present the semantics of terms in 5 different (but equivalent) ways: one explanation in terms of logic, one in set theory, one in terms of axioms (algebraically), one in natural language, and one visual explanation. These ways are equivalent, so you can interpret a term in any of the presented ways. Any way will do; take your pick!
Category | Logic | Sets | Axioms | Natural Language | Visual |
---|---|---|---|---|---|
primitive terms | logic | set theory | axioms | natural language | visual |
boolean | logic | set theory | axioms | natural language | visual |
relational | logic | set theory | axioms | natural language | visual |
residual | logic | set theory | natural language | visual | |
products | logic | set theory | axioms | natural language | visual |
(the pages without hyperlinks are yet to be made).
Semantics in logic
Primitive terms in logic
Relations
When a relation is used in a term, it stands for all pairs it contains at the moment it is evaluated. Those pairs (also referred to as the contents or population of the relation) can change over time as users add or delete pairs from it.
When a relation is used in a term, we can just use its name if that is unambiguous. For instance the name owner
refers to RELATION owner[Person*Building]
if that is the only relation the ampersand-compiler can link it to. In some cases, however the name alone is ambiguous. For example if there are two relations with the same name and different signatures. In such cases Ampersand will try to infer the type from the context. That however does not always succeed. In such cases, Ampersand generates an error message that asks you to remove the ambiguity by adding the correct type.
If a pair is an element of a relation , we write . Alternatively we may write , since we know that is a set.
Identity
For every concept , the term exists. It refers to the identity relation. It means that for every and we have:
The type of is . In Ampersand code you write I[C]
.
Complete relation
For every pair of concepts and the term refers to the complete relation. For every and we have:
The type of is . In Ampersand code you write V[A*B]
.
Boolean operators in logic
The notation means that the pair (a,b) is in relation . This page defines when pair (a,b) is in relation (the intersection of and ), (the union of and ), (the difference of and ).
- intersection : . In other words: if the pair is both in relation and , then it is in the intersection of and .
- union : . In words: if the pair is in the relation or in , then it is in the union of and .
- difference : . In other words, the term contains all pairs from that are not in .
The complement (or negation) of a relation is defined by means of the difference operator:
- complement : If is defined as , then is the set of all tuples in (the Cartesian product) that are not contained in . So
Note that the complement is defined in terms of and . So, two relations with an identical population yet a different type may have different complements.
How to type boolean operators in your script
This page shows how you can type boolean (and other) operators in your Ampersand script.
Relational operators in logic
Purpose of relational operators
To say things such as "the name of the owner", we want to string together multiple relations (viz. name
and owner
). Relational operators allow us to make such statements.
Converse
A relation can be altered by swapping the elements of every pair in the relation. Mathematically, is different from . This operation is called the converse operator. It produces a new relation from an existing one. It is denoted by writing $ (pronounced 'wok' or ’flip’) after the relation name. This is how converse is defined:
If has type, then has type .
Composition
The composition operator is denoted by a semicolon between two terms. It is pronounced as 'composed with'. Let us take a look at composed with . Let and be two relations, with the target of r being the same as the source of s. Then the composition of and is defined by:
If has typeand has type, then has type .
How to type boolean operators in your script
This page shows how you can type boolean (and other) operators in your Ampersand script.
Residual operators in logic
Residual operators are used when "material implication" is involved.
right residual : . In other words: is in the right residual of and means that for every , pair is in relation implies that pair is in .
left residual : . In words: is in the left residual of and
means that for every pair is in relation implies that pair is in .
diamond: . In words: For every , both and are true or both are false.
How to type boolean operators in your script
This page shows how you can type boolean (and other) operators in your Ampersand script.
Semantics in natural language
Primitive terms in natural language
Relations
When a relation is used in a term, it stands for a set of facts that are assumed true on the current time in the current context. Those facts (also referred to as the contents or the population of the relation) can change over time as users add or delete facts from it.
When a relation is used in a term, we can simply use its name if that is unambiguous. For instance the name owner
refers to RELATION owner[Person*Building]
if that is the only relation the ampersand-compiler can link it to. In some cases, however the name alone is ambiguous. For example if there are two relations with the same name and different signatures. In such cases Ampersand will try to infer the type from the context. That however does not always succeed. In such cases, Ampersand generates an error message that asks you to remove the ambiguity by adding the correct type.
If a pair is an element of a relation , we write to denote the fact. It means that we consider to be true (within the current context).
Identity
Every atom in a concept identifies itself. If for example concept "Person" contains atoms {"Ann", "Bob", "Cecil"}, "Ann" identifies "Ann", "Bob" identifies "Bob", and "Cecil" identifies "Cecil". This makes "Ann" and "Bob" different atoms (unequal).
Boolean operators in natural language
Purpose of boolean operators
To say things such as pair ("peter","macbook")
is either in relation ownsa
or wantsa
, requires us to use boolean operators , , and .
Meaning
Let us explain the meaning of relational operators , , and by means of examples.
Assume we have a relation, ownsa[Person*LaptopType]
, which contains the persons who own a particular type of laptop. A fact "peter" ownsa "macbook"
means that Peter owns a MacBook.
Also assume another relation wantsa[Person*LaptopType]
, which contains the persons who want a particular type of laptop. A fact "peter" wantsa "macbook"
means that Peter wants a MacBook.
Union
The sentence: "Peter owns a MacBook or Peter wants a MacBook." is represented as\
"peter"
(ownsa
wantsa
) "macbook"
.
Intersection
The sentence: "Peter owns a MacBook and Peter wants a MacBook." is represented as\
"peter"
(label
colour
) "macbook"
.
Difference
The sentence: "Peter owns a MacBook and Peter does not want a MacBook." is represented as\
"peter"
(label
colour
) "macbook"
.
Natural language templates
There is a pattern to this. A computer can generate a literal translation from the formula to natural language. However, that translation looks clumsy, verbose and elaborate. It is up to you to turn that in normal language. The systematic translation is given in the following table:
Formally | Natural language template |
---|---|
a r b or a s b . | |
a r b and a s b . | |
a r b and nota s b . |
Relational operators in natural language
Purpose of relational operators
To say things such as "the name of the owner", we want to string together multiple relations (viz. name
and owner
). Relational operators allow us to make such statements.
Meaning
The meaning of relational operators and is best explained by means of examples.
Assume we have a relation, label[Contract*Colour]
, which contains the colour of labels on contracts. A fact "1834" label "blue"
means that contract 1834 has a blue label.
Also assume another relation stored[Contract*Location]
, which gives the location where a contract is stored. Fact "1834" store "cabinet 42"
means that contract 1834 is stored in cabinet 42.
Converse
A relation can be altered by swapping the elements of every pair in the relation. Mathematically, is a different from . In natural language, however, the meaning does not change. So if"1834" label "blue"
means that contract 1834 has a blue label, "blue" label~ "1834"
also means that contract 1834 has a blue label.
- The sentence: "All contracts with a blue label are stored in cabinet 42." is represented as
"blue" (label\stored) "cabinet 42"
. Literally it says: For every contract, if it has a blue label, then it is stored in cabinet 42.
Composition
The sentence "A contract with a blue label is stored in cabinet 42." can be represented as "blue" (label~;stored) "cabinet 42"
. Literally it says: There is a contract that has a blue label and is stored in cabinet 42.
Natural language templates
There is a pattern to this. A computer can generate a literal translation from the formula to natural language. However, that translation looks clumsy, verbose and elaborate. It is up to you to turn that in normal language. The systematic translation is given in the following table:
Formally | Natural language template |
---|---|
a (r;s) b | There exists an x : if a r x then x s b . |
b r~ a | a r b . |
The natural language translation for b r~ a
is the same as language translation for a r b
.
Residual operators in natural language
The meaning of residual operators , , and is best explained by means of examples.
Assume we have a relation, label[Contract*Colour]
, which contains the colour of labels on contracts. A fact "1834" label "blue"
means that contract 1834 has a blue label.
Also assume another relation stored[Contract*Location]
, which gives the location where a contract is stored. Fact "1834" store "cabinet 42"
means that contract 1834 is stored in cabinet 42.
- The sentence: "All contracts with a blue label are stored in cabinet 42." is represented as
"blue" (label\stored) "cabinet 42"
. Literally it says: For every contract, if it has a blue label, then it is stored in cabinet 42. - The sentence: "All contracts that are stored in cabinet 42 have a blue label." is represented as
"blue" (label~/stored~) "cabinet 42"
. Literally it says: For every contract, if it is stored in cabinet 42, then it has a blue label. - The sentence: "All blue labeled contracts and no others are stored in cabinet 42." is represented as
"blue" (label~<>stored) "cabinet 42"
. Literally it says: For every contract, if it has a blue label, then it is stored in cabinet 42 and if it is stored in cabinet 42, then it has a blue label.
Natural language templates
There is a pattern to this. A computer can generate a literal translation from the formula to natural language. However, that translation looks clumsy, verbose and elaborate. It is up to you to turn that in normal language. The systematic translation is given in the following table:
Formally | Natural language template |
---|---|
a (r\s) b | For every x : if x r a then x s b . |
a (r/s) b | For every x : if b s x then a r x . |
a (r<>s) b | For every x : if a r x then x s b and if x s b then a r x . |
Semantics in set theory
Primitive terms in set theory
Relations
When a relation is used in a term, it stands for the set of pairs it contains at the moment it is evaluated. That set (also referred to as the contents of the relation) can change over time as users add or delete pairs from it.
When a relation is used in a term, we can simply use its name if that is unambiguous. For instance the name owner
refers to RELATION owner[Person*Building]
if that is the only relation the ampersand-compiler can link it to. In some cases, however the name alone is ambiguous. For example if there are two relations with the same name and different signatures. In such cases Ampersand will try to infer the type from the context. That however does not always succeed. In such cases, Ampersand generates an error message that asks you to remove the ambiguity by adding the correct type.
If a pair is an element of a relation , we write . Alternatively we may write .
Identity
For every concept , the term represents the identity relation. It is defined by:
The type of is . In Ampersand code you write I[C]
.
Complete relation
For every pair of concepts and the term represents the complete relation. It is defined by:
The type of is . In Ampersand code you write V[A*B]
.
Boolean operators in set theory
A relation is by definition a subset of the Cartesian Product of the source and target sets. So, if two different relations r and s are defined on the same source A and target B, then the ordinary set operators can be applied to produce a new relation.
- intersection : is the set that contains the elements that are contained in relation as well as in , or
- union : is the set that contains all elements that are contained either in relation or in , or
- difference : is the set that contains the elements of relation that are not contained in , or
The complement (or negation) of a relation is defined by means of the difference operator:
- complement : If is defined as , then is the set of all tuples in (the Cartesian product) that are not contained in . So
Note that the complement is defined in terms of and . So, two relations with the identical population yet a different type may have different complements.
How to type boolean operators in your script
This page shows how you can write these things in your Ampersand script.
Relational operators in set theory
Purpose of relational operators
To say things such as "the name of the owner", we want to string together multiple relations (viz. name
and owner
). Relational operators allow us to make such statements.
Converse
A relation that contains pairs of the form can be altered by swapping the elements of every pair in the relation. Mathematically, is different from . This operation is called the converse operator. It produces a new relation from an existing one. It is denoted by writing (pronounced 'wok' or ’flip’) after the relation name. This is how converse is defined:
If has type , then has type .
Composition
The composition operator is denoted by a semicolon ; between two terms. It is pronounced as 'composed with', in this case: composed with .
The composition operation is defined as follows: Let and be two relations, with the target of r being the same as the source of s. Then the composition of and , is a relation with signature
Semantics in relational algebra
Semantics of primitive terms in relational algebra
This chapter discusses the boolean operators and the relational operators in the following sections.
Boolean operators in algebra
The boolean operators of Ampersand behave as one would expect in any boolean algebra. Union () and intersection () are both idempotent, commutative, and associative operators. In Ampersand we use a binary difference operator over with the usual semantics: . The (more customary) complement operator is a partial function, because Ampersand supports heterogeneous relation algebra.
Union
The operator (union) satisfies the following axioms:
- (commutativity of )
- (associativity of )
- (idempotence of )
Difference
The difference is the smallest relation that satisfies . Smallest means: If there is a for which , this implies that .
Intersection
The intersection is defined as:
Complement
The complement operator is defined as . The type comes from the term(s) in which is embedded. If that type does not exist or if it is ambiguous, Ampersand will refuse to compile with an appropriate error message.
How to type boolean operators in your script
This page shows how you can write these things in your Ampersand script.
Relational operators in algebra
Purpose of relational operators
To say things such as "the name of the owner", we want to string together multiple relations (viz. name
and owner
). Relational operators allow us to make such statements.
There are two relational operators: the converse () and the composition (semicolon ). This page discusses the most important laws about these operators.
Converse
There are two things you should know about the converse operator. The first is that the converse of the converse gives you the relation itself, whatever that relation may be:
The second thing you should know is that arguments switch places if the converse is brought outside (or inside) brackets
Composition
The composition operator is denoted by a semicolon (;) between two terms. It is pronounced as 'composed with', in this case: composed with .
Composition is associative, which means:
The meaning stays the same, no matter how you place the brackets. So Ampersand lets you omit brackets entirely. You may write instead of or .
Composition has a left and a right identity. Let be a relation, then
How to type relational operators in your script
This page shows how you can write these things in your Ampersand script.
Semantics visualized
For a visual presentation of the semantics of terms, we use Venn-diagrams.
Boolean operators visualized
Consider two relations: authorized[Account*Person]
and beneficiary[Account*Person]
. The first relation tells which persons are authorized to which accounts. The diagram shows this as red dashed lines. The second relation tells which persons stand to benefit from which accounts.. It is depicted by dotted blue lines in the diagram.
This diagram gives an example population of the relations authorized[Account*Person]
and beneficiary[Account*Person]
. Bob is authorized for account DE9382991 and Ann is authorized for account RS746620. Carl stands to benefit from account NL19RABO03992844 and Ann stands to benefit from account RS746620. Formally, we say:
statements |
---|
"NL19RABO03992844" beneficiary "Carl" |
"DE9382991" authorized "Bob" |
"RS746620" authorized "Ann" |
"RS746620" beneficiary "Ann" |
By combining the relations authorized
and beneficiary
, we can derive the following true statements.
statement | natural language |
---|---|
"RS746620" (authorized/\beneficiary) "Ann" | Ann is authorized for and stands to benefit from for account RS746620. |
"NL19RABO03992844" (authorized\/beneficiary) "Carl" | Carl is authorized for or stands to benefit from account NL19RABO03992844. |
"RS746620" (authorized\/beneficiary) "Ann" | Ann is authorized for or stands to benefit from account RS746620. |
"DE9382991" (authorized\/beneficiary) "Bob" | Bob is authorized for or stands to benefit from account DE9382991. |
A different way to state the same is:
authorized/\beneficiary = {("RS746620", "Ann")} |
|
Relational operators visualized
Consider two relations: traveler[Trip*Person]
and dest[Trip*Destination]
. The first relation tells which persons have traveled on which trip. The diagram shows this as red dashed lines. The second relation links trips to destinations. It is depicted by dotted blue lines in the diagram.
Each pair (fact) in the diagram can be written as a fact in two ways, using the converse operator:
Fact | Fact |
---|---|
"Peter" traveler~ "LBD-199" | "LBD-199" traveler "Peter" |
"Peter" traveler~ "TSS-730" | "TSS-730" traveler "Peter" |
"TSS-730" dest "Rome" | "Rome" dest~ "TSS-730" |
"TSS-730" dest "Paris" | "Paris" dest~ "TSS-730" |
"QRA-492" dest "Paris" | "Paris" dest~ "QRA-492" |
From the diagram, we assume that each pair represents a true statement (i.e. a fact). The statements are given both formally and in natural language. The elaborate version is a literate translation of the semantics in logic. The ordinary version tells the same in a more human sounding manner.
Formal statement | Elaborate natural language | Ordinary natural language |
---|---|---|
"Peter" (traveler~;dest) "Rome" | There is a trip that Peter has made, which has Rome as destination. | Peter has made a trip to Rome. |
"Peter" (traveler~;dest) "Paris" | There is a trip that Peter has made, which has Paris as destination. | Peter has made a trip to Paris |
Residual operators visualized
Consider two relations: traveler[Trip*Person]
and dest[Trip*Destination]
. The first relation tells which persons have traveled on which trip. The diagram shows this as red dashed lines. The second relation links trips to destinations. It is depicted by dotted blue lines in the diagram.
From this diagram, we can tell which statements are true (i.e. facts). The statements are given both formally and in natural language. The elaborate version is a literate translation of the semantics in logic. The ordinary version tells the same in a more human sounding manner.
Formal statement | Elaborate natural language | Ordinary natural language |
---|---|---|
"Peter" (traveler~/dest~) "Rome" | For each trip, if it has destination Rome, then it has been made by Peter. | Every trip to Rome has been made by Peter. |
The following statements do NOT follow from the population shown in the diagram:
Formal statement | Elaborate natural language | Ordinary natural language |
---|---|---|
"Peter" (traveler\dest) "Rome" | For each trip, if Peter has made the trip then its destination is Rome. | Every trip that Peter made has Rome as destination. |
"Peter" (traveler\dest) "Paris" | For each trip, if Peter has made the trip then its destination is Paris. | Every trip that Peter made has Paris as destination. |
"Peter" (traveler~/dest~) "Paris" | For each trip, if Paris is the destination then Peter has made that trip. | Every trip to Paris has been made by Peter. |