Quantcast

SQLite Recursive Common Table Expression suggestion

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

SQLite Recursive Common Table Expression suggestion

Simon Slavin-3
I’ve seen many amusing examples of using Common Table Expressions to solve Sudoko puzzles.  Has anyone tried using one to suggest the best next move for Minesweeper ?  The idea would be to supply a grid with the solution so far in it, and supply the total number of mines, and have SQLite suggest a good next move.

No competition.  No prizes.  No fame.  Just thought some of you might enjoy trying it.

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Clemens Ladisch
Simon Slavin wrote:
> I’ve seen many amusing examples of using Common Table Expressions to
> solve Sudoko puzzles.  Has anyone tried using one to suggest the best
> next move for Minesweeper ?

https://en.wikipedia.org/wiki/Minesweeper_(video_game)#Computational_complexity

> have SQLite suggest a good next move.

Define "good".  ;-)


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Brian Curley
...besides, one might argue that anyone who can programmatically predict
the best route for Minesweeper should actually focus on a tool that
predicted the lottery (or even elections... ;)

What I wonder though is if CTEs could actually serve as a stand-in for the
lack of Dynamic SQL, sort of how triggers can sometimes serve in place of a
procedural language. I have successfully coupled shell scripts and the CLI
but in cases where one is limited to desktop options, this would really be
pretty awesome.

Regards.

Brian P Curley



On Mar 7, 2017 3:46 AM, "Clemens Ladisch" <[hidden email]> wrote:

> Simon Slavin wrote:
> > I’ve seen many amusing examples of using Common Table Expressions to
> > solve Sudoko puzzles.  Has anyone tried using one to suggest the best
> > next move for Minesweeper ?
>
> https://en.wikipedia.org/wiki/Minesweeper_(video_game)#
> Computational_complexity
>
> > have SQLite suggest a good next move.
>
> Define "good".  ;-)
>
>
> Regards,
> Clemens
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Michael Tiernan
On Mar 7, 2017 6:56 AM, "Brian Curley" <[hidden email]> wrote:
> I have successfully coupled shell scripts and the CLI

I'd love to see examples of this sort of use case and I suspect that
there's others who would benefit from seeing how others approach solving
some of the common problems.

Does anyone know where knowledge like this is shared? (Specifically aimed
towards users of SQLite?)
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Clemens Ladisch
In reply to this post by Brian Curley
Brian Curley wrote:
> What I wonder though is if CTEs could actually serve as a stand-in for the
> lack of Dynamic SQL

Recursive CTEs make SQL Turing complete.

But they cannot do everything.  For example, when you want to do a pivot
operation, the number of columns is determined by the data, and you
cannot construct and execute that query only from within SQLite.


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Brian Curley
In reply to this post by Michael Tiernan
Reached back into the tape storage in my head for this one, but to
paraphrase a movie older than me: the future is in pipes.

   http://souptonuts.sourceforge.net/readme_sqlite_tutorial.html

Note that DRH likes to mention that SQLite is meant to replace fopen() more
than a full-bore RBDMS, but I think that the CLI is often overlooked. You
can use it ad hoc, or in tandem with existing DBs, just like you can stream
data to the shell for other commercial products, like sqlplus.

There is quite a bit out there.

Regards.

Brian P Curley



On Mar 7, 2017 7:04 AM, "Michael Tiernan" <[hidden email]> wrote:

> On Mar 7, 2017 6:56 AM, "Brian Curley" <[hidden email]> wrote:
> > I have successfully coupled shell scripts and the CLI
>
> I'd love to see examples of this sort of use case and I suspect that
> there's others who would benefit from seeing how others approach solving
> some of the common problems.
>
> Does anyone know where knowledge like this is shared? (Specifically aimed
> towards users of SQLite?)
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Brian Curley
In reply to this post by Clemens Ladisch
Maybe so. Even simpler recursion doesn't get executed, such as a quick poll
of the sqlite_master table to trigger a system-wide count(*) of all tables
isn't allowed, so it seems that it's held at the gate. Even if I mock up a
transaction or a thorough UNION set through a view, I need to output it
just to read in as an update.

Regards.

Brian P Curley



On Mar 7, 2017 7:30 AM, "Clemens Ladisch" <[hidden email]> wrote:

> Brian Curley wrote:
> > What I wonder though is if CTEs could actually serve as a stand-in for
> the
> > lack of Dynamic SQL
>
> Recursive CTEs make SQL Turing complete.
>
> But they cannot do everything.  For example, when you want to do a pivot
> operation, the number of columns is determined by the data, and you
> cannot construct and execute that query only from within SQLite.
>
>
> Regards,
> Clemens
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

James K. Lowden
In reply to this post by Clemens Ladisch
On Tue, 7 Mar 2017 13:30:00 +0100
Clemens Ladisch <[hidden email]> wrote:

> Recursive CTEs make SQL Turing complete.
>
> But they cannot do everything.

Isn't that a contradiction?  

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Clemens Ladisch
James K. Lowden wrote:
> Clemens Ladisch <[hidden email]> wrote:
>> Recursive CTEs make SQL Turing complete.
>>
>> But they cannot do everything.
>
> Isn't that a contradiction?

Being able to emulate a Turing machine (or a register machine) means
that there exists _some_ representation of the data, but not that it has
the form you actually want.  To get back to the pivot example: if I want
multiple columns, what use are thousands of rows that encode the Turing
machine's tape?


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

James K. Lowden
On Tue, 7 Mar 2017 20:26:41 +0100
Clemens Ladisch <[hidden email]> wrote:

