Glossary

A B C D E F I K L M P Q R S T U V W

A

aborted transaction

A transaction whose execution was prematurely terminated by the user or because of an error (e.g., violation of a constraint). All changes in the database performed by an aborted transaction will be null and void, i.e., the transaction will not have a permanent effect.

application expression

An application expression applies a functional predicate to a series of zero or more arguments. For example, ssn-number["John", "Smith"].

See Section 9.4, “Function applications”.

argument

This term is used in two meanings, which are slightly different, though related.

  • A predicate of arity n is said to have n arguments. Each of them has a position k, where 0 < k <= n, and an associated type. Every tuple that is contained in the predicate must have n fields, and the type of the data item in its k'th field must be the type of the predicate's k'th argument.
  • An atom that refers to some predicate p of arity n must have n arguments, which are LogiQL expressions. The type of each of the atom's k'th argument must be the type of p's k'th argument.

For instance, the functional predicate age may be declared to have two arguments, a string and an integer:

age[name] = years ->  string(name), int(years).  

The atom age["Mary"] = 7 has two arguments: the first is the string "Mary", and the second is the integer 7. The same can be said of its alternative form, age("Mary", 7).

arity

The number of arguments of a predicate, or the number of fields in a tuple. Must be an integer greater than or equal to zero.

The arity of a predicate is the same as the arity of tuples contained in that predicate.

atom

An elementary logical formula, which takes the form of a predicate name followed by a list of arguments, in parentheses and separated by commas (but see the section called “Multi-valued functional predicates” for an exception). For example, age("Mary", y) is an atom.

An atom is said to refer to the named predicate (age in our example).

An atom that refers to a functional predicate can be written in special functional syntax, e.g., age["Mary"] = y. Applications of some built-in operations with infix syntax are also considered to be atoms. For example, x > y is an atom, as is x = y + z; in the latter, the predicate is =, and there are two arguments: x and y + z.

Logically, an atom is just an elementary formula, which is true or false for any given instantiations of the variables that occur in it. What this really means in LogiQL is somewhat complicated and depends on context: see Section 10.1, “Atoms”.

B

binding

A very general term, often used to describe the situation when something (A) is associated with something else (B), especially when the association consists in A becoming a name or a reference for B: we then say that A is bound to B. The term is also used to describe situations in which the range or the scope of something (often a variable) is somehow restricted: a typical example is a variable in a logical formula being bound by a quantifier.

In the context of LogiQL "binding" is sometimes used instead of "instantiation". In this manual we reserve the term to talk about variables being "bound" or "unbound". A "bound" variable occurs in a context in which it is able to "receive" instantations. See the section called “Bound variables and their instantiations” for a more thorough discussion.

block

A wrapper for logic submitted to the system: the contents (declarations, rules etc.) are inserted into the system together, and can be removed only together. There are no rules about how to divide logic into blocks, except that some predicates can be made local to a block, so all the logic that refers to those predicates must be in the same block.

See Section 19.1.3, “Blocks”.

branch

A version of a database. The cost of branching and modifying a database is essentially proportional to the size of the modifications, rather than the size of the database.

See Chapter 41, Database Branching.

branch alias

A variable that can be bound to the name of a branch. Used in referring to a predicate in another branch. See the section called “Branch aliases”.

C

commit

A transaction that has successfully run to completion without any errors can be ended by a commit operation. This means that all the changes made by the transaction to database-lifetime data and logic will become permanent (in the sense that they will remain in the database after the transaction has terminated).

constraint

A declaration that ensures the contents of the database satisfy certain logical conditions. The system automatically ensures (either during compile-time analysis or via runtime checking) that this is indeed the case, i.e., that the constraint is not violated.

For example, the following constraint ensures that the age of a person "makes sense":

age[_] = years -> 0 <= years < 150. 

In LogiQL, the declaration of a predicate has the form of a constraint.

constructor predicate

