Overview of Dexlog
1. Dexter and Dexlog

Dexter is a browser-based, domain-independent explorer for structured data. Dexter allows users to explore structured data as tables. A user can populate a table in Dexter either by manually entering data or importing data from a file, database or an api. In addition, a user can populate a table using computations. Computations in Dexter are expressed as Dexlog rules. Dexlog is a variant of Datalog that is extended using negation, sets, tuples, aggregates, and built-in operators. This document presents an overview of Dexlog.

2. Syntax

The vocabulary of Dexlog consists of the following.

  • Object Constants: These are strings that are enclosed within double-quotes ("). Double-quotes, if used within the string, must be escaped. Examples: "1.23", and "\"Why?\""
  • Relation Constants: These refer to tables / relations and are strings of the form [a-z][a-zA-Z0-9_]* (with the exception of illegal and the names of built-in operators). Examples: senatorsInCA, p1_
  • Variables: These strings of the form [A-Z][a-zA-Z0-9_]*. Examples: Name, X and Xy_
  • Sets: These are enclosed within braces and can either be empty {} or a collection of object constants, sets, or tuples which are separated using comma (","). Examples {"1", "2", "3"}, and {{"1", "a"}, {"2"}}
  • Tuples: These are an ordered collection of one or more object constants, sets or tuples which are separated using commas (",") and aare enclosed within square brackets. Examples: ["1", "2", "3"], and [{"1", "2"}, "a", {["3", "4"]}]

3. Dexlog Rules

A Dexlog rule has two parts - a head and a body - separated by ":-". The head consists of a relation constant that is followed by a list of arguments (object constants, sets, tuples, or variables enclosed within round-brackets). The body consists of one or more heads (each of which could be prefixed by a tilde "~") that are separated using "&". For details regarding the Dexlog syntax, we refer the reader to this paper. Dexlog rules are evaluated under set semantics i.e. there are no duplicate answers. In the remainder of this section, we present examples of how Dexlog rules can be used to compute answers of different types of queries.

In our examples discussed below, we refer to the following instances of the tables - people, city and friend.

people city friend
X Y
Avocado male
Avocado female
Broccoli female
X Z
Avocado Stanford
Broccoli Berkeley
X Y
Avocado Broccoli
Broccoli Cabbage

Example 1 (Projecting Columns): Distinct values of one or more columns of a table can be computed by selectively passing the arguments of the body of a rule to the rule head. Consider the following rule.

q1(X) :- people(X, Y)

Evaluation of the above rule leads to the set of answers {X | ∃Y people(X, Y)}.

q1
X
Avocado
Broccoli

Example 2 (Filtering Columns): A filter can be applied on a table by substituting variables of a table with object constants. Consider the following rule.

q2(X) :- people(X, "male")

Evaluation of the above rule leads to the set of answers {X | ∃Y people(X, "male")}.

q2
X
Avocado

Example 3 (Joining Tables): The following rule computes the join of the tables q2 (see Example 2) and city.

q3(Z) :- q2(X) & city(X, Z)

Evaluation of q3 leads to the set of answers {Z | ∃X q2(X) ∧ city(X, Z)}.

q3
Z
Stanford

Example 4 (Disjunction): Computations can also be defined using multiple Dexlog rules. In such a case, the set-union of the answers of all rules is computed. Consider the following rules that compute the set of all people involved in a friendhip.

q4(X) :- friend(X, Y)
q4(X) :- friend(Y, X)

Evaluation of q4 leads to the set of answers {X | ∃Y friend(X, Y)} ∪ {X | ∃Y friend(Y, X)}.

q4
X
Avocado
Broccoli
Cabbage

Example 5 (Negation): Dexlog rules with negation are evaluated under the closed-world assumption using negation-as-failure. Consider the following query.

q5(X) :- q1(X) & ~q2(X)

In the above query, X is an answer of q5 iff X is an answer of q1 but not of q2.

q5
X
Broccoli

Example 6 (Recursion): Dexlog rules can also be tail-recursive. Consider the following query that computes the transitive closure of the friend table.

q6(X, Y) :- friend(X, Y)
q6(X, Y) :- friend(X, Z) & q6(Z, Y)

The first rule for q6 establishes the base-case of the recursion. The second rule computes friends transitively.

q6
X Y
Avocado Broccoli
Broccoli Cabbage
Avocado Cabbage

4. Aggregates

A key difference between Datalog and Dexlog is the introduction of sets (and tuples) as first-class citizens. In addition to set constants (introduced in 2. Syntax), Dexlog supports a special operator called setof for constructing sets.

A setof atom has the general syntax:

setof(AggArg, Body, SetArg) where,

  • AggArg can either be a variable, constant or a tuple.
  • Body is the body of a Dexlog rule.
  • SetArg is variable or a set constant.

Evaluation of setof(AggArg, Body, SetArg) binds SetArg to the set of answers (of vSet) that is computed using the following rule.

vSet(AggArg) :- Body

Safety: The variables of Body that are not AggArg must be bound in (some positive atom) outside of the setof atom.

Example 7 (Aggregation): Consider the following Dexlog rules which compute the set of different genders that a name is associated with.

q7(X, S) :- aux(X) & setof(Y, person(X, Y), S)
aux(X) :- person(X, Y)

In the above rules, the auxiliary relation aux is used to bind the value of the variable X which is free with respect to the setof operator. Evaluation of the above rules, results in the following answers {[X, S] | aux(X) ∧ S = {Y | people(X, Y)}}.

q7
X S
Avocado {"male", "female"}
Broccoli {"female"}

Constraints and illegals: In addition to the usual rules that compute values, Dexlog also allows the definitions of constraints to validate answers of a table or a computation with respect to supplied conditions. Constraints have the general form illegal :- Body, where Body is any body of a Dexlog rule. Example of a constraint which specifies that a Avocado cannot have female friends.

illegal :- friend("Avocado", X) & person(X, "female")

Since Avocado is friends with Broccoli who is a female, the evaluation of the above rule yields an illegal, which suggests the violation of the above constraint.

5. Built-ins

Dexlog has a number of built-in predicates that include arithmetic operators (for example: gt, plus, mod), string-manipulation operators (for example: length, substr, concat), set-based operators (for example: member, union) and tuple-based operators (for example: attr). The complete listing of the built-in operators, their arity, binding patterns and description is provided below.

NameTypeArgPatternDescription
same(X, Y)general2bf, fbFalse if X and Y are bound and X ≠ Y. Otherwise True. If variable X is free then, X is bound to Y's value. Similarly if Y is free.
distinct(X, Y)general2bbTrue if X ≠ Y, otherwise False.
gt(X, Y)general2bbTrue if X > Y, otherwise False.
lt(X, Y)general2bbTrue if X < Y, otherwise False.
geq(X, Y)general2bbTrue if X ≥ Y, otherwise False.
leq(X, Y)general2bbTrue if X ≤ Y, otherwise False.
seq([X,] Y, [Z,] W)general4bbbfFalse if W is bound and W ∉ sequence that starts at 1 (or X) and ends at Y with an increment of 1 (or Z). Otherwise, True. If W is free, W is bound to the sequence starting at 1 (or X) and ends at Y with an increment of 1 (or Z)
plus(X1, [X2 ...,] Xn)numbernbb...fFalse if Xn is bound and Xn ≠ X1 + X2 + ... Xn-1. Otherwise True. If Xn is free, Xn is bound to X1 + X2 + ... + Xn-1.
times(X1, [X2 ...,] Xn)numbernbb...fFalse if Xn is bound and Xn ≠ X1 * X2 * ... Xn-1. Otherwise True. If Xn is free, Xn is bound to X1 * X2 * ... * Xn-1.
minus(X, Y, Z)number3bbfFalse if Z is bound and Z ≠ X - X2. Otherwise, True. If Z is free, Z is bound to X - Y.
div(X, Y, Z)number3bbfFalse if Z is bound and Z ≠ X ÷ X2. Otherwise, True. If Z is free, Z is bound to X ÷ Y.
mod(X, Y, Z)number3bbfFalse if Z is bound and Z ≠ X % Y. Otherwise, True. If Z is free, Z is bound to X % Y.
pow(X, Y, Z)number3bbfFalse if Z is bound and Z ≠ X ^ Y. Otherwise, True. If Z is free, Z is bound to X ^ Y.
exp(X, Y)number2bfFalse if Y is bound and Y ≠ e ^ X. Otherwise, True. If Y is free, Y is bound to e ^ X.
sqrt(X, Y)number2bfFalse if Y is bound and Y ≠ √X. Otherwise, True. If Y is free, Y is bound to √X.
log(X, Y)number2bfFalse if Y is bound and Y ≠ ln X. Otherwise, True. If Y is free, Y is bound to ln X.
ceil(X, Y)number2bfFalse if Y is bound and Y ≠⌈X⌉. Otherwise, True. If Y is free, Y is bound to⌈X⌉.
floor(X, Y)number2bfFalse if Y is bound and Y ≠⌊X⌋. Otherwise, True. If Y is free, Y is bound to⌊X⌋.
round(X, Y)number2bfFalse if Y is bound and Y ≠ |X|. Otherwise, True. If Y is free, Y is bound to |X|.
abs(X, Y)number2bfFalse if Y is bound and Y ≠ absolute value of X. Otherwise, True. If Y is free, Y is bound to absolute value of X.
strlen(X, Y)string2bfFalse if Y is bound and Y ≠ length of string X. Otherwise, True. If Y is free, Y is bound to length of string X.
indexOf(X, Y, Z)string3bbfFalse if Z is bound and Y does not occur at position Z in the string X. Otherwise, True. If Z is free, Z is bound to the position at which Y first occurs in the string X.
lower(X, Y)string2bfFalse if Y is bound and Y ≠ string X (where all upper-case characters are converted to lower-case). Otherwise, True. If Y is free, Y = X with all characters in X converted to lower-case equivalents.
upper(X, Y)string2bfFalse if Y is bound and Y ≠ string X (where all lower-case characters are converted to upper-case). Otherwise, True. If Y is free, Y is bound to X's value with all characters in X converted to upper-case equivalents.
trim(X, Y)string2bfFalse if Y is bound and Y ≠ string X (without leading and trailing white-spaces). Otherwise, True. If Y is free, Y is bound to X's value without leading and trailing white-spaces.
concat(X1, [X2, ...,] Xn)stringnbb...fFalse if Xn is bound and Xn ≠ concatenation of the strings X1, X2 ..., Xn-1. Otherwise, True. If Y is free, Y is bound to the concatenation of the strings X1, X2 ..., Xn-1.
split(X, Y, Z)string3bbfFalse if Z is bound and Z ∉ set of strings that are formed by splitting the string X using the delimiter Y. Otherwise, True. If Z is free, Z is bound to strings that are formed by splitting the string X using the delimiter Y.
replace(X, Y, Z, W)string4bbbfFalse if W is bound and W ≠ string X where the string / regular expression Y is replaced using the string / regular expression Z. Otherwise, True. If W is free, W is bound to string X with the string / regular expression Y is replaced using the string / regular expression Z.
like(X, Y)string2bbFalse if X does not contain the string Y. Otherwise, True.
substr(X, Y, [Z, ] W)string4bbbfFalse if W is bound and W ≠ substring of X from position Y to position Z or the end of the string (if Z is not specified). Otherwise, True. If W is free, W is bound to substring of X from position Y to position Z or the end of the string (if Z is not specified).
matches(X, Y, Z)string3bbfFalse if Z is bound and Z ∉ substrings of X that match the string / regular expression Y. Otherwise, True. If Z is free, Z is bound to the substrings of X that match the string / regular expression Y.
editDist(X, Y, Z)string3bbfFalse is Z is bound and Z ≠ levenshtein distance between the strings X and Y. Otherwise, True. If Z is free, Z is bound to the levenshtein distance between X and Y.
lcs(X, Y, Z)string3bbfFalse is Z is bound and Z ≠ longest common subsequence of the strings X and Y. Otherwise, True. If Z is free, Z is bound to the longest common subsequence of X and Y.
memberOf(X, Y)set2fbFalse if X is bound and X ∉ set Y. Otherwise, True. If X is free X is bound to the elements of the set Y
unionOf(X1, [X2, ...,] Xn)setnbb...fFalse if Xn is bound and X ≠ X1 ∪ X2 ... ∪ Xn-1. Otherwise, True. If X is free, Xn is bound to X1 ∪ X2 ... ∪ Xn-1.
intersectionOf(X1, [X2, ...,] Xn)setnbb...fFalse if Xn is bound and X ≠ X1 ∩ X2 ... ∩ Xn-1. Otherwise, True. If X is free, Xn is bound to X1 ∩ X2 ... ∩ Xn-1.
differenceOf(X, Y, Z)set3bbfFalse if Z is bound and Z ≠ X \ Y. Otherwise, True. If Z is free, Z is bound to X \ Y.
subsetOf(X, Y)set2fbFalse if X is bound and X ⊆ Y. Otherwise, True. If X is free, X is bound to the subsets of Y.
cartesianProductOf(X1, [X2, ...,] Xn)setnbb...fFalse if Xn is bound and X ≠ X1 x X2 ... x Xn-1. Otherwise, True. If X is free, Xn is bound to X1 x X2 ... x Xn-1.
countOf(X, [Y,] Z) set3bbfFalse if Z is bound and Z ≠ cardinality of the set X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the cardinality of the set X or the {x[Y] | x ∈ X} (if Y is specified).
sumOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ sum of the set of numbers X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the sum of the set X or the {x[Y] | x ∈ X} (if Y is specified).
prodOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ product of the set of numbers X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the product of the set X or the {x[Y] | x ∈ X} (if Y is specified).
avgOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ average of the set of numbers X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the average of the set X or the {x[Y] | x ∈ X} (if Y is specified).
stddevOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ standard deviation of the set of numbers X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the standard deviation of the set X or the {x[Y] | x ∈ X} (if Y is specified).
maxOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ maximum of the set X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the maximum of the set X or the {x[Y] | x ∈ X} (if Y is specified).
minOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ minimum of the set X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the minimum of the set X or the {x[Y] | x ∈ X} (if Y is specified).
medianOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ median of the set of numbers X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the median of the set X or the {x[Y] | x ∈ X} (if Y is specified).
modeOf(X, [Y,] Z)set3bbfFalse if Z is bound and Z ≠ mode of the set of numbers X or the {x[Y] | x ∈ X} (if Y is specified). Otherwise, True. If Z is free, Z is bound to the mode of the set X or the {x[Y] | x ∈ X} (if Y is specified).
attr(X, Y, Z)tuple3bbfFalse if Z is bound and Z ≠ X[Y]. Otherwise, True. If Z is free, Z is bound to the value X[Y].
glue(X1, [X2, ...,] Xn)tuplenbb...fFalse if Xn is bound and Xn ≠ X1 ⊗ X2 ... ⊗ Xn-1. Otherwise, True. If Xn is free, Xn is bound to the tuple X1 ⊗ X2 ... ⊗ Xn-1.
join(X,[Y,] Z)tuple / set3bbfFalse if Z is bound and Z ≠ string formed by concatenating the attributes of the tuple X or members of the set X using the delimiter Y (or "," is Y is not specified). Otherwise, True. If Z is free, Z is bound to the string that is formed by concatenating the attributes of the tuple X or members of the set X using the delimiter Y (or "," is Y is not specified).
slice(X, Y, [Z,] W)tuple4bbbfFalse if Z is bound and Z ≠ X[Y..] or Z ≠ X[Y..Z] (if Z is specified). Otherwise, True. If Z is free, Z is bound to the value X[Y..] or X[Y..Z] (if Z is specified).
arity(X, Y)tuple2bfFalse if Y is bound and Z ≠ arity of the tuple X. Otherwise, True. If Y is free, Y is bound to the arity of X.