This work presents some SQL puzzles making use of the application of Hypothetical Datalog (HD) to implement an SQL system. HD provides a way of declaring SQL Common Table Expressions as used to specify local view definitions and recursive queries. We present the concepts of HD that will be employed to translate SQL queries to HD, providing its syntax, an inference system and translation rules. Finally, several SQL puzzles used during teaching SQL in a database subject are proposed.
possibility of making assumptions, both positive (assuming data which is not in the database) and negative (neglecting data which is already in the database) for querying the database. However, since these puzzles are targeted at database students, we restrict ourselves to uses admitted by the SQL standard and leave the extension out of the scope of this paper.
DES is built with concepts from intuitionistic logic programming (ILP) [
SQL data-retrieval queries usually start with a SELECT keyword, which builds the outcome in terms of its expression list. An exception to this is the WITH clause, which permits local view declarations which can be used in its outcome SQL statement. These declarations are known as Common Table Expressions (CTE’s), and its syntax in recursive WITH queries can be simplified as:
WITH RECURSIVE
R1 AS SQL1, -- CTE1 ...,
R AS SQL -- CTE
SQL -- Outcome SQL where each R is a local, temporary view name defined by the SQL query SQL, and can be referenced only in the context of each SQL and SQL , which is the query that builds the outcome. Each declaration R AS SQL is a CTE. Whilst a local view declaration is similar to a CREATE VIEW declaration, its scope is restricted as already noted, and its lifetime is the same as for SQL .
Though CTE’s are used for a number of reasons (divide-and-conquer, readability, creating views for which the user has no rights, . . . ), we are interested in the use that enables SQL as a Turing complete language: by specifying recursive queries. As an example, the following defines natural numbers: WITH RECURSIVE
nat(n) AS (SELECT 0 UNION ALL SELECT n+1 FROM nat)
SELECT n FROM nat; where the keyword RECURSIVE is required by the standard to specify a (potentially) recursive CTE, the first SELECT is the base case (simply returning the tuple (0) as a FROM-less statement), which is unionised with the inductive case (second SELECT). This single CTE is used in the outcome SQL (third SELECT) to deliver all the naturals. Query semantics can be understood as finding its fixpoint for the application of the unionised queries on an enlarging relation nat, which is increased with a new number in each fixpoint-search iteration. In this case, the fixpoint would be infinite, though top- queries can limit the number of retrieved tuples.
Current SQL systems include limitations on recursive queries: mutual and non-linear recursion are
not allowed, only one recursive case can be set, and duplicate elimination is not allowed in the union
of the base and inductive cases. These limitations can be overcome with other database languages
such as Datalog operating over the same relational data, a language capable of expressing mutual and
non-linear recursion, and duplicates [
Here is where intuitionistic logic programming (ILP) can be of help because it adds embedded
implications in the body of clauses. Intuitively, in an embedded implication ⇒ , the atom
is assumed during proving [
:= | ← 1 ∧ . . . ∧ := | ¬ | 1 ◇ 2 | () | (, ) | (, , ) | 1 ∧ . . . ∧ ⇒ where stands for rule, for goal, for atom (possibly containing variables and constants, but no compound terms), is a natural number, is a list of variables, are expressions, ◇ is a comparison operator (=, <, ≤ . . . ), symbols ¬, , and are meta-predicates, and ( ) do not occur out of .
Here, the symbol ⇒ denotes the embedded implication (it builds a goal that can occur in the body
of a rule), and is a duplicate elimination meta-predicate. The first condition (on compound terms) is
needed for ensuring a finite fixpoint in absence of infinite relations, and the second one (on variables of
rules ) ensures that is not specialized by any substitution out of it along inferencing, so can be
assumed “as is” for any inference step, which is an adequate requirement for modelling local definitions
in SQL WITH statements (however, it represents a limitation with respect to [
Symbols ¬, , and are meta-predicates, standing respectively for negation, duplicate elimination, top- queries, and group-by (for solving aggregations as counts and summations, which can occur in expressions as other scalar functions). A group-by goal (, , ) means that ground instances of are grouped by the list of variables (grouping criteria) and, for each group, there is at most one instantation such that it fulfils .
Next, we extend the inference system in [
Δ ⊢ is an inference expression, where is an identified ground atom : . Such an is of the form 1 · · · · · ( ≥ 1) and helps data provenance for supporting duplicates. () is the predicate of atom . A negative inference expression is of the form Δ ⊢ : − . Negative inference expressions play a key role in the SQL extension for negative assumptions, but are out of the scope of this paper. Next definition specifies an inference system where each rule is read as: If the formulas above the line can be inferred, then the ones below the line can be inferred as well. The application of an inference rule is an inference step.
Definition 2.2 (Inference system). Given a database Δ and a set of input inference expressions ℰ , the inference system associated to the -th stratum is defined as follows, where (ℰ ) is a closure operator that denotes the set of inference expressions derivable in this system: Axioms: • Δ ⊢ : is an axiom for each (ground) atomic formula : in Δ, where (Δ, ()) = . • Δ ⊢ 1 ◇ 2 is an axiom, where ◇ ∈ { =, <, >, ≤ , ≥} , are constants, and 1 ◇ 2 holds. • Each expression in ℰ is an axiom.
Inference Rules: • For any rule ← 1 ∧ . . . ∧ with identifier in Δ, where (Δ, ()) = and for any ground substitution : Δ ⊢ : for each
Δ ⊢ ′ : where ′ is the composition of identifiers · 1 · · · . • For any constants and expressions :
Δ ⊢ 1 ◇ 2 Δ ⊢ 1 ◇ 2 where ◇ ∈ { =, <, >, ≤ , ≥} , and evaluates to . • For any atoms , ′:
Δ ⊢ : Δ ⊢ : (′ ) where = ′ , is a single, unique identifier. • For any atoms , , natural number , and ground substitutions :
Δ ⊢ : Δ ⊢ : (, ) where = , are at most single, unique identifiers. • For any atoms , , , and ground substitutions , : (Clause) (Expression) (Duplicates)
(Top) (Assumption) Example 1. Natural numbers can be specified in this language as follows: 1 ≡ ((0) ∧ (() ←
( ) ∧ = + 1)) ⇒ () Starting with Δ = ∅, and applying the Assumption rule:
{((0)), (() ← ∅ ⊢ ((0) ∧ (() ← ( ) ∧ = + 1)} ⊢ ()
( ) ∧ = + 1)) ⇒ () Δ, originally empty, has been enlarged with the two rules in the assumption (let us call it Δ′), and each one receives a unique identifier (as any other possible rule in the program). For this example, let 1 and 2 be the respective identifiers for (0) and () ← ( ) ∧ = + 1. In a second inference step, we can apply the Clause inference rule, giving: Δ′ ⊢ 1 : (){ ↦→ 0} ≡ Δ′ ⊢ 1 : (0), where = { ↦→ 0}, and Δ′ ⊢ 1 : (0) represents a first solution of the query. This can be read as: the atom (0) identified by 1 has been inferred for the context Δ′. Next, using 2 in Clause for some after Assumption yields: Δ′ ⊢ : ( ) 1 Δ′ ⊢ ( = + 1) 1 Δ′ ⊢ 2 · : () 1
Δ ⊢ : Δ ⊢ : ( , , ) where each is a unique identifier for each group , and = , = . (Group-By) • For any goal : Δ ∪ { 1, . . . , } ⊢ Δ ⊢ 1 ∧ . . . ∧ ⇒ where axioms above the line can be inferred: First, the axiom Δ′ ⊢ 1 : (0) (with = { ↦→ 0}) as before, and the second one because it becomes a trivial axiom Δ′ ⊢ 1 = 1 after applying Expression (i.e., the evaluated = 0 + 1 for { ↦→ 1}). So 1 = { ↦→ 0, ↦→ 1}, and the axiom Δ′ ⊢ 2 · 1 : (1) can be inferred. Proceeding in the same way, the following axioms are inferred with > 0: Δ′ ⊢ 2 · · · 2 · 1 : ()
⏟ ⏞
Negative information is deduced by applying the closed-world assumption to a set of inference expressions ℰ (written as (ℰ )) as the union of ℰ and the negative inference expression for Δ ⊢ such that Δ ⊢ ∈/ ℰ . Thus, a stratified bottom-up construction of the unified stratified semantics can be specified by: • ℰ 0 = ∅ • ℰ +1 = (+1(ℰ )) for ≥ 0. which builds a set of axioms ℰ that provides a way to assign a meaning to a goal with: (, ℰ ) = {Δ ⊢ : ∈ ℰ | = } where is a substitution and each axiom in ℰ is mapped to the database Δ it was deduced for, and the inferred fact is labelled with its data source (for supporting duplicates). We use Δ(ℰ ) to denote the multiset of facts so that Δ ⊢ : ∈ ℰ for any . In Example 1, there is only one stratum, so: (1, ℰ ) = {Δ′ ⊢ 2 · · · 2 · 1 : () | ≥ 0} = ℰ1
⏟ ⏞ and the outcome would be the multiset Δ(ℰ1 ) = {() | ≥ 0}.
A top-10 goal for this example would restrict the number of solutions as: Δ(ℰ (10,1)) = {() | 0 ≤ ≤ 9}, which corresponds to modifying the outcome SQL query in the WITH statement by SELECT TOP 10 n FROM nat.
The stratified construction of inference expressions captures the requirements of SQL clauses such
as EXCEPT, NOT IN, and GROUP BY, which are sources of negative arcs in the construction of a predicate
dependency graph (PDG) [
Here, the function SQL_to_DL is defined by extending Definition 6 in [
Definition 3.1. The function SQL_to_DL takes a relation name and an SQL statement as input and returns a Datalog program as defined by cases as follows: % Basic SELECT statement SQL_to_DL (, SELECT FROM WHERE ) =
{ () ← ( ) ∧ () ∧ () } ⋃︀ ⋃︀ ⋃︀ , where SQLREL_to_DL () = (( ), ), SQLEXPS_to_DL () = ((), , ), and SQLCOND_to_DL () = ((), ). Here, each E in the list is either an expression or an argument name present in the relation with corresponding logic variable ∈ . is either a single defined relation (table or view), or a join of relations, or an SQL statement. Function SQLREL_to_DL (respectively, SQLCOND_to_DL ) takes an SQL relation (respectively, condition) and returns a goal with as many variables as arguments of and, possibly, additional rules which result from the translation (and similarly for SQLEXPS_to_DL ()). Variables ⊆ come as a result of the translation of the condition to a goal. % GROUP BY statement SQL_to_DL (, SELECT FROM GROUP BY ) =
{ () ← ∧ (( ), , ) } ⋃︀ ⋃︀ , where SQLEXPS_to_DL () = (, , ), SQLREL_to_DL () = (( ), ). Here, ⊆ are the variables of the predicate corresponding to the attributes of the relation . % Top- SQL_to_DL (, SELECT TOP N FROM WHERE ) = { () ← (, ′()) } ⋃︀ , where SQL_to_DL (′, SELECT FROM WHERE ) = % Union SQL_to_DL (, SQL1 UNION ALL SQL2) = SQL_to_DL (, SQL1) ⋃︀ SQL_to_DL (, SQL2) % Diference SQL_to_DL (, SQL1 EXCEPT SQL2) =
{ () ← () ∧ ¬() } ⋃︀ SQL_to_DL (, SQL1) ⋃︀ SQL_to_DL (, SQL2) % Intersection SQL_to_DL (, SQL1 INTERSECT SQL2) =
{ () ← () ∧ () } ⋃︀ SQL_to_DL (, SQL1) ⋃︀ SQL_to_DL (, SQL2) % WITH statement SQL_to_DL (, WITH 1 AS SQL1, ..., AS SQL SQL ) =
{ () ← ⋀︀({SQL_to_DL (, SQL ) | 1 ≤ ≤ }) ⇒ () } ⋃︀ SQL_to_DL (, SQL ) where ⋀︀() denotes 1 ∧ · · · ∧
( ∈ ).
Next three definitions specify the functions SQLREL_to_DL , SQLEXPS_to_DL and SQLCOND_to_DL which are used by SQL_to_DL .
Definition 3.2. The function SQLREL_to_DL takes an SQL relation (either a relation name, or a join of relations, or an SQL statement) as input and returns both a Datalog goal and program as defined by cases as follows: % Extensional/Intensional relation name SQLREL_to_DL ( ) = ( (), {}) where are the variables corresponding to the -ary relation . % Join of relations SQLREL_to_DL ((1, . . . , )) = ((1)∧· · ·∧ (), 1 ∪· · ·∪ ) where SQLREL_to_DL () = ((), ). % SQL statement SQLREL_to_DL () = ( (), SQL_to_DL ( , )) where are the variables corresponding to the -ary statement , and is a fresh relation name. Definition 3.3. The function SQLEXPS_to_DL takes a sequence of SQL expressions as input and returns a Datalog conjunctive goal for expressions, another for aggregates, and a program, as defined by cases as follows: % Sequence of expressions SQLEXPS_to_DL ((1, . . . , )) = (⋀︀{ | 1 ≤ ≤ }, ⋀︀{ | 1 ≤ ≤ }, 1 ∪ · · · ∪ ), where SQLEXPS_to_DL () = (, , ). % Expression SQLEXPS_to_DL () = (( = ) ∧ , , ), where is the variable corresponding to the expression at position in the list of SQL expressions (1, . . . , ), and is the result of: 1) replacing each attribute of a relation in by the respective variable of the predicate ; 2) replacing each aggregate function over an attribute of the relation by a fresh variable . For each out of , includes a conjunctive goal = ( ), where is the variable of () which corresponds to the attribute ; and 3) replacing each query with alias by a fresh variable such that SQL_to_DL (, ) = (), contains , and includes a conjunctive goal ( ).
Definition 3.4. The function SQLCOND_to_DL takes an SQL condition as input and returns a Datalog conjunctive goal and a program, as defined by cases as follows: % Basic condition SQLCOND_to_DL (1 2) = ((1 ′ 2) ⋀︀{( = ) ∧ | 1 ≤ ≤ 2}, 1 ∪ 2), where SQLEXPS_to_DL () = (( = ) ∧ , , ), 1 ≤ ≤ 2, and ′ is the Datalog corresponding comparison operator to . % Conjunction SQLCOND_to_DL (1 AND 2) = (1′ ∧ 2′, 1 ∪ 2) where (1 ≤ ≤ 2) are conditions and SQLCOND_to_DL ()=(′, ). % Disjunction SQLCOND_to_DL (1 OR 2) = ( (), { ← 1′, ← 2′} ∪ 1 ∪ 2) where (1 ≤ ≤ 2) are conditions, SQLCOND_to_DL ()=(′, ), and is a fresh atom. % Negated condition SQLCOND_to_DL (NOT ) = (′, ) where ′=SQLCOND_to_DL ()=(′, ), and represents the logical complement of ( < = ≥ , 1 ∧ 2 = 1 ∨ 2, and so on).
Note that disjunction requires duplicate elimination because, otherwise, there can be more tuples in the result because a disjunction in a rule is rewritten as two rules, as the next example illustrates: Example 2. Consider the SQL query SELECT SQRT(2) FROM dual WHERE TRUE OR TRUE defining a relation . The relation dual, as originally defined by Oracle, contains a single row and a single column, and it was included as a predefined relation to allow for calculations such as this example. DES includes this as a propositional relation instead (there is no need for an argument because it is not intended to be used). Translating this query using Definition 3.1- Basic SELECT statement, where = dual, = SQRT(2) and = TRUE OR TRUE results in: SQL_to_DL (, SELECT SQRT(2) FROM dual WHERE TRUE OR TRUE) = { () ← ∧ () ∧ } ⋃︀ ⋃︀ ⋃︀ = { () ← ∧ = (2) ∧ (), ← , ← } (rules with respective identifiers 1, 2 and 3), because following Definition 3.2- Extensional/Intensional relation name: SQLREL_to_DL (dual) = (, ) = (, {}), following Definition 3.3-Expression: SQLEXPS_to_DL (SQRT(2)) = (, , ) = (( = (2)), , {}), and following Definition 3.4- Disjunction: SQLCOND_to_DL (TRUE OR TRUE) = (, ) = ( (), { ← , ← }). Thus, ((), ℰ) = {Δ ⊢ 1 · : (1.4142)} (where is the fresh identifier introduced by Definition 2.2- Duplicates). Without duplicate elimination (goal instead of () in rule 1): ((), ℰ) = {Δ ⊢ 1 · 2 : (1.4142), Δ ⊢ 1 · 3 : (1.4142)}, which is not the expected outcome for the SQL query.
The actual system applies other techniques to simplify the translated program, such as partial
evaluation and folding/unfolding [
Next, the translation of a recursive WITH statement is illustrated.
Example 3. Consider the SQL query in Subsection 1.1 defining natural numbers. Translating this query follows Definition 3.1- WITH statement, where 1 = nat, SQL 1 = SELECT 0 UNION ALL SELECT n+1 FROM nat, and SQL = SELECT n FROM nat: SQL_to_DL (, WITH RECURSIVE nat(n) AS (SELECT 0 UNION ALL SELECT n+1 FROM nat) SELECT n FROM nat ) = { () ← ⋀︀({SQL_to_DL (, SQL ) | 1 ≤ ≤ }) ⇒ () } ⋃︀ SQL_to_DL (, SQL ) = {(() ← (((1) ← ∧ 1 = 0 ∧ ) ∧ ((2) ← ( ) ∧ 2 = + 1 ∧ ) ⇒ ())), ((3) ← () ∧ 3 = ∧ )} because, by Definition 3.1- Union: SQL_to_DL (, SELECT 0 UNION ALL SELECT n+1 FROM nat) = SQL_to_DL (, SELECT 0) ∪ SQL_to_DL (, SELECT n+1 FROM nat) and, by Definition 3.1- Basic SQL statement, where SELECT 0 is an abbreviation for SELECT 0 FROM dual WHERE TRUE, the following is get by performing similar steps to Example 2: SQL_to_DL (, SELECT 0) = { (1) ← ∧ 1 = 0 ∧ }, and applying again the same definition to: SQL_to_DL (, SELECT n+1 FROM nat) = { (2) ← ( ) ∧ 2 = + 1 ∧ }, and: SQL_to_DL (, SELECT n FROM nat) = { (3) ← () ∧ 3 = ∧ }.
Further simplification and unfolding steps done in the system results in a single rule:
{(() ← ((0)) ∧ (( ) ← () ∧ = + 1) ⇒ ())}. □
[
This section provides several SQL puzzles9 provided to students and solved in DES, mainly with its
on-line interface DESweb. We use the concrete SQL syntax that DES supports, allowing for omitting
the verbose RECURSIVE modifier which, though promoted and required by the standard for recursive
queries, it seems to be an unneeded writing burden (a simple program analysis can classify recursive
predicates and apply both specific compilations and optimizations). Also, UNION can be used instead of
UNION ALL if duplicates are not required. Even when it might seem that discarding duplicates results
in a solving overhead, it turns out to be the opposite for recursive queries [
Here, we use the concrete syntax of DES, where :- stands for the neck of a rule, the comma (,) for goal conjunction, => for embedded implication, /\ for rule assumptions, distinct() for (), top( ,) for (, ), and group_by(,,) for (, , ). Relation attributes are not explicitly qualified with the relation name unless necessary.
Problem Statement: Compute the Euler number as a Taylor series: = As stop condition implicitly use the system precision for numbers.
A Solution: A straightforward solution is to define a CTE for the factorials with a schema of two arguments: the index (n) and the value of ! (factorial). Its base case is (0, 1), and the inductive case just computes (n + 1, n+1*factorial), given an already-computed tuple (n, factorial). Then, define each term in the series as another CTE, say taylor, with a single column (euler) with each term in the series, computed as 1/factorial from the CTE factorials: WITH factorials(n, factorial) AS
(SELECT 0, 1 UNION ALL SELECT n+1, (n+1)*factorial FROM factorials) WITH taylor(euler) AS
(SELECT 1/factorial FROM factorials) SELECT SUM(euler) FROM (SELECT TOP 18 euler FROM taylor);
Note a couple of things: First, there are two nested WITH statements (factorials is only known in the context of the subsequent WITH statement. Alternatively, two consecutive CTE’s are also possible. Second, the outcome SQL needs a top- clause to limit recursion. Up to now, main RDBMS’s as PostgreSQL, DB2, SQL Server, and Oracle do not admit nested WITH statements.
Datalog Formulation: Next, it is shown the automatically-generated core Datalog10 query and program corresponding to the SQL statement. The program is asserted before solving the query and retracted afterwards. factorials(0,1) /\ (factorials(B,C) :- factorials(D,E), B=D+1, C=(D+1)*E) => answer_1_6(A). answer_1_6(A) :- (taylor(B) :- factorials(_C,D), B=1/D) => answer_1_8(A). answer_1_8(A) :- group_by(answer_1_10(B),[],A=sum(B)). answer_1_10(A) :- top(18,taylor(B)), B=A.
This translation folds some relations for the deductive engine to be able to solve the query. Instead, a user would alternative write a query like this: factorials(0,1) /\ ( factorials(D,E) :- factorials(F,G), D=F+1, E=(F+1)*G ) => (taylor(B) :- factorials(_C,D), B=1/D) => group_by(top(18,taylor(B)),[],A=sum(B)).
An alternative solution is to define a CTE with an argument for the index of the -th term in the series, the value of the term (), and the current value of the running summation (). Thus, the base case is = 0, = 1, and = 1, and the inductive case computes the next term for presolved cases delivering + 1, /( + 1) (which equates to divide the -th term by + 1), and accumulating in the + 1-th approximation. The stop condition should test if the last term is strictly greater than 0, since otherwise this means that the system numeric precision is met. 10Core Datalog is the language directly processed by the deductive engine. (User) Datalog is the language that the user can use at the top-level, and that enables high-level formulations for expressions and some metapredicates. WITH re(n,term,val) AS (SELECT 0, 1.0, 1.0 UNION
SELECT n+1, term/(n+1), val+term/(n+1) FROM re WHERE term/(n+1) > 0)
SELECT MAX(val) AS euler FROM re;
re(0,1,1) /\ ( re(B,C,D) :- re(E,F,G), H=F/(E+1), H>0, B=E+1, C=F/(E+1), D=G+F/(E+1) ) => group_by(re(_B,_C,D), [], A=max(D)).
By submitting this user Datalog query at the top-level, the system compiles it to an almost equal core Datalog query and program as shown above for the SQL case. Such compilations can be inspected with the command /show_compilations on.
Outcome: The query returns in the SICStus implementation: answer(euler:float) -> { answer(2.7182818284590455) }
Obviously, the precision of the approximation to the Euler number depends on the underlying system arithmetics. Here, the last digit should read 2 instead of 5. This outcome is available by submitting the command display_answer on.
Problem Statement: We are given the table hits(theme string, copies int),11 holding song titles and number of sold copies for each title. Write a recursive SQL query to assign the rank of each song in terms of its sold copies (number 1 is for the most sold song, number 2 for the next and so on). If there are two or more songs with the same number of copies, they will receive the same rank number. A Solution: An idea to solve this puzzle is to build pairs with an integer representing the rank and the number of copies for hits such that there no other hits with a higher number of copies. Then, return the maximum rank for each group of hits with the same number of copies, adding to the output the song titles (known from the table hits and their number of copies).
The base case in the recursive part is rank 1 for all hits. The inductive case rec is the next rank in rec such that the copies in hits is strictly less than the copies in rec, i.e., once all copies receive a rank 1, the rank 2 is received to all copies but the one with the maximum number of copies, and so on. Its SQL formulation is as follows: WITH rec(ranking, copies) AS (SELECT 1, copies FROM hits
UNION SELECT ranking+1, hits.copies FROM hits, rec
WHERE hits.copies < rec.copies) SELECT ranking, theme, hits.copies FROM hits, (SELECT MAX(ranking) AS ranking, copies FROM rec GROUP BY copies) m WHERE m.copies = hits.copies; Datalog Formulation: Observe that a Datalog equivalent query is neater than its SQL counterpart: ( rec(1,D) :- hits(_E,D) ) /\ ( rec(F,G) :- hits(_H,G), rec(I,J), G<J, F=I+1 ) => hits(B,C), group_by(rec(D,C), [C], A=max(D)).
Outcome: answer(h1.theme:varchar(50),h1.copies:int,pos:int) -> { answer(1,’White Christmas’,50), answer(2,’In the Summertime’,31), answer(3,’Silent Night’,30), answer(4,’My Heart will Go On’,25), answer(4,’Rock Around the Clock’,25), answer(5,’I Will Always Love You’,20), answer(5,’It\’s Now or Never’,20), answer(5,’We Are the World’,20), answer(6,’If I Didn\’t Care’,19) } Info: 9 tuples computed.
Problem Statement: Compute the first prime numbers, where is a natural bound. A Solution: The sieve of Eratosthenes can be expressed in SQL by generating numbers and getting rid of those which can be divided by a lesser number. So, a natural number generator can be defined as a CTE, and then the factors for each number as another CTE. For a number to be a factor of another number it sufices to check that the division remainder is 0. The CTE factor below delivers pairs of , , where is a number and is one of its factors. The outcome selects each for which there is only one factor. /set bound 100 WITH number(n) AS
(SELECT 0 UNION SELECT n+1 FROM number WHERE n < $bound$), factor(x, f) AS (SELECT x.n, f.n FROM number x, number f
WHERE x.n > f.n AND f.n > 0 AND x.n mod f.n = 0) SELECT x FROM (SELECT x, COUNT(*) c FROM factor GROUP BY x) WHERE c=1;
Note that DES includes user variables which can be used as parameters, such as bound in this example, which are set with the command /set Variable Value.
Datalog Formulation: Again, the translation seems to be more compact than the source SQL statement. number(0) /\ ( number(B) :- number(C), C<100, B=C+1 ) /\ ( factor(D,E) :- number(D), number(E), D>E, E>0, 0=D mod E ) => group_by(factor(A,_F), [A], (_G=count,_G=1)). answer(factor.x:int) -> { answer(2), answer(3), answer(5), answer(7), ..., answer(97) } Info: 25 tuples computed.
Problem Statement: Plot the sine function as depicted in the figure below.
A Solution: Here we define two CTE’s: One working on the real plane ( plot) which relates and coordinates via a function (parametrically specified with the user variable f), with square dimensions. The second CTE works on the “pixel" plane (bars) by building a string of spaces with as many spaces as pixels in the ordinates (horizontally represented instead of vertically), which will be truncated to the required length with respect to the value of the function at each coordinate. Observe that strings in the display are quoted and ended with the characters “’),”, so that it visually resembles the plot.
Both plot and bars are built in a similar way natural numbers are defined: a base case with the first point in the plane, and with a single space, respectively. The recursive case of plot adds pairs (x+dx, fx) for coordinates up to its bound, whilst for bars, a space is added up to reaching its top length.
Once both relations are defined, the outcome query truncates (with the function substr: substring) the longest bar up to the value of the corresponding coordinate for each coordinate found in plot. -- Dimension of the plot (d+1) rows and (d+1) columns: /set d 50 -- Start x: /set x0 0.0 -- End x: /set x1 4*pi -- Delta x: /set dx ($x1$-$x0$)/$d$ -- Function: /set f sin(xi) WITH plot(x, fx) AS (SELECT $x0$ xi, $f$
UNION
SELECT x+$dx$ xi, $f$ FROM plot WHERE x <= $x1$), bars(bar) AS (SELECT ’ ’
UNION
SELECT bar||’ ’ FROM bars WHERE length(bar)<$d$) SELECT substr((select max(bar) bar from bars), 1,
round($d$*(fx-(SELECT min(fx) FROM plot))*(SELECT 1/(max(fx)-min(fx)) FROM plot))) FROM plot; Datalog Formulation: The following equivalent Datalog query includes the aggregate predicates max/3 and min/3, which are syntax simplifications for a group_by predicate (e.g., max(R,X,M) ≡ group_by(R,[],M=max(X))). Functions concat(A,B) (concatenation of A and B and written as A||B in standard SQL), length(A) (length of A), and substr(A,P,N) (substring of N characters of A taken from position P) are used.
( plot($x0$,F) :- F=sin($x0$) ) /\ ( plot(B,C) :- plot(D,_E), D=<$x1$, B=D+$dx$, C=sin(D+$dx$) ) /\ bars(’ ’) /\ ( bars(H) :- bars(G), length(G)<$d$, H=concat(G,’ ’) ) => plot(_A,_B), max(bars(_K),_K,_H), min(plot(_L,_M),_M,_C), group_by(plot(_N,_O),[],(_F=1/(max(_O)-min(_O)))),
A=substr(_H,1,round($d$*(_B-_C)*_F)).
Problem Statement: Given the table conversion(c:string, fb:int, tb:int), with natural numbers to be converted (c) from a base (fb) to another base (tb), write an SQL query returning a row for each element in the table conversion, with schema (number_fb, fb, number_tb, tb), such that number_fb is the number in base fb equivalent to the number number_tb in base tb.
A Solution: This problem can be subdivided as usually in two subproblems: Convert to base 10, and then to the target base. We can assume a table digits(n INT, d STRING) containing tuples as { (0,’0’), (1,’1’), . . . , (10,’A’), . . . }.
For converting to base 10, the approach is to recursively generate tuples with the inspected position (index of the digit from right to left starting with 0) with a value corresponding to the number up to its -th position. So, we can think of a schema for this first CTE as to_base_10(c, fb, tb, s, i, n), where original parameters in conversion (c, fb and tb) are kept with their same names, s is the number truncated up to the − 1-th index, i is the index , and n is the value (base 10) for the number c up to the -th position. The original number is required in this schema because there will be in general several numbers to be converted, so that this first column will discriminate the number for which the conversion is made. A similar requirement applies to the original base fb and the target base fb.
For the sake of keeping neat the formulation, the base case for to_base_10 starts at index − 1, and the original number is appended (with the || operator) with a void − 1-th position, delivering a value 0 for it. Otherwise, we could start at index 0, but calculations in the recursive case should be also included in the base case. This recursive case builds tuples from to_base_10(c, fb, tb, s, i, n) itself as follows: its first 3 columns are the original ones, as found in to_base_10. The number s (recall: a string) is right trimmed in 1 character; the index i is incremented, and its quantity (weighted with its position: fb^(i+1)) is added to n, where the value of the digit is taken from the digits table.
Converting a number in base 10 to another base is a somewhat similar problem, but with schema to_base_b(c, fb, tb, n, st): the three original columns (c, fb and tb), the number in base 10 (n) and the most significant digits already processed ( st). Here, the base case comes from the results for the relation to_base_10, selecting the value n for the final calculation (the length of the truncated number is 1: the last, most-significant character in the string). In this case, the index is not used because another approach is taken: dividing the current number by the target base and delivering the digit corresponding to the remainder of the division as the next digit, from the less to the most significant digits. Then, the recursive case builds the outcome by appending the calculated digit to the left of the former outcome.
WITH to_base_10(c, fb, tb, s, i, n) AS (
SELECT c, fb, tb, c || ’ ’, -1, 0 FROM conversion UNION SELECT c, fb, tb, SUBSTR(s,1,LENGTH(s)-1), i+1, integer(n+(SELECT n
FROM digits
WHERE d=SUBSTR(to_base_10.s,LENGTH(to_base_10.s)-1,1) )*fb^(i+1)) FROM to_base_10 WHERE LENGTH(s)>1 ), to_base_b(c, fb, tb, n, st) AS (
SELECT c, fb, tb, n, ’’ FROM to_base_10 WHERE LENGTH(s)=1 UNION SELECT c, fb, tb, n DIV tb,
(SELECT d FROM digits WHERE n=to_base_b.n MOD to_base_b.tb) || st FROM to_base_b WHERE n MOD tb > 0 ) SELECT c AS number_fb, fb AS fb, st AS number_tb, tb AS tb FROM to_base_b WHERE n=0; Datalog Formulation: The Datalog translation is more elaborated than in previous examples (but still, neater than its counterpart SQL formulation).
( to_base_10(E,F,G,H,-1,0) :- conversion(E,F,G), H=concat(E,’ ’) ) /\ ( to_base_10(I,J,K,L,M,N) :to_base_10(I,J,K,O,P,Q), R=length(O), R>1, T=R-1, L=substr(O,1,T), M=P+1, digits(U,V), X=length(O)-1, V=substr(O,X,1), N=integer(Q+U*J**(P+1))) /\ ( to_base_b(Y,Z,AA,AB,’’) :- to_base_10(Y,Z,AA,AC,_AD,AB), length(AC)=1 ) /\ ( to_base_b(AE,AF,AG,AH,AI) :to_base_b(AE,AF,AG,AJ,AK), AJ mod AG>0, AH=AJ div AG, digits(AM,AN), AM=AJ mod AG, AI=concat(AN,AK) ) => to_base_b(A,B,D,0,C).
Problem Statement: Implement a universal Turing machine as a state transition system, following https://aturingmachine.com/. Possible transitions are specified in the input table transitions(state, symbol, newstate, newsymbol, move), and the initial state is given in initial_state(state, tape, pos). Here, state is a numeric value identifying the state, tape is a string containing a sequence of symbols 0’s and 1’s, pos is the position of the scanned symbol (the leftmost character of the tape is always the position 1 even when the tape can can grow indefinitely to the right or to the left), move can be either be ’L’ (to the left) or ’R’ (to the right).
Input Data: The two input tables are filled as shown next to implement a binary counting machine. It counts from 0 upwards without stopping. Inspecting its outcome can be done by adding a stop condition on the number of the transitions (steps).
INSERT INTO initial_state VALUES(0,’ ’,1); -- (0,B) -> (1,B) Left: When a blank (B) is found we change to state 1: INSERT INTO transitions VALUES(0,’ ’,1,’ ’,’L’); -- (0,0) -> (0,0) Right: This state moves the tape to the right most digit: INSERT INTO transitions VALUES(0,’0’,0,’0’,’R’); -- The following transition is not needed: -- (0,1) -> (0,1) Right: This state moves the tape to the right most digit -- (1,B) -> (0,1) Right: If we change a Blank to a 1 we change back to state 0: INSERT INTO transitions VALUES(1,’ ’,0,’1’,’R’); -- (1,0) -> (0,1) Right: If we change a 0 to a 1 we change back to state 0: INSERT INTO transitions VALUES(1,’0’,0,’1’,’R’); -- (1,1) -> (1,0) Left: If we change a 1 to a 0 we keep looking to the left: INSERT INTO transitions VALUES(1,’1’,1,’0’,’L’); A Solution: Implementing a universal Turing machine can be done with a recursive query where the base case contains the initial state, and the recursive case selects the next state in terms of the symbol in the current tape position. This must consider that the tape can grow both the left and to the right. For the last case, the string tape can be concatenated with a new symbol and the index at the first position does not change. For the former case, a new blank symbol is prepended and the index 1 is for this position.
WITH m(state,tape,pos,step) AS (
SELECT state,tape,pos,1 FROM initial_state UNION ALL SELECT -- State t.newstate, -- Tape CASE
WHEN t.move=’L’ AND pos>1 THEN
SUBSTR(tape,1,pos-1)||t.newsymbol||SUBSTR(tape,pos+1) WHEN t.move=’L’ AND pos=1 THEN
’ ’||t.newsymbol||SUBSTR(tape,pos+1) WHEN t.move=’R’ AND LENGTH(tape)=pos THEN
SUBSTR(tape,1,pos-1)||t.newsymbol||’ ’ WHEN t.move=’R’ AND LENGTH(tape)>pos THEN
SUBSTR(tape,1,pos-1)||t.newsymbol||SUBSTR(tape,pos+1) END, -- Move CASE
WHEN t.move=’L’ AND pos>1 THEN pos-1 WHEN t.move=’L’ AND pos=1 THEN 1
WHEN t.move=’R’ THEN pos+1 END, -- Step step+1 FROM transitions t, m WHERE m.state=t.state AND
SUBSTR(m.tape,m.pos,1)=t.symbol -- AND step < $max_step$ -- Use this as a stop condition ) SELECT step,state,pos,tape FROM m; Datalog Formulation: (m(E,F,G,1) :
initial_state(E,F,G)) /\ (m(H,I,J,K) :transitions(L,M,H,N,O), m(L,P,Q,R), ’$substr’(P,Q,1,M), R<40, S=Q-1, ’$substr’(P,1,S,T), ’$concat’(T,N,U), V=Q+1, ’$substr’(P,V,W), ’$concat’(U,W,X), ’$concat’(’ ’,N,Y), Z=Q+1, ’$substr’(P,Z,AA), ’$concat’(Y,AA,AB), AC=Q-1, ’$substr’(P,1,AC,AD), ’$concat’(AD,N,AE), ’$concat’(AE,’ ’,AF), AG=Q-1, ’$substr’(P,1,AG,AH), ’$concat’(AH,N,AI), AJ=Q+1, ’$substr’(P,AJ,AK), ’$concat’(AI,AK,AL), ’$case’([((O=’L’,Q>1),Q-1),((O=’L’,Q=1),1),(O=’R’,Q+1)],null,J), K=R+1, ’$case’([((O=’L’,Q>1),X),((O=’L’,Q=1),AB),((O=’R’,’$length’(P,AM),AM=Q),AF), ((O=’R’,’$length’(P,AN),AN>Q),AL)],null,I)) => m(B,D,C,A).
SQL puzzles for challenging students’ skills have been presented and solved in the DES system, which
has been selected because it helps students with syntax and semantic warnings about SQL queries.
Since the system is based on intuitionistic logic programming, it allows for neater and simpler SQL
formulations to solve those puzzles because SQL queries are translated into a Hypothetical Datalog
program. Both the syntax and the inference system for the Hypothetical Datalog system in [