Appendix: Abstract Graphical View

The following graph is an alternative representation of the abstract syntax. It represents leaf values (constants, variables, …) in rectangles and composite values as ellipses. Additionally, where a composite is defined as $\small A \oplus B$ a small filled diamond shape represents the exclusive or relationship. Finally, some edges in the graph are labeled with “*”, “+”, and “?” which are the common cardinality notation used in regular expressions and BNF notation.

1. The edge between rule and head has the label “?/*” as it has differing cardinality under $\small\text{Datalog}$, $\small\text{Datalog}^{\lor}$, and $\small\text{Datalog}^{\bot}$.
2. The edge between literal and negated? is labeled as “?” as it is necessary under $\small\text{Datalog}^{\lnot}$ but not under $\small\text{Datalog}$.
3. The edge from the choice between literal and comparison is labeled as “?” as it is necessary under $\small\text{Datalog}^{\theta}$ but not under $\small\text{Datalog}$.
4. The two dashed lines represent the following constraints.
   1. Between relation and predicate to represent the fact that the predicate for a relation may be derived from the predicate of the atoms within it (or vice versa).
   2. Between head and body to represent the fact that while both are optional for a rule, one or other must be present.

GraphViz Source

The following is the source for the graph above.

digraph G {
  rankdir=LR;
  pad=0.1;
  splines=true;

  negated [label="negated?"; shape=box; width=0.1; height=0.1];
  boolean [shape=box; width=0.1; height=0.1];
  string [shape=box; width=0.1; height=0.1];
  integer [shape=box; width=0.1; height=0.1];
  variable [shape=box; width=0.1; height=0.1];
  anonymous [shape=box; width=0.1; height=0.1];
  predicate [shape=box; width=0.1; height=0.1;];

  program [root=true];

  program -> edb;
  program -> idb;
  edb -> relation [label="*"];
  idb -> relation [label="*"];
  idb -> rule [label="*"];
  rule -> head [label="?/*"];
  head -> atom;
  rule -> body [label="?"];
  body -> literal [label="+"];

  head -> body [arrowhead=none;style=dashed;label="|head|+|tail|>=1"];

  literal -> xor3;
  literal -> negated [label="?"];
  xor3 -> atom;
  xor3 -> comparison [label="?"];

  comparison -> term [label="lhs"];
  comparison -> term [label="rhs"];
  comparison -> operator;

  relation -> predicate [style=dashed];
  relation -> atom [label="*"];
  atom -> term [label="+"];
  atom -> predicate;

  term -> xor2;
  xor2 -> constant;
  xor2 -> variable;
  xor2 -> anonymous;

  xor1 [shape=diamond,style=filled,label="",height=.1,width=.1];
  xor2 [shape=diamond,style=filled,label="",height=.1,width=.1];
  xor3 [shape=diamond,style=filled,label="",height=.1,width=.1];

  constant -> xor1;
  xor1 -> integer;
  xor1 -> string;
  xor1 -> boolean;
}

This file is accessible directly here.