> James K. Lowden wrote:
> > Clemens Ladisch <[hidden email]> wrote:
> >> Recursive CTEs make SQL Turing complete.
> >>
> >> But they cannot do everything.
> >
> > Isn't that a contradiction?
>
> Being able to emulate a Turing machine (or a register machine) means
> that there exists _some_ representation of the data, but not that it
> has the form you actually want.  To get back to the pivot example: if
> I want multiple columns, what use are thousands of rows that encode
> the Turing machine's tape?

I don't know.  It's popular nowadays to posit that recursion makes SQL
Turing-complete.  While I accept any loop can be expressed as
recursion, I cannot envision your pivot-table query without some form
of dynamic SQL.  How else to provide to the interpreter the names of
the output columns?  

--jkl

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

petern
In reply to this post by Clemens Ladisch
Further to sqlite pivot function, matrix functions, or any other result set
meta query language feature, I commented about this before with a concrete
suggestion.  The core problem is the awkward complexity of building a
completely general virtual table (vtab) based eval("<sql>") or
meta("<sql>") which communicates correctly with the query optimizer.

Things have changed somewhat since I wrote those comments.  After the
introduction of row values in 3.15 https://www.sqlite.org/rowvalue.html ,
at least, now the sqlite ecosystem can cope with efficient vector valued
data for passing parameters into and out of the hypothetical eval() or
meta() vtab module.  Presumably there are more pleasant surprises like
rowvalues on the horizon?

Has anyone put thought into how completely general sqlite sql strings could
be executed with full optimizer support within vtab code so the properties
of the resulting rowset can be exposed in the result columns returning from
the desired vtab module?

Just a thought.  Looking forward to the dazzling thread of replies!










On Tue, Mar 7, 2017 at 11:26 AM, Clemens Ladisch <[hidden email]> wrote:

> James K. Lowden wrote:
> > Clemens Ladisch <[hidden email]> wrote:
> >> Recursive CTEs make SQL Turing complete.
> >>
> >> But they cannot do everything.
> >
> > Isn't that a contradiction?
>
> Being able to emulate a Turing machine (or a register machine) means
> that there exists _some_ representation of the data, but not that it has
> the form you actually want.  To get back to the pivot example: if I want
> multiple columns, what use are thousands of rows that encode the Turing
> machine's tape?
>
>
> Regards,
> Clemens
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

Dominique Devienne
On Wed, Mar 8, 2017 at 3:47 AM, petern <[hidden email]> wrote:

> Things have changed somewhat since I wrote those comments.  After the
> introduction of row values in 3.15 https://www.sqlite.org/rowvalue.html ,
> at least, now the sqlite ecosystem can cope with efficient vector valued
> data for passing parameters into and out of the hypothetical eval() or
> meta() vtab module.
>

How so? There are zero API functions taking or returning "row values",
which is currently a pure SQL abstraction, and not a "physical" vector
of values you can manipulate.

You can create an eval() function now, via an eponymous vtable IMHO [1].
it just won't participate in the outer query plan, of course. --DD

[1] https://www.sqlite.org/vtab.html#eponymous_virtual_tables
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: SQLite Recursive Common Table Expression suggestion

petern
Yes, but we can live and hope for the day a sqlite project roadmap is
disclosed with eponymous vtab API which supports completely dynamic column
outputs and a fully featured API for row valued language atoms.

When that day comes pivot tables, matrix operations, and other row type
introspection computations will be trivial to implement.   This strategy
would be far superior to the ad hoc SQL syntax additions used by other
engines to support, for example, the very useful pivot table primitive.

In the meantime I was hoping to find out if anybody had some clever ideas
about how to shoehorn in a workable albeit opaque eval("<sql>") which
somehow communicates to the outer context the missing and vital information
about dynamic type of row along with the results.

Consider the following strategy for implementing pivot table.

There already exists an eval("<sql>") extension function:  File
ext/misc/eval.c <http://www.sqlite.org/src/finfo?name=ext/misc/eval.c>
which returns a string value.  Multiple invocations of this function could
be used to compute the output dimensions and column names of an arbitrary
query.

What's missing is a complementary operation which outputs a table of column
names and types for an arbitrary SQL query.  Call this eponymous function
columnsof("<sql>")

By combining those two operations, it would be possible to natively compute
within sqlite a generalized pivot table which, for output at least, look
right.

The final missing ingredient would be an eponymous function, call it
tableof("<csv>") which can transform a well formed CSV string pivot table
from the previous step into a fully fledged table object with the correct
number and type of columns from the CSV string.


On Wed, Mar 8, 2017 at 12:09 AM, Dominique Devienne <[hidden email]>
wrote:

> On Wed, Mar 8, 2017 at 3:47 AM, petern <[hidden email]>
> wrote:
>
> > Things have changed somewhat since I wrote those comments.  After the
> > introduction of row values in 3.15 https://www.sqlite.org/rowvalue.html
> ,
> > at least, now the sqlite ecosystem can cope with efficient vector valued
> > data for passing parameters into and out of the hypothetical eval() or
> > meta() vtab module.
> >
>
> How so? There are zero API functions taking or returning "row values",
> which is currently a pure SQL abstraction, and not a "physical" vector
> of values you can manipulate.
>
> You can create an eval() function now, via an eponymous vtable IMHO [1].
> it just won't participate in the outer query plan, of course. --DD
>
> [1] https://www.sqlite.org/vtab.html#eponymous_virtual_tables
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Loading...