A constructor predicate is a one-to-one function (injection) that maps a multi-dimensional key to an entity.

See Section 8.3.1, “Constructor Predicates”.

contents of a predicate

The set of tuples contained in a predicate.

D

database lifetime

Logic and data that persist for longer than a single transaction are said to have database lifetime.

See Also lifetime.

declaration

In LogiQL, a predicate can (and sometimes must) be declared as having a name and a particular number of arguments, each with a particular type. In some contexts the declaration of a predicate need not be given explicitly, but can be derived automatically from atoms that refer to the predicate: we then say the declaration is implicit.

A predicate can also have some additional important properties, in particular it may be a functional predicate. These are also (explicitly or implicitly) declared.

The most convenient way to declare a functional predicate is to use the special functional syntax of LogiQL. For example, the following declares two predicates, the second of which is functional:

square_root(number, positive, negative) -> float(number),
                                           float(positive), float(negative).
age[name] = years -> string(name), int(years). 

The declaration of a predicate takes the form of a constraint. This is justified by the fact that its purpose is to impose a restriction on the tuples in the predicate: they must have a certain length, each of their fields must have a certain type, and the contents of functional predicates must satisfy certain restrictions.

Additional properties of a predicate can be declared by adding the predicate's name to certain predefined system predicates. For example, to make p a pulse predicate we can follow its declaration with one of the following facts:

lang:pulse(`p).
lang:isPulse[`p] = true. 

See Section 8.1, “Predicate Declaration” and the following sections.

deletion

The act of removing a tuple from a predicate. We sometimes also say that the tuple is erased.

See Also insertion.

delta

The word "delta" is sometimes used for one of the prefixes to a delta atom, i.e., +, - or ^. The word is also informally used for other things that have to do with differences between two versions of something, e.g., it may be used to refer to the contents of a delta predicate.

delta atom

A delta atom is an atom that is prefixed with +, - or ^. Roughly speaking, these prefixes refer, respectively, to insertion, deletion or upsert operations.

See Also delta logic.

delta logic

Logic that specifies or refers to changes in EDB predicates.

See Section 19.2, “Delta logic”.

delta predicate

An auxiliary predicate that contains information about requests for insertions and deletions.

See Section 19.2.2, “Delta rules”.

See Also delta logic.

delta rule

Similar to a rule, but contains delta atoms in the head.

See Section 19.2.2, “Delta rules”.

See Also delta logic.

derive

A rule is said to derive into the predicates that occur in its head. This is because it can cause addition of tuples to (or removal of tuples from) those predicates when modifications are made to the the predicates that are referred to by the atoms in its body.

The term "derive" is also used in a more conventional sense: for example, the signature of a predicate can sometimes be automatically derived (i.e., inferred) by the compiler.

E

EDB

An abbreviation for "Extensional DataBase". An EDB predicate is one whose contents are manipulated "explicitly" (via delta logic), rather than maintained wholly automatically through rules. An EDB predicate must be materialized.

See Section 19.2, “Delta logic”.

entity

In the context of LogiQL, an entity is a member of an entity predicate. An entity is anonymous, i.e., it is impossible to refer to it directly by its name. Two entities can be compared only for equality.

Entities can be created by means of reference-mode predicates or constructor predicates. Both give the programmer a means to indirectly refer to an entity.

entity predicate

