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.
SQL is usually understood as a specific-purpose, declarative programming language, intended to insert and extract data from relational databases. However, since the addition of recursive common table expressions (CTE, included for the first time in the ISO/IEC Standard SQL:1999, also known as SQL3) its nature has evolved to become a Turing-complete language. To acknowledge this, a specific class of tag systems, CTS's (Cyclic Tag Systems) were proposed in [1], and a corollary of its work was that a CTS can emulate a Turing-complete class of tag systems. Since a CTS can be implemented in standard SQL, 1 this proves that SQL is Turing complete.
This result can be used to pose more advanced problems as puzzles to students with the aim of sharpening their programming skills and promoting open-mindedness. Using puzzles to this end is a well-known technique [2], and in fact they are used all around the world as in the Hour of Code, 2 Programming Praxis, 3 CodeKata, 4 Β‘Acepta el reto! 5 and also specific for SQL [3]. 6 Our experience and student feedback when teaching database concepts to advanced students (typically in the double degree of Computer Science and Mathematics) during last years confirms the usefulness of puzzles as an intellectual challenge posed to students (proposed as extra-curricular activities). This paper collects some of those SQL puzzles, ranging from the easier ones to the more complex and appealing ones. Though SQL can not be considered as an esoteric language [4], expressing these puzzles with this language can be viewed as an esoteric usage.
While these puzzles can be solved in most SQL systems, when teaching we use instead the Datalog Educational System (DES) 7 [5]. This system, which is capable of solving standard SQL queries, is in our view more adequate for students than others because, in particular, it provides better syntax error explanations and even semantic error warnings [6]. Moreover, students can use its SQL declarative debugger [7] for fixing semantically incorrect views. These last two features are absent in commercial SQL systems. Apart from this, DES extends the SQL language beyond the standard, including the
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:
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:
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 [10,11]. However, local (temporary) view definitions as needed to represent the behavior of a WITH clause are not part of a Datalog language, which only allows for non-volatile predicates.
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 π΅ [12], limiting its scope to this proof. A database language based on ILP is Hypothetical Datalog [8], which is extended in [9,13,14] with rules (not only atoms) in such assumptions, a feature that can be leveraged to represent those SQL local view definitions. Next section recalls this feature implemented in the DES system, which also includes essential SQL functionalities such as handling duplicates and aggregates.
The Hypothetical Datalog language in [9] implements a system based on intuitionistic logic programming. Here, its syntax and semantics are extended with conditions in expressions and meta-predicates for supporting common SQL needs: top-π queries (i.e., at most, π solutions to its goal are allowed), aggregates, and expressions in comparison predicates. Next, π£πππ (π ) is the set of variables in π .
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 [12]).
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 [9] with inference rules for comparison operators, top-π and group-by goals. The well-known concepts of predicate dependency graph (PDG) and stratifiable database Ξ [15] are used here (see also page 298 in [9]). Here, the PDG includes a negative arc π Β¬ β π between the head predicate π of a rule and a predicate π in its body, such that π occurs in an argument of a meta-predicate Β¬, π or π’; otherwise, it includes a positive arc π β π. A negative arc π Β¬ β π imposes that π must be solved before π for avoiding non-monotonicity [15]. π π‘π(Ξ, π ) is the stratum corresponding to predicate π in Ξ [9] such that for a positive arc pβq, π π‘π(Ξ, p) β₯ π π‘π(Ξ, q), and for a negative arc p Β¬ βq, π π‘π(Ξ, p) > π π‘π(Ξ, q). Ξ β’ π is an inference expression, where π is an identified ground atom ππ : π΄. Such an ππ is of the form
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.
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.
β’ For any rule π΄ β π 1 β§ . . . β§ π π with identifier ππ in Ξ, where π π‘π(Ξ, ππππ(π΄)) = π and for any ground substitution π:
β’ For any constants π π and expressions π π :
(Expression) where β β {=, <, >, β€, β₯}, and π π π evaluates to π π .
β’ For any atoms π΄, π΄ β² :
(Duplicates) where π΄ = π΄ β² π, πΌ is a single, unique identifier.
β’ For any atoms π΄ π , π΄, natural number π , and ground substitutions π π :
(Top) where π΄ π = π΄π π , πΌ π are at most π single, unique identifiers.
β’ For any atoms π΄ π , π΄, π΅ π , π΅ and ground substitutions π π , π:
(Group-By) where each πΌ π is a unique identifier for each group ππ π π , and π΄ = π΄ π π, π΅ = π΅ π π.
β’ For any goal π:
Example 1. Natural numbers can be specified in this language as follows:
Starting with Ξ = β , and applying the Assumption rule:
Ξ, 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:
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:
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:
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:
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:
and the outcome would be the multiset
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) [16].
Here, the function SQL_to_DL is defined by extending Definition 6 in [9] with top-π queries, aggregates and expressions. This function takes a relation name and an SQL statement as input and returns a multiset of Hypothetical Datalog rules providing the same meaning as the SQL relation for a corresponding predicate with the same name as the relation. From here on: Without loss of expressivity, we assume that a group-by statement includes a relation name in its FROM clause; set-related operators and symbols refer to multisets because SQL relations can contain duplicates; each attribute is qualified by the relation name it corresponds to so that they can be uniquely identified; an empty conjunctive goal is π‘ππ’π; where convenient, variables of goals are made explicit; and for the sake of conciseness, Hypothetical Datalog is simply referred to as Datalog. 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.
where SQLEXPS_to_DL (πΈπ₯ππ ) = (π·πΏπΈπ₯ππ , π·πΏπ΄ππ, πΈπ₯ππ π π’πππ ), SQLREL_to_DL (π ππ) = (π·πΏπ ππ(π ), π πππ π’πππ ). Here, π β π are the variables of the predicate π·πΏπ ππ corresponding to the attributes πΆπππ of the relation π ππ.
where SQLREL_to_DL (π ππ π ) = (π·πΏπ ππ(π π ), π πππ π’πππ π ).
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:
where SQLEXPS_to_DL (πΈπ₯π π ) = (π·πΏπΈπ₯π π , π·πΏπ΄ππ π , πΈπ₯ππ π’πππ π ).
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:
where SQLEXPS_to_DL (πΈπ₯π π ) = ((π π = π·πΏπΈπ₯π π ) β§ π·πΏππ π , π‘ππ’π, πΈπ₯ππ π’πππ π ), 1 β€ π β€ 2, and πππ β² is the Datalog corresponding comparison operator to πππ.
π , πΆπ π’πππ π ), 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:
π(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 [17], which are not presented here. In this case, the resulting translation is simply {π(1.4142)}, as it can be checked in the system by displaying compilations with the command /show_compilations on. Observe also that the system emits the warning for this example: [Sem] Tautological condition: (true OR true), which is one of the results of its semantic analysis [6]
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:
Further simplification and unfolding steps done in the system results in a single rule: {(π(π) β (πππ‘(0)) β§ (πππ‘(π ) β πππ‘(π) β§ π = π + 1) β πππ‘(π))}. β‘
[9] provides a theorem for the semantic equivalence of an SQL relation and its counterpart Datalog translation for a subset of the language presented here. An SQL relation is translated into an extended relational algebra relation (ERA) definition (with SQL_to_ERA ), for which an interpretation for a computed answer in terms of the ERA operators is provided. The Datalog program is interpreted with the unified stratified semantics, which provides the set of axioms β° for the original database Ξ augmented with the translation of the query π to this Datalog program. So, the proof inductively proceeds by strata, and for each stratum by cases, showing the semantic equivalence of the translation from the SQL query π into an ERA expression for a relation π (with SQL_to_ERA ), and the translation of π into a Datalog program (with SQL_to_DL ).
This section provides several SQL puzzles 9 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 [18]. For each puzzle, its problem statement is given, together with an equivalent Datalog formulation, and outcome. A selection of other puzzles can be found in Appendix A.
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: 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: 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. 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.
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
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 [9] have been extended to support expressions in conditions and other meta-predicates needed for expressing SQL more complex queries. The implementation can be greatly enhanced in several ways; for example, replacing its prototype SQL parser with a more performant one, and supporting the semi-naΓ―ve differential optimization [19], which hugely improves performance for recursive problems, and fixing some known issues. Additionally, more puzzles will be developed for the enjoyment of students (and the teacher).
1 https://wiki.postgresql.org/index.php?title=Cyclic_Tag_System&oldid=15106 2 https://hourofcode.com 3 https://programmingpraxis.com 4 http://codekata.com 5 Face the challenge! https://www.aceptaelreto.com 6 SQLzoo https://sqlzoo.net, HackerRank https://www.hackerrank.com/domains/sql 7 Desktop applications for different OS's and Prolog host systems (https://des.sourceforge.io), and an on-line system DESweb (https://desweb.fdi.ucm.es) which includes the last development version are available.
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; Datalog Formulation: 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:
answer(h1.theme:varchar(50),h1.copies:int,pos:int) -> { answer (
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 suffices 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.
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.
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.
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). 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.
(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