Merge branch 'mob'

[arxana.git] / latex / arxana-reboot-backend.tex

\section{SQL tables} \label{sql-code}

\begin{notate}{Objects and codes} \label{objects-and-codes}
Every object in the system is identified by an ordered
pair: a \emph{code} and a \emph{reference}.  The codes say
which table contains the indicated object, and references
provide that object's id.  To a specific element of a list
or n-tuple, a third number, that element's \emph{offset},
is required.  The codes are as follows:

\begin{center}
\begin{tabular}{|l|l|}
\hline
0 & list \\ \hline
1 & string \\ \hline
2 & pair \\ \hline
3 & triple \\ \hline
\end{tabular}
\end{center}
\end{notate}

\begin{idea}
CREATE TABLE strings (
   id SERIAL PRIMARY KEY,
   text TEXT NOT NULL UNIQUE
);

CREATE TABLE pairs (
   id SERIAL PRIMARY KEY,
   code1 INT NOT NULL,
   ref1 INT NOT NULL,
   code2 INT NOT NULL,
   ref2 INT NOT NULL,
   UNIQUE (code1, ref1,
           code2, ref2)
);

CREATE TABLE triples (
   id SERIAL PRIMARY KEY,
   code1 INT NOT NULL,
   ref1 INT NOT NULL,
   code2 INT NOT NULL,
   ref2 INT NOT NULL,
   code3 INT NOT NULL,
   ref3 INT NOT NULL,
   UNIQUE (code1, ref1,
           code2, ref2,
           code3, ref3)
);
\end{idea}

\begin{notate}{A list of lists}\label{models-of-theories}
As a central place to manage our collections, we first
create a list of lists.  The `heading' is the list's name,
and its `header' is metadata.
\end{notate}

\begin{idea}
CREATE TABLE lists (
  id SERIAL PRIMARY KEY,
  heading REFERENCES strings(id) UNIQUE,
  header REFERENCES strings(id) 
);
\end{idea}

\begin{notate}{Lists on demand}\label{models-of-theories}
Whenever we want to create a new list, we first add to the
`lists' table, and then create a new table ``listk''
(where k is equal to the new maximum id on `lists').
\end{notate}

\begin{idea}
CREATE TABLE listk (
   offset SERIAL PRIMARY KEY,
   code INT NOT NULL,
   ref INT NOT NULL
);
\end{idea}

\begin{notate}{Side-note on containers via triples}  \label{containers-using-triples}
To model a basic container, we can just use triples like
``(A in B)''.  This is useful, but the elements of B are
of course unordered.  In Section \ref{importing}, we make
extensive use of triples like (B 1 $\alpha$), (B 2
$\beta$), etc., to indicate that B's first component is
$\alpha$, second component is $\beta$, and so on; so we
can make ordered list-like containers as well.

This is an example of the difference in expressive power
of tags (which only provide a sense of unordered
containment in ``virtual baskets'') and triples (which
here are seen to at least provide the additional sense of
ordered containment in ``virtual filing cabinets'',
although they have much more in store for us); cf. Note
\ref{prog-lit-review}.

As useful as models based on these two principles are in
principle, the user could easily be overloaded by looking
at lots of different containers encoded in raw triples,
all at once.
\end{notate}

\begin{notate}{Sense of containment}
Note that every element of a list is in the list in the
same ``sense'' -- for example, we can't instantly
distinguish elements that are ``halfway in'' from those
that are ``all the way in'', the same way we could with
pure triples.
\end{notate}

%% \begin{notate}{References into theories}
%% Since at the moment we have less than 10 basic codes, we
%% can uniquely reference contents of theory $k$ with ordered
%% pairs $10k+\mathit{basic\ code}$ and $\mathit{reference}$.
%% \end{notate}

\begin{notate}{Uniqueness of strings and triples} \label{unique-things}
An attempt to create a duplicate contents in a string or
triple generates a warning.  This saves storage, given
possible repetitive use -- and avoids confusion.  We can,
however, reference duplicate ``copies'' on the lists.
\end{notate}

\begin{notate}{Change} \label{change}
Notice also that since neither strings nor triples
``change'', we have to account for change in other ways.
In particular, the contents of lists can change.  (We may
subsequently add some metadata to certain lists are
``locked'', or indicate that they can only be changed by
adding, etc., so that their contents can be cited stably
and reliably.)
\end{notate}

%% \begin{notate}{Each place contains one object} \label{places}
%% It is obvious from the table definition that I want each
%% place to contain precisely one thing; perhaps it is less
%% obvious why I want to use a database table to maintain
%% this relationship between ``places'' and ``things''.  This
%% is largely a matter of convenience, but in particular it
%% makes it easy for places to change.
%% \end{notate}

\begin{notate}{Provenance and other metadata} \label{provenance}
We could of course add much more structure to the
database, starting with simple adjustments like adding
provenance metadata or versioning into the records for
each stored thing.  For the time being, I assume that such
metadata will appear in the application or content layer,
as triples.  (The exception are the ``headings'' and
``headers'' associated with lists.)
\end{notate}

\section{Common Lisp-side}

\subsection{Preliminaries}

\subsubsection*{System definition}