An entity predicate is essentially an abstract data type. The type of its contents (the entities) is different from all the other types in the database schema, except for two cases:

  • if an entity predicate q is declared as a subtype of another entity predicate p (q's supertype), then the set of entities in q is a subset of the set of entities in p;
  • if entity predicates q and r are both subtypes of the same entity predicate p, then they may share values.

An entity predicate is called top-level if it is not a subtype of another entity predicate.

See Section 8.3, “Entity Predicates”

See Also entity.

entity type

Another term for an entity predicate.

erasure

Sometimes used as a synonym for deletion.

event logic

A term used for pulse predicates and related logic.

See Section 19.3, “Events”.

execution graph

An auxiliary data structure internal to the LogicBlox database runtime system (but in some cases stored in the database). Encodes primarily dependencies between rules: the information is used to make maintenance efficient.

See Section 19.4.1, “Maintenance”.

F

fact

A declaration that a particular tuple belongs to a particular IDB predicate. For example, age("Mary", 7). is a declaration that the tuple ("Mary", 7) is a member of predicate age.

If age is a functional predicate in which the first argument is the key, a fact such as age("Mary", 7). can also be written as age["Mary"] = 7.

A fact can be considered as a degenerate rule: the rule's body is trivially true, so we write just the head.

The word "fact" is sometimes used interchangeably with "tuple", but the two are not the same. A fact is a syntactic artefact, and is considered to be a part of "logic". A tuple is a data item, and is most often not associated with a fact, but generated by a rule or imported through CVS/TDX.

There is, of course, a clear correspondence between the two: any set of tuples can be represented as a set of facts. Indeed, the word "predicate" is used to describe either a part of a database (a set of tuples), or a logical entity (a set of facts). To maintain the necessary distinction, it is useful to say that a predicate contains tuples or consists of facts.

See Section 10.1.1, “Atoms as facts”.

failure
logical failure
FDV

An abbreviation for functional dependency violation.

firing

A rule is said to "fire" if there are instantiations of its variables that make its body true.

fixpoint

A stable state of the database, in which the contents of all predicates are consistent with the contents of the other predicates and with all the active rules.

See Also maintenance.

frame rule

A special form of rule, generated internally by the system. Frame rules are created to ensure that direct changes to EDB predicates (via delta atoms) will have the desired effect during maintenance.

See Section 19.4.6, “Frame rules”.

functional dependency violation

A violation of the principal (implicit) constraint of a functional predicate: an attempt to insert a tuple with a particular key when a different tuple with the same key is already a member of the same functional predicate.

functional predicate

A predicate that has been declared to satisfy the following:

  • a non-empty initial sequence of its arguments is designated as the key;
  • the predicate contains at most one tuple with any particular key.

For example, the predicate age may be declared as follows:

age[name] = years -> string(age), int(years). 

This means that the predicate age consists of tuples like ("Mary", 7), ("John", 8) etc., and the first field of each tuple is the key. It also means that the predicate cannot contain two tuples with the same key, e.g., both ("Mary", 7) and ("Mary", 8). An attempt to insert one of these tuples when the other is already present is a functional dependency violation.

See Section 8.2, “Functional Predicates”. Note that it is possible to have a functional predicate with a value that consists of several arguments, though the use of such functional predicates is discouraged (see the section called “Multi-valued functional predicates”).

I

IDB

An abbreviation for "Intensional DataBase". The contents of an IDB predicate are determined by a set of rules (namely those that derive into this predicate). Since the contents can always be reconstructed on demand, an IDB predicate need not necessarily be materialized. IDB predicates can be regarded as similar to the "views" that can be defined in more conventional database systems.

See Section 8.8, “Derivation Types” for information about how to avoid materialization.

insertion

The act of adding a tuple to a predicate.

See Also deletion.

installed logic

A synonym for database-lifetime logic. This use of the term is discouraged, because the word "install" can refer to several different actions: one can install inactive blocks, and transaction-lifetime or query-lifetime logic is temporarily installed during the execution of a transaction.

instance

A general term used to describe a particular/concrete embodiment of a general pattern. For instance:

  • "for instance" is often used instead of "for example";
  • a workspace is a particular instance of a LogicBlox database;
  • a particular instance of a rule is obtained by substituting some particular instantiation for each of its variablevariables.

In the context of LogiQL we do not ascribe any special meaning to this term. We list it here in order to help avoid confusion between "instance" and "instantiation".

instantiation

A LogiQL variable represents a value obtained from the contents of a predicate and/or by evaluating an expression. That value is called the variable's instantiation (we can also say that the variable became instantiated to this value).

The term is meant to stress the fact that an instantiated variable cannot be distinguished from its instantiation: one can think of the action of instantiating variable v with some value e as equivalent to textually replacing v with e in the rule in which it appears.

While technically an instantiation is a single value, it is often useful to think of a variable as being instantiated to a set of values, with the additional proviso that this set is not independent of the instantiations of other variables in the the same rule. This way of thinking is in fact closer to the way in which LogiQL rules are actually evaluated. See the section called “Bound variables and their instantiations” and Section 10.1.3, “Atoms in bodies of rules” for a more detailed discussion.

K

key

In a functional predicate, the key is the initial sequence of arguments that uniquely defines the remaining ones (the value).

For example, the following predicate definition might be used to define the colour of a pixel on the screen (x and y are the coordinates of a point):

pixel_colour[x, y] = c -> int(x), int(y), colour(c). 

The declaration tells us that the predicate contains tuples of the form (x, y, c), where x and y together form the key, and that, given a particular key, the predicate will either not contain any tuple that begins with the key, or contain only one such tuple, thus uniquely determining the value (i.e., the colour).

L

lifetime

A property of logic and/or data that describes its persistence, but also the stage at which it is processed by a transaction. See Section 19.1.5, “The notion of "lifetime"”.

logic

A collection of declarations, constraints, facts, rules, delta rules and explicit commands to insert, delete or upsert tuples. Logic is usually packaged into units called blocks.

Data (i.e., tuples) are usually not considered to be "logic".

logical failure

"Logical failure" is a term we apply when, given some instantiation of its variables, the body of a rule is false with respect to the database.

Logical failure may happen, in particular, during the evaluation of an expression in the argument of an atom (or in a comparison): if the expression cannot be computed, we say that it fails, and the atom (or comparison) in which it appears is considered to be false.

For example, in the rule

p(x) <- x = y / z, q(y, z). 

(where x, y and z are integers) we need not worry about the case when z is zero: the division will then simply fail, so no x will be computed for that particular combination of y and z, and p will become populated only with those values of the form y/z which can be computed.

M

maintenance

A process that brings the database into a state that is consistent with recent changes in data or logic.

See Section 19.4.1, “Maintenance”.

See Also fixpoint.

materialization

We say that a predicate is materialized if its contents are an explicit part of the database. For instance, if the only rule for an IDB predicate odd100 is

odd100(x) <- int:range(1, 100, 2, x). 

then to materialize odd100 means to literally insert the 50 tuples (1), (3), (5) etc. into the database.

See Section 8.8, “Derivation Types” for information about how to avoid materialization of IDB predicates.

P

populated

We say that a predicate is (or becomes) populated when its tuples are inserted into the database.

predicate

In the context of the LogicBlox system the term "predicate" refers to a named set of tuples. A predicate is typed, i.e., all of its tuples have the same length, and each particular field of each of these tuples always has the same type.

A predicate is similar to a "table" in a relational database system. The main difference is that a predicate is a set (of tuples), while a table is a bag (of rows). In other words, a table can contain duplicates, but a predicate cannot.

See Chapter 8, Predicates.

pulse predicate

A predicate whose contents are not stored between transactions, even though the predicate itself may have database lifetime. Pulse predicates are used primarily as an auxiliary device to cause certain rules to "fire" during a transaction.

See Section 19.3.1, “Pulse predicates”.

See Also event logic.

Q

query lifetime

Logic and data that are executed at stage QUERY of a transaction (see Section 19.4.2, “The Six Stages”). Not only do they not persist for longer than the query stage of a transaction, but also the changes that they make to database-lifetime predicates are strictly temporary, and will disappear when the transaction terminates (regardless of whether it is aborted or committed).

See Also lifetime.

R

refmode predicate

An abbreviation for reference-mode predicate. Sometimes we say simply "refmode" and omit the word "predicate".

reference-mode predicate

A predicate that associates the entities in a particular entity predicate with labels (of some primitive type) that allow the programmer to refer to the entities by using the reference-mode predicate as one would use a dictionary. Creation of the entity and of the label are simultaneous.

See Section 8.3.2, “Reference-Mode Predicates”.

retraction

Sometimes used as a synonym for deletion.

rule

The unqualified term "rule" usually means an IDB rule. EDB rules are referred to as "delta rules".

A rule consists of a head and a body, each of which are LogiQL formulas. It can be read as an implication: if, for some instantiation of the rule's variables, its body is true (with respect to the contents of the database), then its head is also true.

(The above is not quite accurate if negation is involved. See the section called “Rules and the quantification of variables” for some more information.)

The complete set of all rules and facts whose head atoms refer to some IDB predicate p constitutes a complete definition of p: the predicate contains only those tuples which match some fact or a head atom of some rule whose body is true.

An IDB predicate can be considered as the LogiQL counterpart of a "view". Indeed, it need not be materialized, though it often is.

See Chapter 11, Rules.

S

scalar

A scalar predicate is a functional predicate with no keys, i.e., effectively a constant.

See Section 8.2, “Functional Predicates”.

signature

A predicate's name, arity, and the type of each of its arguments.

See Also declaration.

schema

The set of all predicate declarations (either explicit or implicitly derived) in a database.

stage

One of the stages of a transaction.

See Section 19.4.2, “The Six Stages”.

stage suffix

A suffix of the form predicate_name@stage that refers to the contents of the named predicate as they were at that particular stage of the transaction. Can only be used to refer to stages that are not later than the current one.

See Section 19.4.4, “Stage suffixes”.

T

transaction

A transaction is a series of actions such as deletion of old data, addition of new data and logic, evaluation of rules that update the data, and verification that the data violates no constraints.

A transaction is atomic, i.e., the results of all its actions are taken together as a "unit of change" to the database. If the transaction is aborted, the database is not modified at all. If the transaction is committed, its overall effect on the database will be the result of all its actions, not just of some of them.

In the LogicBlox system a transactions is rather complex, as it consists of several stages. To be effective, the user has to be aware of the stages and their function.

See Chapter 19, Transaction Logic.

transaction lifetime

Logic and data that do not persist for longer than a single transaction are said to have transaction lifetime. More specifically, the term applies to logic that is executed at stage INITIAL of a transaction (see Section 19.4.2, “The Six Stages”). Logic that is executed at stage QUERY is usually said to have query lifetime, rather than transaction lifetime.

See Also lifetime.

tuple

An unit of data, similar to the "row" of a table in relational databases. A tuple consists of fields. For instance, ("Mary", 7) is a tuple that consists of two fields: the string "Mary" and the integer 7. It is possible for a tuple to have one field, or even no fields.

Predicates are sets of tuples. A tuple together with the name of the predicate to which it belongs can be thought of as a logical fact. For example, age("Mary", 7) may be intended to mean that Mary is seven years old.

U

upsert

Update or insert. An upsert operation (which can be performed only on a functional predicate) will update the value associated with a given key if the relevant predicate already contains a tuple with that key, or simply insert a new tuple if the key is a new one.

V

value

This very general term is often used to describe the value that one gets from a functional predicate when one provides the key.

When talking about LogiQL variables, we prefer to talk about the instantiation of a variable, rather than its value.

variable

A variable in LogiQL is a logical variable, which is quite unlike a variable in imperative programming languages, and more like a variable in algebra and logic. See the section called “The concept of "a variable"” for an extended discussion.

See Also instantiation.

W

workspace

An instance of the database itself (as opposed to the LogicBlox database system). Contains logic and data.

See Section 19.1.2, “Workspaces”.