\begin{common}{arxana.asd}
(defsystem "arxana"
    :version "1"
    :author "Joe Corneli <holtzermann17@gmail.com>"
    :licence "Public Domain"
    :components
    ((:file "packages")
     (:file "utilities" :depends-on ("packages"))
     (:file "database" :depends-on ("utilities"))
     (:file "queries" :depends-on ("packages"))))
\end{common}

\subsubsection*{Package definition}

\begin{common}{packages.lisp}
(defpackage :arxana
  (:use #:cl #:clsql #:clsql-sys))
\end{common}

\subsubsection*{Utilities}

\begin{notate}{Useful things} \label{useful}
These definitions are either necessary or useful for
working the database and manipulating triple-centric
and/or theory-situated data.  The implementation of
theories given here is inspired by Lisp's streams.  This
is perhaps the most gnarly part of the code; the pay-off
of doing things the way we do them here is that
subsequently theories can sit ``transparently'' over other
structures.
\end{notate}

\begin{common}{utilities.lisp}
(in-package arxana)
(locally-enable-sql-reader-syntax)

;; (defun connect-to-database ()
;;    (connect `("localhost" "joe" "joe" "")
;;             :database-type :postgresql-socket))

(defun connect-to-database ()
   (connect `("localhost" "joe" "joe" "joe")
            :database-type :mysql))

(defmacro select-one (&rest args)
  `(car (select ,@args :flatp t)))

(defmacro select-flat (&rest args)
  `(select ,@args :flatp t))

(defun resolve-ambiguity (stuff)
  (first stuff))

(defun isolate-components (content i j)
  (list (nth (1- i) content)
        (nth (1- j) content)))

(defun isolate-beginning (triple)
  (isolate-components (cdr triple) 1 2))

(defun isolate-middle (triple)
  (isolate-components (cdr triple) 3 4))

(defun isolate-end (triple)
  (isolate-components (cdr triple) 5 6))

(defvar *read-from-heading* nil)

(defvar *write-to-heading* nil)
\end{common}

\begin{notate}{On `datatype'}
Just translate coordinates into their primary dimension.
(How should this change to accomodate codes 4, 5, 6,
possibly etc.?)
\end{notate}

\begin{common}{utilities.lisp}
(defun datatype (data)
  (cond ((eq (car data) 0)
         "strings")
        ((eq (car data) 1)
         "places")
        ((eq (car data) 2)
         "triples")
        ((eq (car data) 3)
         "theories")))

(locally-disable-sql-reader-syntax)
\end{common}

\begin{notate}{Resolving ambiguity}
Often it will eventuate that there will be more than one
item returned when we are only truly prepared to deal with
one item.  In order to handle this sort of ambiguity, it
would be great to have either a non-interactive notifier
that says that some ambiguity has been dealt with, or an
interactive tool that will let the user decide which of
the ambiguous options to choose from.  For now, we provide
the simplest non-interactive tool: just choose the first
item from a possibly ambiguous list of items.
\end{notate}

\begin{notate}{Using a different database}
See Note \ref{backend-variant} for instructions on changes
you will want to make if you use a different database.
\end{notate}

\begin{notate}{Use of the ``count'' function}
The SQL count function is thought to be inefficient with
some backends; workarounds exist.  (And it's considered to
be efficient with MySQL.)
\end{notate}

\begin{notate}{Abstraction} \label{abstraction}
While it might be in some ways ``nice'' to allow people to
chain together ever-more-abstract references to elements
from other theories, I actually think it is better to
demand that there just be \emph{one} layer of abstraction
(since we can then quickly translate back and forth,
rather than running through a chain of translations).

This does not imply that we cannot have a theory
superimposed over another theory (or over multiple
theories) that draws input from throughout a massively
distributed interlaced system -- rather, just that we
assume we will need to translate to ``base coordinates''
when building such structures.  However, we'll certainly
want to explore the possibilities for running links
between theories (abstractly similar in some sense to
pointing at a component of a triple, but here there's no
uniform beg, mid, end scheme to refer to).
\end{notate}

\subsection{Main table definitions}

\begin{notate}{Defining tables from within Lisp}
This is Lisp code to define the permanent SQL tables
described in Section \ref{sql-code}.
\end{notate}

\begin{common}{tabledefs.lisp}
;; (execute-command "CREATE TABLE strings (
;;    id SERIAL PRIMARY KEY,
;;    text TEXT NOT NULL UNIQUE
;; );")

(execute-command "CREATE TABLE strings (
   id SERIAL PRIMARY KEY,
   text TEXT,
   UNIQUE INDEX (text(255))
);")

(execute-command "CREATE TABLE places (
   id SERIAL PRIMARY KEY,
   code INT NOT NULL,
   ref INT NOT NULL
);")

(execute-command "CREATE TABLE triples (
   id SERIAL PRIMARY KEY,
   code1 INT NOT NULL,
   ref1 INT NOT NULL,
   code2 INT NOT NULL,
   ref2 INT NOT NULL,
   code3 INT NOT NULL,
   ref3 INT NOT NULL,
   UNIQUE (code1, ref1,
           code2, ref2,
           code3, ref3)
);")

(execute-command "CREATE TABLE theories (
  id SERIAL PRIMARY KEY,
  name INT UNIQUE REFERENCES strings(id)
);")
\end{common}

\begin{notate}{Eliminating and tables}
In case you ever need to redefine these tables, you can
run code like this first, to delete the existing copies.
(Additional tables are added whenever a theory is created;
code for deleting theories or their contents will appear
in Section \ref{processing-theories}.)
\end{notate}

\begin{idea}
(dolist (view (list-views)) (drop-view view))
(execute-command "DROP TABLE strings")
(execute-command "DROP TABLE triples")
(execute-command "DROP TABLE places")
(execute-command "DROP TABLE theories")
\end{idea}

\subsection{Modifying the database}

\begin{common}{database.lisp}
(in-package arxana)
(locally-enable-sql-reader-syntax)
\end{common}

\subsection*{Processing strings}

\begin{notate}{On `string-to-id'}
Return the id of `text', if present, otherwise nil.

There was a segmentation fault with clisp here at one
point, maybe because I hadn't gotten the clsql sql reader
syntax loaded up properly.  Note that calling the code
without the function wrapper did not produce the same
segfault.
\end{notate}

\begin{common}{database.lisp}
(defun string-to-id (text)
  (select [id]
          :from [strings]
          :where [= [text] text]))
\end{common}

\begin{notate}{On `add-string'} \label{add-string}
Add the argument `text' to the list of strings.  If the string
is successfully created, its coordinates are returned.
Otherwise, and in particular, if the request was to create
a duplicate, nil is returned.

Should this give a message ``Adding \meta{text} to the
strings table'' when the string is added by an indirecto
function call, such as through `massage'?
(Note \ref{massage}.)
\end{notate}

\begin{common}{database.lisp}
(defun add-string (text)
  (handler-case
   (progn (insert :into [strings]
                  :attributes '(text)
                  :values `(,text))
          `(1 ,(string-to-id text)))
   (sql-database-data-error ()
     (warn "\"~a\" already exists."
           text))))
\end{common}

\begin{notate}{Error handling bug}
The function `add-string' (Note \ref{add-string}) exhibits
the first of several error handling calls designed to
ensure uniqueness (Note \ref{unique-things}).
Experimentally, this works, but I'm observing that, at
least sometimes, if the user tries to add an item that's
already present in the database, the index tied to the
associated table increases even though the item isn't
added.  This is annoying.  I haven't checked whether this
happens on all possible installations of the underlying
software.
\end{notate}

\subsection*{Parsing general input}

\begin{notate}{On `massage'} \label{massage}
User input to functions like `add-triple' and so on and so
forth can be strings, integers (which the function
``serializes'' as the string versions of themselves), or
as \emph{coordinates} -- lists of the form (code ref).
This function converts all of these input forms into the
last one!  It takes an optional argument `addstr' which,
if supplied, says to add string data to the database if it
wasn't there already.
\end{notate}

\begin{common}{database.lisp}
(defun massage (data &optional addstr)
  (cond
   ((integerp data)
    (massage (format nil "~a" data) addstr))
   ((stringp data)
    (let ((id (string-to-id data)))
      (if id
          (list 0 id)
          (when addstr
            (add-string data)))))
   ((and (listp data)
         (equal (length data) 2))
    data)
   (t nil)))
\end{common}


\subsection*{Processing triples}

\begin{notate}{On `triple-to-id'}
Return the id of the triple (beg mid end),
if present, otherwise nil.
\end{notate}

\begin{common}{database.lisp}
(defun triple-to-id (beg mid end)
  (let ((b (massage beg))
        (m (massage mid))
        (e (massage end)))
    (select [id]
            :from [triples]
            :where [and [= [code1] (first b)]
                        [= [ref1] (second b)]
                        [= [code2] (first m)]
                        [= [ref2] (second m)]
                        [= [code3] (first e)]
                        [= [ref3] (second e)]])))
\end{common}

\begin{notate}{On `add-triple'} \label{add-triple}
Elements of triples are parsed by `massage'
(Note \ref{massage}).  If the triple
is successfully created, its coordinates are returned.
Otherwise, and in particular, if the request was to create
a duplicate, nil is returned.
\end{notate}

\begin{common}{database.lisp}
(defun add-triple (beg mid end)
  "Add a triple comprised of BEG MID and END."
  (let ((b (massage beg t))
        (m (massage mid t))
        (e (massage end t)))
    (when (and b m e)
      (handler-case
       (progn
         (insert-records
          :into [triples] :attributes '(code1 ref1
                                        code2 ref2
                                        code3 ref3)
          :values `(,(first b) ,(second b)
                    ,(first m) ,(second m)
                    ,(first e) ,(second e)))
         `(2 ,(triple-to-id b m e)))
       (sql-database-data-error ()
         (warn "\"~a\" already entered as [~a ~a ~a]."
               (list beg mid end) b m e))))))
\end{common}

\subsection*{Processing theories} \label{processing-theories}

\begin{notate}{Things to do with theories}
For the record, we want to be able to create a theory, add
elements to that theory, remove or change elements in the
theory, and, for convenience, zap everything in a theory.
Perhaps we will also want functions to remove the tables
associated with a theory as well, swap the position of two
theories, or change the name of a theory.  We will also
want to be able to export and import theories, so they can
be ``beamed'' between installations.  At appropriate
places in the Emacs interface, we'll need to set
`*write-to-heading*' and `*read-from-heading*'.
\end{notate}

\begin{notate}{What can go in a theory} \label{what-can-go-in}
Notice that there is no rule that says that a triple or
place that's part of a theory needs to point only at
strings that are in the same theory.
\end{notate}

\begin{notate}{On `list-to-id'}
Return the id of the theory with given `heading', if present,
otherwise, nil.
\end{notate}

\begin{common}{database.lisp}
(defun list-to-id (heading)
  (let ((string-id (string-to-id heading)))
    (select [id]
            :from [lists]
            :where [= [heading] string-id])))
\end{common}

\begin{notate}{On `add-theory'} \label{add-theory}
Add a theory to the theories table, and all the new
dimensions of the frame that comprise this theory.
(Theories have names that are strings -- it seems a
little funny to always have to translate submitted
strings to ids for lookup, but this is what we do.)
\end{notate}

\begin{common}{database.lisp}
(defun add-list (heading)
  (let ((string-id (second (massage heading t))))
    (handler-case
        (progn (insert :into [lists]
                       :attributes '(heading)
                       :values `(,string-id))
               (let ((k (theory-to-id heading)))
                 (execute-command
                  (format nil "CREATE TABLE lists~A (
   offset SERIAL PRIMARY KEY,
   code INT NOT NULL,
   ref INT NOT NULL
);" k))
                 `(0 ,k)))
      (sql-database-data-error
          ()
        (warn "The list \"~a\" already exists."
              heading)))))
\end{common}

\begin{notate}{On `get-lists'}
Find all lists that contain `symbol'.
\end{notate}

\begin{common}{database.lisp}
(defun get-lists (symbol)
  (let* ((data (massage symbol))
         (type (datatype data))
         (id (second data))
         (n (caar
             (query "select count(*) from lists")))
         results)
    (loop for k from 1 upto n
          do (let ((present
                    (query (concatenate
                            'string
                            "select offset from list"
                            (format nil "~A" k)
                            " where ((code = "
                            (format nil "~A" type)
                            ") and (ref = "
                            (format nil "~A" id)
                            "))"))))
               (when present
                 ;; bit of a problem if there are multiple
                 ;; entries of that item on the given
                 ;; list.
                 (setq results (cons (list 0 k present)
                                     results)))))
    results))
\end{common}

\begin{notate}{On `save-to-list'}
Record `symbol' on list named `name'.
\end{notate}

\begin{common}{database.lisp}
(defun save-to-list (symbol name)
  (let* ((data (massage symbol t))
         (type (datatype data))
         (string-id (string-to-id name))
         (k (select-one [id]
                        :from [lists]
                        :where [= [name] string-id]))
         (tablek (concatenate 'string
                              type (format nil "~A" k))))
    (insert-records :into (sql-expression :table tablek)
                    :attributes '(id)
                    :values `(,(second data)))))
\end{common}

\subsection*{Lookup by id or coordinates}

\begin{notate}{The data format that's best for Lisp} \label{what-is-best-for-lisp}
It is a reasonable question to ask whether or not the an
item's id should be considered part of that item's
defining data when that data is no longer in the database.
For the functions defined here, the id is an input, and so
by default I'm not including it in the output here,
because it is already known.  However, for functions like
`triples-given-beginning' (See Note
\ref{graph-like-data}), the id is \emph{not} part of the
known data, and so it is returned.  Therefore I am
providing the `retain-id' flag here, for cases where
output should be consistent with that of these other
functions.
\end{notate}

\begin{common}{database.lisp}
(defun string-lookup (id &optional retain-id)
  (let ((ret (select [text]
                     :from [strings]
                     :where [= [id] id])))
    (if retain-id
        (list id ret)
        ret)))

(defun triple-lookup (id &optional retain-id)
  (let ((ret (select [code1] [ref1]
                     [code2] [ref2]
                     [code3] [ref3]
                     :from [triples]
                     :where [= [id] id])))
    (if retain-id
        (cons id ret)
        ret)))

(defun list-lookup (id &optional retain-id)
  (let ((ret (select [name]
                     :from [lists]
                     :where [= [id] id])))
    (if retain-id
        (list id ret)
        ret)))
\end{common}

\begin{notate}{Succinct idioms for following pointers}
Here are some variants on the functions above which save
us from needing to extract the id of the item from its
coordinates.
\end{notate}

\begin{common}{database.lisp}
(defun string-contents (coords)
  (string-lookup (second coords)))

(defun place-contents (coords)
  (place-lookup (second coords)))

(defun triple-contents (coords)
  (triple-lookup (second coords)))
\end{common}

\begin{notate}{Switchboard} \label{switchboard}
Even more succinctly, one function that can get
the object indicated by any set of coordinates.
\end{notate}

\begin{common}{database.lisp}
(defun switchboard (coords)
  (cond ((eq (first coords) 0)
         (string-contents coords))
        ((eq (first coords) 1)
         (place-contents coords))
        ((eq (first coords) 2)
         (triple-contents coords))))
\end{common}

\begin{notate}{Anti-pasti}
The readability of this code could perhaps be improved if
we used functions like `switchboard' more frequently.
(More to the point, it seems it's not currently used.)  In
particular, it would be nice if we could sweep idioms like
\verb+`(2 ,(car triple))+ under the rug.
\end{notate}

\begin{common}{database.lisp}
(locally-disable-sql-reader-syntax)
\end{common}

\subsection{Queries} \label{queries}

\begin{notate}{The use of views} \label{use-of-views}
It is easy enough to select those triples which match
simple data, e.g., those triples which have the same
beginning, middle, or end, or any combination of these.
It is a little more complicated to find items that match
criteria specified by several different triples; for
example, to \emph{find all the books by Arthur C. Clarke
  that are also works of fiction}.

Suppose our collection of triples contains a portion as
follows:
\begin{center}
\begin{tabular}{lll}
Profiles of the Future & is a & book \\ 2001: A Space
Odyssey & is a & book \\ Ender's Game & is a & book
\\ Profiles of the Future & has genre & non-fiction
\\ 2001: A Space Odyssey & has genre & fiction \\ Ender's
Game & has genre & fiction \\ Profiles of the Future & has
author & Arthur C. Clarke \\ 2001: A Space Odyssey & has
author & Arthur C. Clarke \\ Ender's Game & has author &
Orson Scott Card
\end{tabular}
\end{center}

One way to solve the given problem would be to find those
items that \emph{are written by Arthur C. Clarke} (* ``has
author'' and ``Arthur C. Clarke''), that \emph{are books}
(* ``is a'' ``book''), and \emph{that are classified as
  fiction} (* ``has genre'' ``fiction'').  We are looking
for items that match \emph{all} of these conditions.

Our implementation strategy is: collect the items matching
each criterion into a view, then join these views.  (See
the function `satisfy-conditions'
\ref{satisfy-conditions}.)

If we end up working with large queries and a lot of data,
this use of views may not be an efficient way to go -- but
we'll cross that bridge when we come to it.
\end{notate}

\begin{notate}{Search queries}
In Note \ref{sphinx-setup} et seq., we give some
instructions on how to set up the Sphinx search engine to
work with Arxana.  However, a much tighter integration of
Sphinx into Arxana is possible, and will be coming soon.
\end{notate}

\begin{common}{queries.lisp}
(in-package arxana)
(locally-enable-sql-reader-syntax)
\end{common}

\subsection*{Printing}

\begin{notate}{On `print-system-object'} \label{print-system-object}
The function `print-system-object' bears some resemblance
to `massage', but is for printing instead,
and therefor has to be recursive (because triples and
places can point to other system objects, printing can be
a long and drawn out ordeal).
\end{notate}

\begin{common}{queries.lisp}
(defun print-system-object (data &optional components)
  (cond
    ;; just return strings
    ((stringp data)
     data)
    ;; printing from coordinates (code, ref)
    ((and (listp data)
          (equal (length data) 2))
     ;; we'll need some hack to deal with
     ;; elements-of-theories, which, right now, are two
     ;; elements long but are not (code, ref) pairs but
     ;; rather (local_id, ref) pairs, or maybe actually if
     ;; we take context into consideration, they're
     ;; actually (k, table, local_id, ref) quadruplets.
     ;; Obviously with *that* data we can translate to
     ;; (code, ref).  On the other hand, if we *don't*
     ;; take it into consideration, we probably can't do
     ;; much of anything.  So we should be careful to be
     ;; aware of just what sort of information we're
     ;; passing around.
     (cond ((equal (first data) 0)
            (string-lookup (second data)))
           ((equal (first data) 1)
            (print-system-object
             (place-lookup (second data) t)))
           ((equal (first data) 2)
            (let ((triple (triple-lookup (second data) t)))
              (if components
                  (list
                   (print-beginning triple)
                   (print-middle triple)
                   (print-end triple))
                  (concatenate
                   'string
                   (format nil "T~a[" (second data))
                   (print-beginning triple) "."
                   (print-middle triple) "."
                   (print-end triple) "]"))))
           ((equal (first data) 3)
            (concatenate 'string "List printing not implemented yet."))))
    ;; place
    ((and (listp data)
          (equal (length data) 3))
     (concatenate 'string
                  (format nil "P~a|" (first data))
                  (print-system-object (cdr data)) "|"))
    ;; triple
    ((and (listp data)
          (equal (length data) 7))
      (if components
          (list
           (print-beginning data)
           (print-middle data)
           (print-end data))
          (concatenate
           'string
           (format nil "T~a[" (first data))
           (print-beginning data) "."
           (print-middle data) "."
           (print-end data) "]")))
    (t nil)))

(defun print-beginning (triple)
  (print-system-object (isolate-beginning triple)))

(defun print-middle (triple)
  (print-system-object (isolate-middle triple)))

(defun print-end (triple)
  (print-system-object (isolate-end triple)))
\end{common}

\begin{notate}{Depth}
If we are going to have complicated recursive references,
our printer, and anything else that gives the system some
semantics, should come with some sort of ``layers'' switch
that can be used to limit the amount of recursion we do in
any given computation.
\end{notate}

\begin{notate}{Printing objects as they appear in Lisp} \label{printing-objects-in-lisp}
With the following functions we provide facilities for
printing an object, either from its id or from the
expanded form of the data that represents it in Lisp.
(This is one good reason to have one standard form for
this data; compare Note \ref{what-is-best-for-lisp}.
These functions assume that the id \emph{is} part of
what's printed, so if using functions like `triple-lookup'
to retrieve data for printing, you'll have to graft the id
back on before printing with these functions.)
\end{notate}

\begin{notate}{Printing theories}
We'll want to both print all of the content of a theory,
and print \emph{from} the theory in a more limited way.
(Perhaps we get the second item for free, already?)
\end{notate}

\begin{common}{queries.lisp}
(defun print-string (string &optional components)
  (print-system-object string components))

(defun print-place (place &optional components)
  (print-system-object place components))

(defun print-triple (triple &optional components)
  (print-system-object triple components))

(defun print-string-from-id (id &optional components)
  (print-system-object (list 0 id) components))

(defun print-place-from-id (id &optional components)
  (print-system-object (list 1 id) components))

(defun print-triple-from-id (id &optional components)
  (print-system-object (list 2 id) components))
\end{common}

\begin{notate}{Printing some stuff but not other stuff} \label{printing-some}
These functions are good for printing lists as come out of
the database.  See Note \ref{strings-and-ids} on printing
strings.
\end{notate}

\begin{common}{queries.lisp}
(defun print-strings (strings)
  (mapcar 'second strings))

(defun print-places (places &optional components)
  (mapcar (lambda (item)
             (print-system-object item components))
  places))

(defun print-triples (triples &optional components)
 (mapcar (lambda (item)
             (print-system-object item components))
             triples))

(defun print-theories (theories &optional components)
 (mapcar (lambda (item)
             (print-system-object item components))
             theories))
\end{common}

\begin{notate}{Printing everything in each table} \label{printing-everything}
These functions collect human-readable versions of
everything in each table.  Notice that `all-strings' is
written differently.
\end{notate}

\begin{common}{queries.lisp}
(defun all-strings ()
  (mapcar 'second (select [*] :from [strings])))

(defun all-places ()
  (mapcar 'print-system-object
          (select [*] :from [places])))

(defun all-triples ()
 (mapcar 'print-system-object
         (select [*] :from [triples])))

(defun all-theories ()
 (mapcar 'print-system-object
         (select [*] :from [theories])))
\end{common}

\begin{notate}{Printing on particular dimensions}
One possible upgrade to the printing functions would be to
provide the built-in to ``curry'' the printout -- for
example, just print the source nodes from a list of
triples.  However, it should of course also be possible to
do processing like this Lisp after the printout has been
made (the point is, it is presumably it is more efficient
only to retrieve and format the data we're actually
looking for).
\end{notate}

\begin{notate}{Strings and ids} \label{strings-and-ids}
Unlike other objects, strings don't get printed with their
ids.  We should probably provide an \emph{option} to print
with ids (this could be helpful for subsequent work with
the strings in question; on the other hand, since strings
are being kept unique, we can immediately exchange a
string and it's id, so I'm not sure if it's necessary to
have an explicit ``option'').
\end{notate}

\subsection*{Functions that establish basic graph structure}

\begin{notate}{Thinking about graph-like data} \label{graph-like-data}
Here we have in mind one or more objects (e.g. a
particular source and sink) that is associated with
potentially any number of triples (e.g. all the possible
middles running between these two identified objects).
These functions establish various forms of locality or
neighborhood within the data.

The results of such queries can be optionally cached in a
view, which is useful for further processing
(cf. \ref{satisfy-conditions}).

These functions take input in the form of strings and/or
coordinates (cf. Note \ref{massage}).
\end{notate}

\begin{common}{queries.lisp}
(defun triples-given-beginning (node &optional view)
  "Get triples outbound from the given NODE.  Optional
  argument VIEW causes the results to be selected into a
  view with that name."
  (let ((data (massage node))
        (window (or view "interal-view"))
        ret)
    (when data
      (create-view
       window
        :as (select [*]
             :from [triples]
             :where [and [= [code1] (first data)]
                         [= [ref1] (second data)]]))
      (setq ret (select [*] :from window))
      (unless view
        (drop-view window))
      ret)))

(defun triples-given-end (node &optional view)
  "Get triples inbound into NODE.  Optional argument VIEW
       causes the results to be selected into a view with
       that name."
  (let ((data (massage node))
        (window (or view "interal-view"))
        ret)
    (when data
      (create-view
       window
        :as (select [*]
             :from [triples]
             :where [and [= [code3] (first data)]
                         [= [ref3] (second data)]]))
      (setq ret (select [*] :from window))
      (unless view
        (drop-view window))
      ret)))

(defun triples-given-middle (edge &optional view)
  "Get the triples that run along EDGE.  Optional argument
       VIEW causes the results to be selected into a view
       with that name."
  (let ((data (massage edge))
        (window (or view "interal-view"))
        ret)
    (when data
      (create-view
       window
       :as (select [*]
            :from [triples]
            :where [and [= [code2] (first data)]
                        [= [ref2] (second data)]]))
      (setq ret (select [*] :from window))
      (unless view
        (drop-view window))
      ret)))

(defun triples-given-middle-and-end (edge node &optional
       view)
  "Get the triples that run along EDGE into NODE.
       Optional argument VIEW causes the results to be
       selected into a view with that name."
  (let ((edgedata (massage edge))
        (nodedata (massage node))
        (window (or view "interal-view"))
        ret)
    (when (and edgedata nodedata)
      (create-view
       window
       :as (select [*]
            :from [triples]
            :where [and [= [code2] (first edgedata)]
                        [= [ref2] (second edgedata)]
                        [= [code3] (first nodedata)]
                        [= [ref3] (second nodedata)]]))
      (setq ret (select [*] :from window))
      (unless view
        (drop-view window))
      ret)))

(defun triples-given-beginning-and-middle (node edge
                                           &optional view)
  "Get the triples that run from NODE along EDGE.
Optional argument VIEW causes the results to be selected
into a view with that name."
  (let ((nodedata (massage node))
        (edgedata (massage edge))
        (window (or view "interal-view"))
        ret)
    (when (and nodedata edgedata)
      (create-view
       window
       :as (select [*]
            :from [triples]
            :where [and [= [code1] (first nodedata)]
                        [= [ref1] (second nodedata)]
                        [= [code2] (first edgedata)]
                        [= [ref2] (second edgedata)]]))
      (setq ret (select [*] :from window))
      (unless view
        (drop-view window))
      ret)))

(defun triples-given-beginning-and-end (node1 node2
       &optional view)
  "Get the triples that run from NODE1 to NODE2.  Optional
       argument VIEW causes the results to be selected
       into a view with that name."
  (let ((node1data (massage node1))
        (node2data (massage node2))
        (window (or view "interal-view"))
        ret)
    (when (and node1data node2data)
      (create-view
       window
       :as (select [*]
            :from [triples]
            :where [and [= [code1] (first node1data)]
                        [= [ref1] (second node1data)]
                        [= [code3] (first node2data)]
                        [= [ref3] (second node2data)]]))
      (setq ret (select [*] :from window))
      (unless view
        (drop-view window))
      ret)))

;; This one use `select-one' instead of `select'
(defun triple-exact-match (node1 edge node2 &optional
       view)
  "Get the triples that run from NODE1 along EDGE to
NODE2.  Optional argument VIEW causes the results to be
selected into a view with that name."
  (let ((node1data (massage node1))
        (edgedata (massage edge))
        (node2data (massage node2))
        (window (or view "interal-view"))
        ret)
    (when (and node1data edgedata node2data)
      (create-view
       window
       :as (select [*]
            :from [triples]
            :where [and [= [code1] (first node1data)]
                        [= [ref1] (second node1data)]
                        [= [code2] (first edgedata)]
                        [= [ref2] (second edgedata)]
                        [= [code3] (first node2data)]
                        [= [ref3] (second node2data)]]))
      (setq ret (select-one [*] :from window))
      (unless view
        (drop-view window))
      ret)))
\end{common}

\begin{notate}{Becoming flexible about a string's status}
One possible upgrade would be to provide versions of these
functions that will flexibly accept either a string or a
``placed string'' as input (since frequently we're
interested in content of that sort; see
\ref{importing-sketch}).
\end{notate}

\subsection*{Finding places that satisfy some property}

\begin{notate}{On `get-places-subject-to-constraint'}
Like `get-places' (Note \ref{get-places}), but this
time takes an extra condition of the form (A C B)
where one of A, B, and C is `nil'.  We test each
of the places in place of this `nil', to see if a
triple matching that criterion exists.
\end{notate}

\begin{common}{queries.lisp}
(defun get-places-subject-to-constraint (symbol condition)
  (let ((candidate-places (get-places symbol))
        accepted-places)
    (dolist (place candidate-places)
      (let ((filled-condition
             (map 'list (lambda (elt) (or elt
                                          `(1 ,place)))
                  condition)))
        (when (apply 'triple-relaxed-match
                     filled-condition)
          (setq accepted-places
                (cons place accepted-places)))))
    accepted-places))
\end{common}

\subsection*{Logic}

\begin{notate}{Caution: compatibility with theories?}
For the moment, I'm not sure how compatible this function
is with the theories apparatus we've established, or with
the somewhat vaguer notion of trans-theory questions or
concerns.  Global queries should work just fine, but
theory-local questions may need some work.  Before getting
into compatibility of these questions with the theory
apparatus, I want to make sure that apparatus is working
properly.  Note that the questions here do rely on
functions for graph-like thinking (Note
\ref{graph-like-data} et seq.), and it would certainly
make sense to port to ``subgraphs'' as represented by
theories.
\end{notate}

\begin{notate}{On `satisfy-conditions'} \label{satisfy-conditions}
This function finds the items which match constraints.
Constraints take the form (A B C), where precisely one of
A, B, or C should be `nil', and any of the others can be
either input suitable for `massage', or
`t'.  The `nil' entry stands for the object we're
interested in.  Any `t' entries are wildcards.

The first thing that happens as the function runs is that
views are established exhibiting each group of triples
satisfying each predicate.  The names of these views are
then massaged into a large SQL query.  (It is important to
``typeset'' all of this correctly for our SQL `query'.)
Finally, once that query has been run, we clean up,
dropping all of the views we created.
\end{notate}

\begin{common}{queries.lisp}
(defun satisfy-conditions (constraints)
  (let* ((views (generate-views constraints))
         (formatted-list-of-views (format-views
                                   views))
         (where-condition (generate-where-condition
                           views
                           constraints))
         (ret
          ;; Let's see what the query is, first of all.
          (query
           (concatenate
            'string
            "select v1.id, v1.code1, v1.ref1, "
                          "v1.code2, v1.ref2, "
                          "v1.code3, v1.ref3 "
            "from "
            formatted-list-of-views
            "where "
            where-condition
            ";"))))
    (mapc (lambda (name) (drop-view name)) views)
    ret))
\end{common}

\begin{notate}{Subroutines for `satisfy-conditions'}
The functions below produce bits and pieces of the SQL
query that `satisfy-conditions' submits.  The point of the
`generate-views' is to create a series of views centered
on the term(s) we're interested in (the `nil' slots in
each submitted constraint).  With
`generate-where-condition', we insist that all of these
interesting terms should, in fact, be equal to one
another.
\end{notate}

\begin{notate}{On `generate-views'}
In a `cond' form, for each constraint we must select the
appropriate function to generate the view; at the very end
of the cond form, we spit out the viewname (for `mapcar'
to add to the list of views).
\end{notate}

\begin{common}{queries.lisp}
(defun generate-views (constraints)
  (let ((counter 0))
    (mapcar
     (lambda (constraint)
       (setq counter (1+ counter))
       (let ((viewname (format nil "v~a" counter)))
         (cond
          ;; A * ? or A ? *
          ((or (and (eq (second constraint) t)
                    (eq (third constraint) nil))
               (and (eq (second constraint) nil)
                    (eq (third constraint) t)))
           (triples-given-beginning
            (first constraint)
            viewname))
          ;; * B ? or ? B *
          ((or (and (eq (first constraint) t)
                    (eq (third constraint) nil))
               (and (eq (first constraint) nil)
                    (eq (third constraint) t)))
           (triples-given-middle
            (second constraint)
            viewname))
          ;; * ? C or ? * C
          ((or (and (eq (first constraint) t)
                    (eq (second constraint) nil))
               (and (eq (first constraint) nil)
                    (eq (second constraint) t)))
           (triples-given-end
            (third constraint)
            viewname))
          ;; ? B C
          ((eq (first constraint) nil)
           (triples-given-middle-and-end
            (second constraint)
            (third constraint)
            viewname))
          ;; A ? C
          ((eq (second constraint) nil)
           (triples-given-beginning-and-middle
            (first constraint)
            (second constraint)
            viewname))
          ;; A C ?
          ((eq (third constraint) nil)
           (triples-given-beginning-and-end
            (first constraint)
            (third constraint)
            viewname)))
         viewname))
     constraints)))

(defun format-views (views)
  (let ((formatted-list-of-views ""))
    (mapc (lambda (view)
            (setq formatted-list-of-views
                  (concatenate
                   'string
                   formatted-list-of-views
                   (format nil "~a," view))))
          (butlast views))
    (setq formatted-list-of-views
          (concatenate
           'string
           formatted-list-of-views
           (format nil "~a " (car (last views)))))
    formatted-list-of-views))

(defun generate-where-condition (views conditions)
  (let ((where-condition "")
        (c (select-component (first conditions))))
    ;; there should be one less "=" condition than there
    ;; are things to compare; until we get to the last
    ;; view, everything is joined together by an `and'.
    ;; -- this needs to consider (map over) both `views'
    ;; and `conditions'.
    (loop
     for i from 1 upto (1- (length views))
     do
     (let ((compi (select-component (nth i conditions)))
           (viewi (nth i views)))
       (setq
        where-condition
        (concatenate
         'string
         where-condition
         (concatenate
          'string
          "(v1.code" c " = " viewi ".code" compi ") and "
          "(v1.ref" c " = " viewi ".ref" compi ") and ")))))
    (let ((viewn (nth (1- (length views)) views))
          (compn (select-component
                    (nth (length views) conditions))))
      (setq
       where-condition
       (concatenate
        'string
        where-condition
        "(v1.code" c " = " viewn ".code" compn ") and "
        "(v1.ref" c " = " viewn ".ref" compn ")")))
    where-condition))

(defun select-component (condition)
  (cond ((eq (first condition) nil) "1")
        ((eq (second condition) nil) "2")
        ((eq (third condition) nil) "3")))
\end{common}

\begin{common}{queries.lisp}
(locally-disable-sql-reader-syntax)
\end{common}

\begin{notate}{Even more complicated logic}
In order to conveniently manage complex queries, it would
be nice if we could store the results of earlier queries
into views, so that we can combine several such views for
further processing.
\end{notate}