#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\begin_preamble
\usepackage{tikz-cd}
\usepackage{xcolor}
\hypersetup{
colorlinks,
linkcolor={red!50!black},
citecolor={blue!50!black},
urlcolor={blue!80!black}
}
\end_preamble
\use_default_options false
\begin_modules
theorems-ams
eqs-within-sections
figs-within-sections
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "times" "default"
\font_sans "helvet" "default"
\font_typewriter "courier" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures false
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder false
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry false
\use_package amsmath 2
\use_package amssymb 2
\use_package cancel 1
\use_package esint 0
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Title
Graphs, Metagraphs, RAM, CPU
\end_layout
\begin_layout Author
Linas Vepštas
\begin_inset Foot
status open
\begin_layout Plain Layout
linasvepstas@gmail.com
\begin_inset CommandInset href
LatexCommand href
target "https://orcid.org/0000-0002-2557-740X"
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Date
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="2">
<features tabularvalignment="middle">
<column alignment="right" valignment="top">
<column alignment="left" valignment="top">
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2 Sept 2020
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Version 1.0
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
22 Nov 2021
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Version 2.0
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5 Dec 2021
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Version 2.1
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
22 Sept 2023
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Version 2.1.1
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Abstract
This text reviews the concepts of a graph store, starting from the fundamental
question of how to efficiently represent a graph in RAM (that is, in storage).
Starting with a naive conception of a graph database, it arrives at hypergraphs
and metagraphs as minor modifications to the storage format of a graph.
The resulting structure proves to be simpler and more efficient for representin
g graph data.
\end_layout
\begin_layout Abstract
This starts a domino chain of claims: Metagraphs are more flexible than
either graph stores or SQL-style table stores or JSON-stores for storing
data.
Metagraphs have a natural query language that is more powerful and easier
to use than SQL-inspired query languages, mostly because the table-join
concept is obviated and replaced by isomorphism.
\end_layout
\begin_layout Abstract
It is easy to specify a term rewriting system with metagraphs; it is a trite
extension of having a query system.
Both forward and reverse queries are natural, and so metagraphs provide
a solid foundation for rule-based systems.
\end_layout
\begin_layout Abstract
Metagraphs are naturally typed, in the sense of type theory.
Metagraphs are easily reified, and so the type system is itself trivially
expressible as metagraphs.
\end_layout
\begin_layout Abstract
Metagraphs can be used to specify a programming system/programming language,
but that language is low-level, and not really suitable for humans.
It is ideal for algorithmic (machine) manipulation, analogous to intermediate
languages inside of compilers.
\end_layout
\begin_layout Abstract
Most of these claims are founded on experimental results, rather than assertions
of theoretical analysis.
The experimental platform is the OpenCog AtomSpace and Atomese language.
\end_layout
\begin_layout Abstract
This is part of a sequence of texts on sheaves (
\emph on
a la
\emph default
sheaf theory).
It is a prerequisite for understanding the practical foundations on which
sheaves can be built.
It is useful, but not necessary, for understanding the actual AtomSpace
implementation.
\end_layout
\begin_layout Abstract
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents
\end_inset
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Introduction
\end_layout
\begin_layout Standard
Currently, graph databases are popular, as they have a rather distinct performan
ce profile, differing from both SQL and noSQL databases.
At a simplistic level, the OpenCog AtomSpace is a kind of a graph database.
More correctly, it is a generalized-hypergraph or
\begin_inset Quotes eld
\end_inset
metagraph
\begin_inset Quotes erd
\end_inset
database.
This design has certain implications for RAM and CPU usage.
This text argues that it has superior properties to ordinary graph databases.
It arrives at this conclusion by starting with the most basic, foundational
description of graph databases, and then defines hypergraphs and metagraphs
as minor variants on the underlying data structures.
\end_layout
\begin_layout Standard
Graphs offer an interesting storage format for many reasons.
Coupled to those reasons is a need for graph traversal, and another need
for graph query (solving the subgraph isomorphism problem).
Thus, the questions examined here include how one might best be able to
traverse graphs, and how to best perform subgraph matching.
By
\begin_inset Quotes eld
\end_inset
best
\begin_inset Quotes erd
\end_inset
, it is meant algorithms that find a good balance between speed and size.
\end_layout
\begin_layout Standard
This text is organized into the following sections:
\end_layout
\begin_layout Itemize
A naive definition of graphs.
\end_layout
\begin_layout Itemize
An aside about attaching attributes to the edges and vertexes of a graph.
This is effectively a quick summary of traditional knowledge representation
formats, specifically, tables, JSON and s-expressions.
\end_layout
\begin_layout Itemize
How graphs can be represented in memory (RAM), and how much storage is used
to represent a graph.
\end_layout
\begin_layout Itemize
Modifications to the representation that result in hypergraphs and metagraphs,
including an analysis of memory usage.
A formal definition of a metatree, the core component of a metagraph.
A key result is that metatrees are more compact than graphs for most data
representation problems.
The first hints that they are also more natural and easier to work with
start to show.
\end_layout
\begin_layout Itemize
A discussion of the concept of
\begin_inset Quotes eld
\end_inset
indexing
\begin_inset Quotes erd
\end_inset
, and how indexes are used to find data.
Contrasts are drawn between indexing in graphs, and indexing in SQL databases.
(The noSQL databases are given short shrift, mostly because of a famous
result showing that they are actually an
\begin_inset Quotes eld
\end_inset
opposite category
\begin_inset Quotes erd
\end_inset
, best termed coSQL.
\begin_inset CommandInset citation
LatexCommand cite
key "Meijer2011"
literal "false"
\end_inset
) A key observation is that metagraphs unavoidably have a certain kind of
index built into them; they come equipped with a (partial) index.
\end_layout
\begin_layout Itemize
A discussion of partial indexes, and their role in database normalization.
An argument is made that metatrees are self-normalizing.
This feels perhaps uncomfortable, given the vast resources that database
textbooks expend on teaching normalization to students.
\end_layout
\begin_layout Itemize
Representing metatrees as strings, with specific attention focused on the
fact that subtrees are necessarily unique, and how this uniqueness can
be managed in a practical way.
This includes a rejection of UUID's as a technique for assigning unique
labels to metatrees.
\end_layout
\begin_layout Itemize
A discussion of insertion, deletion and graph mutability.
A primary result is that metatrees are necessarily immutable, as otherwise
a host of useful and desirable assumptions are shattered.
This is a positive result: immutability is a marvelous property for data
structures to have, when they are being accessed by multi-threaded systems.
A secondary result is that a metagraph database looks exactly like a single
metatree, but a mutable one.
Thus, there are two kinds of metatrees: the immutable ones are called
\begin_inset Quotes eld
\end_inset
data
\begin_inset Quotes erd
\end_inset
and the mutable ones are called
\begin_inset Quotes eld
\end_inset
databases
\begin_inset Quotes erd
\end_inset
.
Since they are both metatrees, they can be layered, nested, hierarchically
stacked, as desired.
\end_layout
\begin_layout Itemize
A review of query languages and graph traversal.
A primary result is that all SQL-inspired query languages inherit the table-bas
ed viewpoint of SQL.
This in turn causes one to think in terms of table joins, which, in a graph
setting, looks like an explicitly-specified graph walk, chaining from one
edge to the next.
This is seen in systems such as GraphQL, SparQL, Neo4J or grakn.ai (TypeDB),
which present graph queries in terms of explicit edge walks.
\end_layout
\begin_layout Itemize
An example of a metagraph query language, which hops outside of the *QL
paradigm of edge walks (
\emph on
aka
\emph default
table joins), into a query mode that more closely resembles pattern matching.
Conventional pattern matching is implemented in terms of a state machine,
and so it is not enough for a proper graph query.
A true graph walk requires a stack machine; it requires a recursive walk
of a graph.
\end_layout
\begin_layout Itemize
A short discussion of query analysis and query planning for a metagraph
query language.
\end_layout
\begin_layout Itemize
A presentation of inverted queries.
These are queries that are
\begin_inset Quotes eld
\end_inset
answers
\begin_inset Quotes erd
\end_inset
in search of a
\begin_inset Quotes eld
\end_inset
question
\begin_inset Quotes erd
\end_inset
.
They consist entirely of constant terms, to be matched to forward-queries
having variables in them.
Inverted queries are the bread-and-butter of chat-bots and rule engines.
The key observation here is that metatrees represent inverted queries just
as readily and naturally as forward queries; this is because a partial
index on a metatree can be understood as a kind of trie.
Metatrees unify database concepts with rule engine concepts within the
same framework.
\end_layout
\begin_layout Itemize
A discussion of the natural interpretation of metatrees.
The experimental result here, after a decade of use, is that metatrees
correspond to type-theoretical types.
They reify easily and naturally, and have an obvious suite of type constructors.
As you might guess from the tone of voice here, the type constructors are
themselves just metatrees.
The concept of sheaves is touched upon very quickly here, as the sheaf
elements are just
\begin_inset Quotes eld
\end_inset
jigsaw puzzle pieces
\begin_inset Quotes erd
\end_inset
and the jigsaw connectors are types.
\end_layout
\begin_layout Itemize
A discussion of execution, evaluation, fexprs, macros, $vau, term rewriting
systems and intermediate languages.
Obviously, abstract syntax trees are a special case of trees, and trees
are a special case of metatrees.
Abstract syntax trees achieve two things: they encode executable programs,
and they also encode syntactic structure that can be re-written by homotopic
transformations.
As such, they bridge across some old ideas in lisp (fexprs, $vau) and newer
ideas in knowledge representation (prolog).
\end_layout
\begin_layout Itemize
A discussion of human-oriented programming languages vs.
machine-oriented programming languages.
Metatrees and metagraphs are themselves too low a level to be suitable
as a programming language which human beings would want to use on a daily
basis.
Instead, they have more in common with compiler intermediate languages,
which are term rewriting systems used by machines (compilers) to perform
transformations on data.
\end_layout
\begin_layout Standard
As a conclusion, it is noted that the OpenCog AtomSpace has been the experimenta
l platform on which all of the above results have been obtained, and embodies
most of the ideas presented here.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/AtomSpace
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://github.com/opencog/atomspace
\end_layout
\end_inset
\end_layout
\end_inset
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Graph Representations
\end_layout
\begin_layout Standard
Formally, a graph is
\end_layout
\begin_layout Itemize
A set of vertexes
\begin_inset Formula $V=\left\{ v_{1},v_{2},\cdots,v_{M}\right\} $
\end_inset
\end_layout
\begin_layout Itemize
A set of edges
\begin_inset Formula $E=\left\{ e_{1},e_{2},\cdots,e_{N}\right\} $
\end_inset
where each edge
\begin_inset Formula $e_{k}$
\end_inset
is an ordered pair of vertexes drawn from the set
\begin_inset Formula $V$
\end_inset
.
\end_layout
\begin_layout Standard
Because edges are ordered pairs, it is conventional to denote them with
arrows, having a head and tail.
These can be joined together in arbitrary ways.
Below is a
\begin_inset Quotes eld
\end_inset
typical
\begin_inset Quotes erd
\end_inset
directed graph:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/graph-6.eps
lyxscale 70
width 40col%
\end_inset
\end_layout
\begin_layout Subsection
Attributes
\end_layout
\begin_layout Standard
In practice, one wishes to associate a label to each vertex, and also some
additional attribute data; likewise for the edges.
There are three fundamental choices available for storing attributes: merged
schema+data, disjoint schema–data and s-expressions.
An examples of the first is JSON.
Each block of data to be stored is preceded by its name.
Additional markup, such as quotes and square brackets, indicate structure
such as text-strings and arrays.
An example of disjoint schema–data are tables.
The name and data type appears only in the column heading for the table;
individual rows in the table do not need to repeat the schema.
Clearly, for tables with more than a few rows, the tabular format offers
a huge advantage in terms of memory usage.
Conversely, having many tables with just one or two rows each quickly becomes
a table management problem; conventional systems are not designed to hold
a million tables of one row each.
\end_layout
\begin_layout Standard
Tables are highly inflexible when new columns or new schema need to be added.
There is no sensible way to take one row of a table, and have it use a
different schema than the other rows.
It doesn't even make sense to talk about rows in this way; if one row has
a different schema than another, they aren't rows of the same table any
more.
\end_layout
\begin_layout Standard
An example of an s-expression store is a key-value store.
Here, the first word is taken to be the key; subsequent words are taken
to be a list of values associated with that key.
The idea of s-expressions emphasizes that the key-value store can be hierarchic
ally structured.
An example is the Unix file-system structure: each directory can have files,
but it can also have subdirectories,
\emph on
ad infinitum
\emph default
.
In this sense, a URL can be understood to be a kind-of s-expression.
\end_layout
\begin_layout Standard
In a graph store, one has these three basic choices for storing attributes,
both for vertexes and for edges.
One might even contemplate a mixture; after all, a JSON blob is isomorphic
to a table with only a single row.
The remainder of this text will make little or no assumptions about the
storage format of the attributes, as this has little or no impact on the
primary topics here.
With one exception: query and indexing.
This is reviewed in a distinct section later on.
\end_layout
\begin_layout Subsubsection
Emulating Tables
\end_layout
\begin_layout Standard
This section aims to make the above commentary a bit more concrete by working
though some examples.
Although the examples in this section are written in text, the reader is
very strongly urged to try to imagine how these structures might be represented
in RAM, and how much storage they might take.
A later section will return to these questions of in-RAM representations.
\end_layout
\begin_layout Standard
Consider the need to store data about some students.
Expressed in JSON format, it might be written as:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
{ grades:
\end_layout
\begin_layout Plain Layout
[
\end_layout
\begin_layout Plain Layout
{ student: {name: Joe}, {gpa: 3.5}},
\end_layout
\begin_layout Plain Layout
{ student: {name: Mary}, {gpa: 3.6}},
\end_layout
\begin_layout Plain Layout
{ student: {name: Rachel}, {gpa: 3.0}}
\end_layout
\begin_layout Plain Layout
]
\end_layout
\begin_layout Plain Layout
}
\end_layout
\end_inset
The square brackets denote a list; as is conventional with a list, all list
elements are uniform and of the same type.
Clearly, this appears to be a very regular structure.
If there are hundreds of students, one might try to save some space by
eliminating the repeated attribute names.
If JSON is used for this, this becomes a column-store:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
{ table:
\end_layout
\begin_layout Plain Layout
{ schema: {name: string}, {gpa: float}}
\end_layout
\begin_layout Plain Layout
{ names: [Joe, Mary, Rachel] },
\end_layout
\begin_layout Plain Layout
{ gpa: [3.5, 3.6, 3.0 ] }
\end_layout
\begin_layout Plain Layout
}
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
That is, each entry in the table is a column name, followed by a list of
all of the values in that column.
\end_layout
\begin_layout Standard
This is distinct from a row-store.
In a row store, one conventionally provides a schema describing the columns
and their formats, much as above, and then provides the rows, one by one,
as
\begin_inset Quotes eld
\end_inset
records
\begin_inset Quotes erd
\end_inset
, or inhomogeneous lists of fixed length.
That is, each entry in the list has a different type (it has the type of
the column), but each list is exactly the same length; thus, a
\begin_inset Quotes eld
\end_inset
record
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Students
\end_layout
\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
name
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
gpa
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
string
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
float
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Joe
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.5
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Mary
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.6
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Rachel
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.0
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
There does not appear to be any way of representing a row-store in JSON,
at least not in the JSON as naively conceived here.
One wishes to write something like the below, but the syntax makes it illegal:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
{ table:
\end_layout
\begin_layout Plain Layout
{ schema: {name: string}, {gpa: float}}
\end_layout
\begin_layout Plain Layout
{ students:
\end_layout
\begin_layout Plain Layout
[
\end_layout
\begin_layout Plain Layout
(Joe, 3.5), # This is not valid JSON!
\end_layout
\begin_layout Plain Layout
(Mary, 3.6),
\end_layout
\begin_layout Plain Layout
(Rachel, 3.0)
\end_layout
\begin_layout Plain Layout
]
\end_layout
\begin_layout Plain Layout
}
\end_layout
\begin_layout Plain Layout
}
\end_layout
\end_inset
\end_layout
\begin_layout Standard
It is this last example that makes clear that an s-expression store can
offer the best of both worlds.
This is shown in the next section.
\end_layout
\begin_layout Subsubsection
OGRE: Open Generic Representation
\end_layout
\begin_layout Standard
A particularly nice and human-friendly API can be found in the OGRE module
in BAP.
\begin_inset CommandInset citation
LatexCommand cite
key "OGRE"
literal "false"
\end_inset
It is an s-expression database that allows new data structures to be defined
in generic ways.
In short, any s-expression is a valid record.
Records do not need to be of the same length, or of the same type.
\end_layout
\begin_layout Standard
Thus, the previous example can be written as
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(student (name Joe) (gpa 3.5))
\end_layout
\begin_layout Plain Layout
(student (name Mary) (gpa 3.6))
\end_layout
\begin_layout Plain Layout
(student (name Rachel) (gpa 3.0))
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
Note that these are three distinct records, and are NOT a list of three
rows!
\end_layout
\begin_layout Standard
As written, this has a distinctly JSONic feel to it, in that every value
is tagged with the field type that names it.
But then, the OGRE documentation notes that this is equivalent to
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(student Joe 3.5)
\end_layout
\begin_layout Plain Layout
(student Mary 3.6)
\end_layout
\begin_layout Plain Layout
(student Rachel 3.0)
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
provided that one already knows the column structure of the data.
But this is easily achieved:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(declare student (name str) (gpa float))
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
This last statement resembles a conventional table-database table declaration.
\end_layout
\begin_layout Standard
One can go farther: there is no particular need to tag each row with the
row-label
\family sans
\size small
'student'
\family default
\size default
.
The most compact representation then appears to be the following:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(students-table
\end_layout
\begin_layout Plain Layout
(Joe 3.5)
\end_layout
\begin_layout Plain Layout
(Mary 3.6)
\end_layout
\begin_layout Plain Layout
(Rachel 3.0))
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
This last form now obviously has the shape of a row-store.
Each row is a tuple, all tuples look alike.
\end_layout
\begin_layout Standard
This last form enables a rather conventional SQL query system to be defined.
There is a table definition, providing column types, and column labels
(the labels are needed for query/search), and the individual records (rows)
in the table are uniform.
The uniformity allows both for very compact storage and easy query.
\end_layout
\begin_layout Standard
The nature of query in these three styles, and what it implies for RAM consumpti
on and CPU use, is quite dramatic.
They can have remarkably different performance profiles, and even some
remarkable limitations in the kinds of queries that can be imagined or
can be written.
This is a more complex topic, and will be returned to later in this text.
\end_layout
\begin_layout Subsubsection
Tables and Algebraic Data Types
\end_layout
\begin_layout Standard
Category theory provides a modern foundation for a lot of thinking in computer
science,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia:
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Category_theory
\end_layout
\end_inset
but perhaps much more instructive and practical would be a book such as
\begin_inset Quotes eld
\end_inset
Category Theory for Programmers
\begin_inset Quotes erd
\end_inset
, Bartosz Milewski (2019) available here:
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://github.com/hmemcpy/milewski-ctfp-pdf
\end_layout
\end_inset
.
\end_layout
\end_inset
and one particular aspect of it, type theory, provides a theoretical framework
for the practical construction of data types.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Type_theory
\end_layout
\end_inset
for an overview of the abstract theory of types, stemming from the nature
of functors in category theory.
The word
\begin_inset Quotes eld
\end_inset
type
\begin_inset Quotes erd
\end_inset
here is the same as that in computer programming: the data type, see
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Data_type
\end_layout
\end_inset
for a review of the more concrete ideas.
\end_layout
\end_inset
Much of this text presumes these theoretical foundations are percolating
in the background, and so a few brief words are in order.
\end_layout
\begin_layout Standard
An SQL Table declaration corresponding to the above example is
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
CREATE TABLE student (
\end_layout
\begin_layout Plain Layout
name text,
\end_layout
\begin_layout Plain Layout
gpa real
\end_layout
\begin_layout Plain Layout
)
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
The interpretation is meant to be straight-forward: a table with two columns,
one of which is an unlimited length character string, the other a single-precis
ion floating point number.
We could do the same in C++ (or Java, or any conventional object oriented
language) and write
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
class student {
\end_layout
\begin_layout Plain Layout
char* name;
\end_layout
\begin_layout Plain Layout
float gpa;
\end_layout
\begin_layout Plain Layout
};
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
In terms of knowledge representation, these all express the same idea.
The practical differences between these are whether the structures are
created at runtime (as they would be for SQL, or scheme/lisp) or compile
time (as they would be for C++ or OCaml).
\end_layout
\begin_layout Standard
All of these are examples of
\begin_inset Quotes eld
\end_inset
compound types
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
composite types
\begin_inset Quotes erd
\end_inset
, or more loosely, the
\begin_inset Quotes eld
\end_inset
product type
\begin_inset Quotes erd
\end_inset
, or, more narrowly, the
\begin_inset Quotes eld
\end_inset
Cartesian product
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Product_type
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Cartesian_product
\end_layout
\end_inset
.
Here, and in many subsequent footnotes, the reader will be directed at
Wikipedia pages.
This is meant for clarity: if the reader is unfamiliar with a topic or
phrase, the Wikipedia page provides the requisite details.
These Wikipedia references are not meant to be hand-waving appeals to abstract
concepts: they are meant to provide precise, formal definitions for the
ideas discussed here.
The intended sense of the words and concepts brought up here are meant
to be precisely, exactly those described in the Wikipedia articles.
Although this text attempts to be understandable without prior, indepth
understanding of that content, it would also be the case that all of the
finer points and subtleties will be missed, without this acquaintance.
Read the Wikipedia articles.
You should be familiar with what they talk about.
\end_layout
\end_inset
The Cartesian product of two sets
\begin_inset Formula $A$
\end_inset
and
\begin_inset Formula $B$
\end_inset
, in set-builder notation, is
\begin_inset Formula
\[
A\times B=\left\{ \left(a,b\right)\vert a\in A\mbox{ and }b\in B\right\}
\]
\end_inset
We want
\begin_inset Formula $A$
\end_inset
to be the set of students and
\begin_inset Formula $B$
\end_inset
to be the set of grades they could get; these are not only different sets,
but the types of the members of these sets are different.
This leads to the product type
\begin_inset Formula ${\bf A}\times{\bf B}$
\end_inset
where the
\begin_inset Formula ${\bf A}$
\end_inset
is the type of text strings, and
\begin_inset Formula ${\bf B}$
\end_inset
is the type of numbers with decimal places.
Members are again written as
\begin_inset Formula $\left(a,b\right)$
\end_inset
or perhaps
\begin_inset Formula $\left(a:{\bf A},b:{\bf B}\right)$
\end_inset
and are sometimes called
\begin_inset Quotes eld
\end_inset
tuples
\begin_inset Quotes erd
\end_inset
, for the obvious reason that the comma is a great way of writing lists
of things: lists are Cartesian products.
\end_layout
\begin_layout Standard
If this starts feeling circular, that is because it is: the SQL statement
and the C++ class declaration above are both examples of Cartesian products.
Tuples and records are generically examples of products.
\end_layout
\begin_layout Subsubsection
Category Theory and Coproducts
\end_layout
\begin_layout Standard
We're going to jump the gun a bit, and briefly mention coproducts, as they
are dual to products.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Coproduct
\end_layout
\end_inset
.
\end_layout
\end_inset
Examples of coproducts in programming are the
\family sans
\size small
\begin_inset Quotes eld
\end_inset
union
\begin_inset Quotes erd
\end_inset
\family default
\size default
statement in C/C++, or the variant type in other programming languages.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Union_type
\end_layout
\end_inset
.
\end_layout
\end_inset
In type theory, these are referred to as
\begin_inset Quotes eld
\end_inset
sum types
\begin_inset Quotes erd
\end_inset
, and are dual to the product type.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Tagged_union
\end_layout
\end_inset
.
\end_layout
\end_inset
In type theory, these are referred to as the sigma type
\begin_inset Formula $\Sigma$
\end_inset
and the pi type
\begin_inset Formula $\Pi$
\end_inset
,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Dependent_type
\end_layout
\end_inset
.
\end_layout
\end_inset
and in formal logic (set theory) lead to the notion of the sigma-pi hierarchy.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/L
\backslash
%C3
\backslash
%A9vy_hierarchy
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Descriptive_set_theory
\end_layout
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Category theory is sometimes called the
\begin_inset Quotes eld
\end_inset
theory of dots and arrows
\begin_inset Quotes erd
\end_inset
, and a central notion is the
\begin_inset Quotes eld
\end_inset
opposite category
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $C^{\mbox{op}}$
\end_inset
that is dual to the category
\begin_inset Formula $C$
\end_inset
.
In the opposite category, the direction of all of the arrows are reversed.
Naming-wise, the prefix
\begin_inset Quotes eld
\end_inset
co-
\begin_inset Quotes erd
\end_inset
is prepended to names: thus products are dual to coproducts.
The coproduct type and the sum type are the same thing.
Insofar as the product can be drawn as
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/product.eps
width 40col%
\end_inset
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
the coproduct can be drawn as
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/coproduct.eps
width 40col%
\end_inset
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
It is common in category theory to leave the dots and arrows unlabeled,
as often it is more interesting to just talk about the shapes, rather than
the labels.
But to make it clear, here is the product type again, with the labels:
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/product-students.eps
width 40col%
\end_inset
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
The arrows are the
\begin_inset Quotes eld
\end_inset
canonical projections
\begin_inset Quotes erd
\end_inset
or the
\begin_inset Quotes eld
\end_inset
projection morphisms
\begin_inset Quotes erd
\end_inset
of the product.
The union type or coproduct will not be illustrated.
The reader is encouraged to imagine a C/C++
\family sans
\begin_inset Quotes eld
\end_inset
\size footnotesize
union
\family default
\size default
\begin_inset Quotes erd
\end_inset
statement and arrange the arrows appropriately.
\end_layout
\begin_layout Standard
The product and the coproduct, taken together, are often referred to as
Algebraic Data Types (ADT).
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Algebraic_data_type
\end_layout
\end_inset
.
\end_layout
\end_inset
In the text that follows, there will be lots of arrows, pointing both forwards,
and backwards.
These can all be understood in terms of the type-theoretic foundations
sketched here.
A more formal presentation of the type theory is deferred to a different
text in this series, describing the jigsaw puzzle-piece metaphor, and how
it is used to construct sheaves.
\end_layout
\begin_layout Standard
Not all of the arrows that will be drawn in the subsequent text can be understoo
d as category-theoretic arrows.
Category theory has some fairly strict ideas about what one can do with
arrows, and thus, not every diagram will be a valid category.
However, many of them will be.
The most important examples of arrows that can be interpreted as category-theor
etic arrows are the indexes on SQL tables (
\family sans
\size footnotesize
PRIMARY KEY
\family default
\size default
and
\family sans
\size footnotesize
FOREIGN KEY
\family default
\size default
) and the opposite arrows in noSQL key-value databases.
This is gleefully articulated by Meijer and Bierman.
\begin_inset CommandInset citation
LatexCommand cite
key "Meijer2011"
literal "false"
\end_inset
We shall need arrows going in both directions in order to perform efficient
metagraph queries, to be explained in later sections.
\end_layout
\begin_layout Subsection
Graphs for Storing Data
\end_layout
\begin_layout Standard
The above listed three ways of storing attributes on a graph, and yet ignored
the graph itself.
Thus, for completeness, lets draw the diagram of how this might be stored
in a graph.
\end_layout
\begin_layout Standard
Obviously, its
\begin_inset Quotes eld
\end_inset
graphical
\begin_inset Quotes erd
\end_inset
if it is drawn as follows:
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/joe-mary-v1.eps
width 60col%
\end_inset
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
In the above, the vertexes are labeled with s-expressions; the edges are
not labeled.
It consists of two disjoint graphs; one of the graphs is used to encode
the type information used in the other graph.
There are a large variety of choices that can be made in how this is done.
The above just shows one way; it might not be the best way, although that
depends on the problem domain.
\end_layout
\begin_layout Standard
Below shows another alternative, this time with labeled edges:
\end_layout
\begin_layout Standard
\align center
\begin_inset VSpace defskip
\end_inset
\begin_inset Graphics
filename graphics/joe-mary-v2.eps
width 35col%
\end_inset
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
The encoded data is the same; the encoding is different.
Here, the schema makes an explicit reference to the object being described.
The cost is that the graph is no longer of a uniform shape.
\end_layout
\begin_layout Subsubsection
Mixed Representations
\end_layout
\begin_layout Standard
In both of the above examples, the graph store was assumed to have some
distinct, separate attribute store for each vertex, and possibly each edge.
Thus, in a sense, this is not a
\begin_inset Quotes eld
\end_inset
pure
\begin_inset Quotes erd
\end_inset
graph store, where each edge or vertex can only have an atomic singleton
value on it (a single number or a single string).
Of course, one could rework the above graphs so that each vertex/edge does
have just one single value on it.
While the simplicity of singleton-valued graphs is perhaps intellectually
appealing, it proves to not be practical for everyday use.
Assuming singleton-valued graphs also has some very strong implications
on RAM and CPU use, and the ability to perform searches/queries.
This point will be returned to below.
In the meanwhile, this kind of mixed model will be assumed: some data will
be stored graphically, and some data will be stored as complex attribute
sets attached to the edges and vertexes.
\end_layout
\begin_layout Standard
Some historical hand-waving can be done to justify the origins of a mixed-model
graph store.
In predicate logic, and in model theory, one distinguishes the predicates
and terms that one is discussing, from the truth values or valuations that
can be assigned to them.
It is relatively straightforward to envision predicates and terms as trees
or DAG's.
The truth values are distinct from the graphs themselves; instead, they
are an assignment of true/false to each expression.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is the grand leap from Aristotelian,
\begin_inset Quotes eld
\end_inset
classical
\begin_inset Quotes erd
\end_inset
logic, to predicate logic.
The disentanglement of truth-valuations from propositions enables giant
leaps in reasoning abilities.
This in turn opens the ability to further disentangle syntactic from semantic
entailment, thus allowing a connection to grammar and language to be made.
The adjointness between grammar and graphs is precisely the core, central
reason why properly constructed graph databases are central to the pursuit
of AGI.
\end_layout
\end_inset
A straight-forward example can be found in Prolog: in the beginning, there
are expressions; by means of inference, truth-value labels are inferred.
The truth values are not a part of the original graph; they live outside
of it, as an attribute.
\end_layout
\begin_layout Standard
Of course, things get interesting as soon as one leaves the domain of crisp-logi
c T/F values, and considers instead valuations that are Bayesian probabilities.
Some monkeying around then leads one to distinguish Bayesian probabilities
from fuzzy logic valuations.
Other kinds of data worms its way in: confidence intervals; frequentist
counts; marginals.
Some of this data is non-numeric, but are choices (
\emph on
e.g.
\emph default
true, false or unknown) or explicitly symbolic (
\emph on
e.g.
\emph default
red, blue or green).
It usually does not take long to realize the practical need for a mixed-model
graph database, supporting both good graph features, and also supporting
complex attribute systems attached to each edge/vertex.
\end_layout
\begin_layout Subsubsection
Related Work
\end_layout
\begin_layout Standard
See also Grainger et al.
\begin_inset CommandInset citation
LatexCommand cite
key "Grainger2016"
literal "false"
\end_inset
for a description of a dynamic edge-vertex database with inverted indexes.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Representing Graphs in RAM
\end_layout
\begin_layout Standard
In what follows, all data is assumed to live in-RAM; the on-disk representations
do not concern us.
One reason for this is that a variety of disk management systems exist,
and work quite well at abstracting details.
The earliest such is perhaps the Berkeley DBM
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Berkeley_DB
\end_layout
\end_inset
\end_layout
\end_inset
and the Gnu gdbm.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://www.gnu.org.ua/software/gdbm/
\end_layout
\end_inset
\end_layout
\end_inset
These have been followed by Google's LevelDB
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://dbdb.io/db/leveldb
\end_layout
\end_inset
\end_layout
\end_inset
and Facebook's extension RocksDB.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://rocksdb.org/
\end_layout
\end_inset
\end_layout
\end_inset
It is usually not too hard to take an in-RAM database, and layer it on
top of one of these systems to obtain a disk-backed database.
Of course, there are numerous ifs-and-buts, which provide motivations to
roll-your-own; these will be ignored in this text.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
One must resist one wide-spread and common temptation: layering an in-RAM
database on top of another database that is RAM-hungry.
This is at best counter-productive: for every byte consumed in one, one
risks a byte consumed in the other.
As a result, one can only store half as much data, or must purchase twice
as much RAM.
Despite the self-evidence of these last statements, such a layering is
widely recommended, on the basis of the supposed superiority of the lower
layer.
One must be particularly cautious if the lower layer requires the use of
network communications.
Networking requires the kernel to become involved, tasking-switching and
performing IPC.
This can easily become a performance bottleneck.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
All the discussion in this text assumes uniform memory access; that is,
a
\begin_inset Quotes eld
\end_inset
flat
\begin_inset Quotes erd
\end_inset
memory topology, where any location in storage can be accessed with the
same latency as any other.
Modern CPU's are all NUMA machines;
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Non-uniform_memory_access
\end_layout
\end_inset
\end_layout
\end_inset
it is too much for this text to dive into the issues that these pose.
\end_layout
\begin_layout Subsection
Naive RAM Representations
\end_layout
\begin_layout Standard
Storing a set of vertexes in RAM is straight-forward.
Since it is a set, one can use either a hash-table, a b-tree, or even an
array or list.
For the discussion here, the precise format is not directly relevant, and
so a tabular format will be used to illustrate the ideas.
Again, the table rows might actually reside in hash-tables or b-trees,
depending on desired access and update performance.
\end_layout
\begin_layout Standard
The vertex table is straight-forward:
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
vertex id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
The goal of having a vertex id (which is necessarily a
\begin_inset Quotes eld
\end_inset
universally unique id
\begin_inset Quotes erd
\end_inset
or uuid) is that it is required by the edge table.
In the most obvious, direct form, the edge table will have the shape
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="4">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
edge id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
head-vertex
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
tail-vertex
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
77
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
88
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
99
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\begin_inset CommandInset label
LatexCommand label
name "graph edge table"
\end_inset
\end_layout
\begin_layout Standard
This representation is perhaps too naive.
To perform a graph traversal, i.e.
to walk from vertex to vertex, following only connecting edges, one needs
to know which edges come in, and which edges go out.
Of course, these can be found in the edge table, but searching the edge
table is absurd: for an edge table of
\begin_inset Formula $N$
\end_inset
edges, such a search takes
\begin_inset Formula $O\left(N\right)$
\end_inset
time.
Thus, it is natural to incorporate a special index for edges into the vertex
table:
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="4">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
vertex id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
outgoing
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
incoming
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
{}
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
{77}
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
{77}
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
{88,99}
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
{88}
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
{88}
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\begin_inset CommandInset label
LatexCommand label
name "graph vertex table"
\end_inset
\end_layout
\begin_layout Standard
Note that the incoming and outgoing columns hold sets: any given vertex
may appear in more than one edge.
They are sets, not lists, as the order is not particularly important.
They are not 'multisets': any given edge appears at most once in the incoming/o
utgoing sets.
Suitable representations for sets include hash-tables and trees, each with
its own distinct RAM and access-time profile.
\end_layout
\begin_layout Standard
Table updates must be both thread safe and fast.
It is easy to lock the table with a mutex, but this can quickly limit the
amount of concurrency.
The latest lock-free technology promises reasonable solutions; however,
the technology remains immature.
There are several implementations of concurrent hash maps, but none for
concurrent multimaps (that also support erase).
Likewise, lock-free tree implementations are absent; trees offer a considerably
more compact storage format when tables are small.
\end_layout
\begin_layout Subsection
Prelude to indexing
\end_layout
\begin_layout Standard
A conventional requirement for graph databases is to locate all nodes and
vertexes having some particular attribute.
This opens a Pandora's box of indexing schemes.
The opening of this box is deferred to a later section, but we can take
a quick peak: suppose one wants to find all vertexes where the attr-data
has a field called
\begin_inset Quotes eld
\end_inset
favorite song
\begin_inset Quotes erd
\end_inset
.
Vertexes representing buildings and automobiles won't have a
\begin_inset Quotes eld
\end_inset
favorite song
\begin_inset Quotes erd
\end_inset
, vertexes representing people might, but not necessarily.
Thus, there is a need for an index: a set of all vertexes that have this
tag.
Every time a vertex is added or removed, this index might have to be updated.
Thus, adding indexes in this way incurs a CPU overhead.
If there are
\begin_inset Formula $J$
\end_inset
indexes, then there is an
\begin_inset Formula $O\left(J\right)$
\end_inset
CPU overhead for vertex insertion/removal.
There is also RAM consumption: an index containing
\begin_inset Formula $K$
\end_inset
items requires at least
\begin_inset Formula $O\left(K\right)$
\end_inset
storage, and possibly
\begin_inset Formula $O\left(K\log K\right)$
\end_inset
.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Hypergraphs
\end_layout
\begin_layout Standard
A hypergraph is much like a graph, except that the edges, now called
\begin_inset Quotes eld
\end_inset
hyperedges
\begin_inset Quotes erd
\end_inset
, can contain more than two vertexes.
That is, the hyperedge, rather than being an ordered pair of vertexes,
is an ordered list of vertexes.
The metagraph takes the hypergraph concept one step further: the hyperedge
may also contain other hyperedges.
A change of terminology is useful: the basic objects are now called
\begin_inset Quotes eld
\end_inset
nodes
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
links
\begin_inset Quotes erd
\end_inset
instead of
\begin_inset Quotes eld
\end_inset
vertexes
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
edges
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
Formally, a hypergraph is:
\end_layout
\begin_layout Itemize
A set of vertexes
\begin_inset Formula $V=\left\{ v_{1},v_{2},\cdots,v_{M}\right\} $
\end_inset
\end_layout
\begin_layout Itemize
A set of hyperedges
\begin_inset Formula $E=\left\{ e_{1},e_{2},\cdots,e_{N}\right\} $
\end_inset
where each hyperedge
\begin_inset Formula $e_{k}$
\end_inset
is an ordered list of vertexes drawn from the set
\begin_inset Formula $V$
\end_inset
.
This list may be empty, or have one, or two, or more members.
\end_layout
\begin_layout Standard
A metagraph is very nearly the same:
\end_layout
\begin_layout Itemize
A set of nodes
\begin_inset Formula $V=\left\{ v_{1},v_{2},\cdots,v_{M}\right\} $
\end_inset
\end_layout
\begin_layout Itemize
A set of links
\begin_inset Formula $E=\left\{ e_{1},e_{2},\cdots,e_{N}\right\} $
\end_inset
where each hyperedge
\begin_inset Formula $e_{k}$
\end_inset
is an ordered list of nodes, or other links, or a mixture.
They are arranged to be acyclic (to form a directed acyclic graph).
\end_layout
\begin_layout Standard
It is convenient to give the name
\begin_inset Quotes eld
\end_inset
atoms
\begin_inset Quotes erd
\end_inset
to something that is either a node or a link.
Links are thus lists of atoms.
\end_layout
\begin_layout Subsection
Hypergraph representations
\end_layout
\begin_layout Standard
The naive representation for the hypergraph is a straight-forward extension
of the edge table (the table
\begin_inset CommandInset ref
LatexCommand vpageref
reference "graph edge table"
plural "false"
caps "false"
noprefix "false"
\end_inset
above).
The table below provides an example that is shown in the figure following
below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
hyper-edge id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
vertex-list
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(v_{1}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(v_{1},v_{2}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(v_{3},v_{4}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{4}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(v_{3},v_{2},v_{1}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
The vertex list may be empty, may hold one, or more vertexes.
It is necessarily ordered (and thus not a set) and may contain repeated
entries (a vertex may appear more than once in the list).
In other respects, this edge table is quite similar to the edge table for
ordinary graphs.
\end_layout
\begin_layout Standard
As before, the ability to traverse the hypergraph (quickly) is a core requiremen
t.
This means that, given a vertex, one must be able to quickly find the edges
attached to it.
This requires modification to the vertex table given before.
\end_layout
\begin_layout Standard
Several choices are possible.
One is to add a new column for each positional location in the vertex list.
That is, 0'th column holds the edges which have the corresponding vertex
in the 0'th position of the vertex list, the 1'th column likewise.
This can be read off from the table above:
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="6">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
vertex id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
edge-set-0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
edge-set-1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
edge-set-2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{1},e_{2}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{2},e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{3},e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{4}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{2}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
To actually store this table, one must have a data-structure that is a list-of-s
ets, which can be a bit over-complex and challenging to use.
It is easier to just mash all of these into one set; that is all that is
needed for hypergraph traversal.
If the positional location is needed, then it can always be looked up per-hyper
edge.
This is neither technically challenging nor CPU-intensive: the arity of
hyperedges is typically small, based on real-world mappings with interesting
datasets.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
We've worked with natural language, genomics and robotics datasets.
\end_layout
\end_inset
Thus, the vertex table can take the simpler form
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
vertex id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
incoming-set
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{1},e_{2},e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{2},e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{3},e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{4}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{2}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\begin_inset CommandInset label
LatexCommand label
name "hyper vertex table"
\end_inset
\end_layout
\begin_layout Standard
Note that the vertex table looks a lot like the edge table, the only difference
being that the vertex-list in the edge table is an ordered list, while
the incoming-set (the edge-set) really is a set.
Effectively, this is because a hypergraph is
\begin_inset Quotes eld
\end_inset
almost
\begin_inset Quotes erd
\end_inset
a bipartite graph, having the form below, with the set
\begin_inset Formula $E$
\end_inset
on the left being the set of hyperedges.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/hypergraph.eps
lyxscale 60
width 45col%
\end_inset
\end_layout
\begin_layout Standard
The boxes denote the fact that the hyperedges are ordered lists.
The
\begin_inset Formula $E$
\end_inset
and
\begin_inset Formula $V$
\end_inset
ellipses are the hyperedge and vertex tables.
If the boxes could be collapsed to single points, this would be a 'true'
bipartite graph; but they cannot be.
The ordering is needed and important.
\end_layout
\begin_layout Subsubsection
RAM Utilization
\end_layout
\begin_layout Standard
One might wish to conclude:
\begin_inset Quotes eld
\end_inset
Oh, but a bipartite graph is just a graph, so a graph database is sufficient
for all my needs.
\begin_inset Quotes erd
\end_inset
At some abstract level, this is perhaps true; at the CPU and RAM-consumption
level, it is not.
So, in this figure, attributes (the attr-data) are attached only to the
\begin_inset Formula $v_{k}$
\end_inset
and
\begin_inset Formula $e_{k}$
\end_inset
in the diagram; there is no attribute data attached to the lines in this
figure.
What's more, the lines in this figure are not directly recorded in any
tables; they are implicit only in the structure of the vertex and hyperedge
tables.
\end_layout
\begin_layout Standard
Counting the memory usage is instructive.
Lets assume that the size of the vertex-id and the edge-id are the same
– they are pointers or 64-bit ints – so each id requires 1 unit of RAM.
Assume that lists are either null-terminated or record a length, so that
a list of
\begin_inset Formula $n$
\end_inset
items requires
\begin_inset Formula $n+1$
\end_inset
units of storage.
Lets encode sets as lists, to make counting easy; let
\begin_inset Formula $\left\langle J\right\rangle $
\end_inset
be the average size of the attribute collection.
The hyperedges shown in the example figure then require 2+3+3+4=12 units
of storage, plus 5 more for the hyperedge table itself, and
\begin_inset Formula $4\left\langle J\right\rangle $
\end_inset
of attribute storage.
The vertexes require 4+3+3+2 units of storage, plus 5 for the vertex-table
itself, plus
\begin_inset Formula $4\left\langle J\right\rangle $
\end_inset
more of attributes.
Summing this, one obtains
\begin_inset Formula $34+8\left\langle J\right\rangle $
\end_inset
total RAM consumption.
\end_layout
\begin_layout Standard
For the general case, one has
\begin_inset Formula
\[
N_{V}\left(1+\left\langle J\right\rangle +\left\langle N_{I}\right\rangle \right)+N_{E}\left(1+\left\langle J\right\rangle +\left\langle N_{O}\right\rangle \right)
\]
\end_inset
where
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $N_{V}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Number of vertexes
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $N_{E}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Number of hyperedges
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\langle J\right\rangle $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Average size of attributes
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\langle N_{I}\right\rangle $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Average size of the incoming set
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\langle N_{O}\right\rangle $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Average size of the vertex list
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
The average count of the incoming set is equal to the average count of the
vertex list, so we can approximate
\begin_inset Formula $\left\langle N_{I}\right\rangle =\left\langle N_{O}\right\rangle $
\end_inset
; the only reason to track these separately is that one may use hash tables
or trees for sets, whereas lists require arrays.
This makes the RAM usage slightly different for the two.
\end_layout
\begin_layout Standard
The equivalent representation as a graph requires
\end_layout
\begin_layout Standard
\begin_inset Formula
\begin{align*}
\left(N_{V}+N_{E}\right)\left(1+\left\langle J\right\rangle \right)+N_{V}\left\langle N_{I}\right\rangle +N_{E}\left\langle N_{O}\right\rangle & \quad\mbox{ for the vertex table}\\
N_{V}\left\langle N_{I}\right\rangle \left(3+\left\langle J_{nil}\right\rangle \right) & \quad\mbox{ for the edge table}
\end{align*}
\end_inset
Comparing the this to the expression for the hypertable, we see that the
vertex table is the same size as the entire hypertable.
The ordinary graph representation also requires the overhead of the edge
table; here the
\begin_inset Formula $\left\langle J_{nil}\right\rangle $
\end_inset
is the cost of storing an empty attribute list, and the factor of 3 comes
from storing an ordinary edge-id and it's two endpoints.
Graph databases can store hypergraphs, but incur a RAM penalty for doing
so.
\end_layout
\begin_layout Subsubsection
Storing hypergraphs in graphs, and vice-versa
\end_layout
\begin_layout Standard
If the only thing that one is storing are hypergraphs, then having a custom
hypergraph representation really is smaller than the equivalent bipartite
graph: it dispenses with the need for an explicit ordinary-edge table.
Does this mean that there's some magic, here? No, not really.
Every ordinary graph is a special case of a hypergraph, where the hyper-edge
always has arity two.
To use an ordinary graph-store to record a single edge, we need
\begin_inset Formula $3+\left\langle J\right\rangle $
\end_inset
units of storage: the edge-label, and the two vertexes in the edge.
To use a hyperedge store to record a single (ordinary) edge, we need
\begin_inset Formula $4+\left\langle J\right\rangle $
\end_inset
units of storage: the edge-label, the list of vertexes, and the list terminator.
Thus, storing an ordinary graph as a hypergraph requires
\begin_inset Formula $N_{E}$
\end_inset
more units of storage.
This seems tolerable: for a million-edge graph, and 64-bit pointers, this
requires 8MBytes of additional storage.
On modern machines, the extra 8MBytes seems not all that large.
There's a bit of a penalty in moving from graph storage to hypergraph storage,
but it's not that much.
Modern cellphones have 8GBytes of RAM...
\end_layout
\begin_layout Standard
Moving in the opposite direction is much worse: the penalty is
\begin_inset Formula $N_{V}\left\langle N_{I}\right\rangle \left(3+\left\langle J_{nil}\right\rangle \right)$
\end_inset
which is surprisingly large.
Assuming that
\begin_inset Formula $\left\langle J_{nil}\right\rangle =1$
\end_inset
, then a million-vertex graph requires
\begin_inset Formula $\left\langle N_{I}\right\rangle $
\end_inset
times 32MBytes of additional storage.
For uniformly-distributed graphs, one might have
\begin_inset Formula $\left\langle N_{I}\right\rangle $
\end_inset
of 3 to 10; for scale-free graphs of this size,
\begin_inset Formula $\left\langle N_{I}\right\rangle $
\end_inset
might be around 14; for square-root-Zipfian graphs (such as Wikipedia page
views, or biological datasets: genome, proteome, reactome datasets) the
\begin_inset Formula $\left\langle N_{I}\right\rangle $
\end_inset
would be around 200,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The average size of the incoming set is
\begin_inset Formula
\[
\left\langle N_{I}\right\rangle =\frac{1}{N_{V}}\int_{1}^{N_{V}}n\left(v\right)dv
\]
\end_inset
where
\begin_inset Formula $n\left(v\right)$
\end_inset
is the number of connections to vertex
\begin_inset Formula $v$
\end_inset
and
\begin_inset Formula $N_{V}$
\end_inset
is the total number of vertexes.
For a Zipfian distribution, this is
\begin_inset Formula
\[
\left\langle N_{I}\right\rangle =\frac{1}{N_{V}}\int_{1}^{N_{V}}\frac{N_{V}}{v}dv=\log N_{V}
\]
\end_inset
while for a square-root-Zipfian, one has
\begin_inset Formula
\[
\left\langle N_{I}\right\rangle =\frac{1}{N_{V}}\int_{1}^{N_{V}}\frac{AN_{V}}{\sqrt{v}}dv=2A\sqrt{N_{V}}
\]
\end_inset
The scale factor
\begin_inset Formula $A$
\end_inset
is data-dependent.
For Wikipedia page views,
\begin_inset Formula $A\approx20$
\end_inset
, see
\begin_inset Flex URL
status collapsed
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Wikipedia:Does_Wikipedia_traffic_obey_Zipf
\backslash
%27s_law
\backslash
%3F
\end_layout
\end_inset
for graphs and discussion.
For genomics, see
\begin_inset Flex URL
status collapsed
\begin_layout Plain Layout
https://github.com/linas/biome-distribution/blob/master/paper/biome-distributions.
pdf
\end_layout
\end_inset
where
\begin_inset Formula $A$
\end_inset
is in the range of 0.1 to 0.3, depending on the dataset.
These last estimates are a bit glib, as the specifics of the datasets are
quite subtle.
Still, one may conclude that these considerations have quite dramatic implicati
ons for graph stores.
\end_layout
\end_inset
so we are looking at overheads in the gigabyte range.
There is a huge cost of jamming a hypergraph into an ordinary graph store.
\end_layout
\begin_layout Standard
XXX TODO This is making some rather strong claims about RAM usage, and really
needs to be quadruple-checked and strengthened.
It's a bit breezy and casual, as written.
XXX TODO.
\end_layout
\begin_layout Subsection
Metagraph representations
\end_layout
\begin_layout Standard
The metagraph differs from the hypergraph in that now a hyperedge (link)
may contain either another vertex (node) or another link.
Visually, this is no longer a bipartite graph, but has the shape of a directed
acyclic graph (DAG), such as the one shown below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/metagraph.eps
lyxscale 60
width 25col%
\end_inset
\end_layout
\begin_layout Standard
The primary difference between the above, and a 'true DAG' is that the links
are ordered lists, represented as boxes in this diagram.
For lack of a better name, this can be called a
\begin_inset Quotes eld
\end_inset
metatree
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Later on, metatrees will be called
\begin_inset Quotes eld
\end_inset
Atoms
\begin_inset Quotes erd
\end_inset
.
An Atom is simply a term for something that can be either a
\begin_inset Quotes eld
\end_inset
Node
\begin_inset Quotes erd
\end_inset
or a
\begin_inset Quotes eld
\end_inset
Link
\begin_inset Quotes erd
\end_inset
.
As we haven't yet clearly defined a Node or Link yet, the term
\begin_inset Quotes eld
\end_inset
metatree
\begin_inset Quotes erd
\end_inset
will suffice.
\end_layout
\end_inset
The metatree can be converted to a DAG in two different ways.
One way is to collapse the boxes to single points.
The other way is to dissolve the boxes entirely, and replace a single arrow
from point-to-box by many arrows, from point to each of the box elements.
Neither of these conversions are faithful.
The first erases the ordering within the box, while the second erases the
grouping that the box provides.
\end_layout
\begin_layout Standard
The node table for a metagraph is effectively the same as the hyper-vertex
table
\begin_inset CommandInset ref
LatexCommand vpageref
reference "hyper vertex table"
plural "false"
caps "false"
noprefix "false"
\end_inset
.
For the example metatree diagram, it is
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
node id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
incoming-set
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $n_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{1},e_{3}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $n_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{1},e_{2}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $n_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{2},e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\begin_inset CommandInset label
LatexCommand label
name "metagraph node table"
\end_inset
\end_layout
\begin_layout Standard
The link table now requires both an outgoing-atom list, and an incoming-link
set.
The incoming set can only consist of links; the outgoing list can consist
of either nodes or links.
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="4">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
link id
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
outgoing-list
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
incoming-set
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
attr-data
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(n_{1},n_{2}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{3}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(n_{2},n_{3}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{3}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(e_{1},e_{2},n_{1},e_{2}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ e_{4}\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{4}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left(e_{3},n_{3}\right)$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\left\{ \cdot\right\} $
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\begin_inset CommandInset label
LatexCommand label
name "metagraph link table"
\end_inset
\end_layout
\begin_layout Standard
The link table adds a column, as compared to the hypergraphs, and thus resembles
the vertex table
\begin_inset CommandInset ref
LatexCommand vpageref
reference "graph vertex table"
plural "false"
caps "false"
noprefix "false"
\end_inset
for an ordinary graph store: It has both 'incoming' and 'outgoing' sets.
There are two differences: the outgoing set is no longer a set, but a list.
The other is even stranger: the first column (the column of vertexes) has
been replaced by a column of links!
\end_layout
\begin_layout Standard
Perhaps we are making the wrong comparison? Oddly, it also resembles the
edge table (
\begin_inset CommandInset ref
LatexCommand vpageref
reference "graph edge table"
plural "false"
caps "false"
noprefix "false"
\end_inset
).
For ordinary directed graphs, each edge is a vertex pair.
The vertices of an edge may be termed the 'head vertex' and the 'tail vertex';
equivalently, the outgoing vertex and the incoming vertex (or
\emph on
vice-versa
\emph default
, depending on how one envisions the arrows).
These two endpoints are replaced by the incoming set and the outgoing list.
Now, the first column remains the same: a column of edges, in both cases.
The overall four-column form remains the same.
\end_layout
\begin_layout Standard
Looking at this table, one might imagine that the naive graph tables, the
hypergraph tables, and the metagraph tables seem to have much in common.
This is, however, perhaps a bit deceptive, as performance considerations
dictate the finer aspects of the design.
This will be looked at next.
\end_layout
\begin_layout Standard
The metagraph, having the general shape of a DAG, can clearly be wedged
into an ordinary graph store.
Conversely, an ordinary graph is merely a metagraph that never goes more
than one-level deep, and whose links are always arity-two.
Either format is adequate for representing the other.
The metagraph, much like the hypergraph, has no need to explicitly declare
the arrows in the tree; they are not stored, nor do they have attributes.
The RAM-usage considerations are much like those for the hypergraph.
We can conclude that it is quite efficient to store a graph in a metagraph,
but that storing a metagraph in an ordinary graph database pays a large
penalty.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Indexing
\end_layout
\begin_layout Standard
The above reviewed the basic structure of hypergraphs.
Database performance depends strongly on the use of indexes.
Thus, a practical hypergraph database design must address the use of indexes
and how they moderate performance.
This section will review the structure of indexes, or rather, the alternatives
one has for index representation.
The whole point of using a graph database, as opposed to a collection of
tables, or key-value database, or a JSON-database, is that the graph structure
encodes something important about the problem, something that cannot be
easily achieved by doing table joins or key-value look-ups.
Some examples of
\begin_inset Quotes eld
\end_inset
difficult
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
impossible
\begin_inset Quotes erd
\end_inset
queries will be looked at in a later section.
\end_layout
\begin_layout Standard
It is worth remarking that the so-called noSQL databases are effectively
'identical' to SQL databases.
They are 'identical' in the sense of being categorical opposites: the direction
s of all arrows are reversed.
This was explicitly articulated in a famous paper by Meijer and Bierman.
\begin_inset CommandInset citation
LatexCommand cite
key "Meijer2011"
literal "false"
\end_inset
Much of the following uses an SQL-style notation; if the reader is more
familiar with key-value databases, then simply reverse the directions of
all arrows to obtain the equivalent discussion.
\end_layout
\begin_layout Standard
A few comments are in order regarding the SQL-style query notation.
It has become dominant.
One can look at systems as different as SparQL and GraphQL, or even the
OGRE query language
\begin_inset CommandInset citation
LatexCommand cite
key "OGRE"
literal "false"
\end_inset
(
\emph on
op.
cit.
\emph default
) and clearly see not just the influence of SQL, but in fact a nearly verbatim
copy of it.
There is a reason for this dominance, and it is not (just) history.
The reason is anchored (once again) in table representations, and the presence
(or rather, lack thereof) of inbuilt indexes in the tables.
\end_layout
\begin_layout Standard
This is a good place to make a heretical claim: SQL or it's variants (GraphQL,
SparQL, ...) are
\emph on
NOT
\emph default
the best choice for a metagraph query language.
The shackles of *QL thinking are remarkably hard to escape.
Even the principled, category-theoretic foundations such as the Functorial
Query Language (FQL)
\begin_inset CommandInset citation
LatexCommand cite
key "Spivak2014"
literal "false"
\end_inset
fail to evade the problems presented here, primarily because it is still
table-based at it's heart (FQL is reviewed below, to illustrate several
problems).
A better alternative will become clear, once a more careful examination
is made of the role of indexes in queries.
\end_layout
\begin_layout Standard
In a metagraph database, just as in a table-based database, there will be
certain types of queries that are used a lot, and speeding these up through
indexing is a key requirement.
How might this work, in practice? Let's examine some queries, and see how
they might work.
\end_layout
\begin_layout Subsection
Single attribute queries
\end_layout
\begin_layout Standard
Suppose one wishes to find all nodes with some specific attribute.
Naively, this requires walking over all nodes, examining the attached attribute
structure, extracting a named field from the attributes, and examining
the value of that field.
This is a task that SQL databases excel at - for example,
\size small
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
SELECT name,salary FROM employees WHERE department='sales';
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The author would like to apologize for this seemingly non-sexy example.
It is the stereotypical example from database textbooks, and harks back
to the 1960's, when working out the fine details of management science
actually was a sexy research topic, and helped power the economic ascent
of the Western world.
It's importance should not be under-estimated: Ancient Rome was an agrarian
civilization built on concepts of hierarchical organization; organizational
hierarchies will continue to describe reality, including AGI.
Org-charts are boring but important.
\end_layout
\end_inset
A graph database is not needed for this task.
Nonetheless, this is a plausible task, even for a graph database.
The traditional solution would be
\shape italic
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
CREATE INDEX ON employees(department);
\family default
\shape default
\size default
\begin_inset Quotes erd
\end_inset
which results in the creation of ordered pairs
\begin_inset Formula $\left(D,\left\{ R\right\} \right)$
\end_inset
with
\begin_inset Formula $D$
\end_inset
the name of the department, and
\begin_inset Formula $\left\{ R\right\} $
\end_inset
the set of all records having that value.
The
\family sans
\size footnotesize
\emph on
SELECT
\family default
\size default
\emph default
is then straight-forward: given
\begin_inset Formula $D$
\end_inset
, it need only return
\begin_inset Formula $\left\{ R\right\} $
\end_inset
.
The size of this index is
\begin_inset Formula $O\left(N\right)$
\end_inset
where
\begin_inset Formula $N$
\end_inset
is the number of employees.
This is necessarily so: one cannot build an index smaller than the number
of employees: every employee must be in some department, as, conventionally,
table-driven databases don't have null entries in rows.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Well, in practice, they often do; but now imagine the task of finding all
records with a null value in some column...
\end_layout
\end_inset
The point of the index is to replace an
\begin_inset Formula $O\left(N\right)$
\end_inset
cpu-time search with an
\begin_inset Formula $O\left(1\right)$
\end_inset
cpu-time search.
The price of doing so was an
\begin_inset Formula $O\left(N\right)$
\end_inset
or
\begin_inset Formula $O\left(N\log N\right)$
\end_inset
RAM structure.
\end_layout
\begin_layout Standard
Table-based information has certain kinds of representational difficulties:
imagine the case of an employee with dashed-line reporting to multiple
departments.
This might motivate one to cast an eye towards graph databases.
\end_layout
\begin_layout Standard
How might one accomplish indexing like this in a graph database? The simplest,
most naive answer is to create new,
\begin_inset Quotes eld
\end_inset
privileged
\begin_inset Quotes erd
\end_inset
vertexes, one vertex per department.
They are
\begin_inset Quotes eld
\end_inset
privileged
\begin_inset Quotes erd
\end_inset
, in that the associated attributes record one and only one value: the name
of the department.
Basically, the vertexes are labeled, thus escaping the overhead of crawling
through a collection of attributes to find one in particular.
One also creates an unlabeled, attribute-free edge, from the department
name back to the full employee record.
Finding all employees in
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sales
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
is fast: one searches the vertex table (
\begin_inset CommandInset ref
LatexCommand vpageref
reference "graph vertex table"
plural "false"
caps "false"
noprefix "false"
\end_inset
) to find the vertex
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sales
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
, and then traces all outgoing edges to the full record.
The graph can be thought of as a table with a special
\begin_inset Quotes eld
\end_inset
built in
\begin_inset Quotes erd
\end_inset
index: the index of outgoing edges.
\end_layout
\begin_layout Standard
This is to be contrasted to a conventional table database.
The contents of a conventional table (row) database, after indexing, is
illustrated below.
Before indexing, the vertexes
\begin_inset Formula $v_{6},v_{7},v_{8}$
\end_inset
and edges
\begin_inset Formula $e_{1},e_{2},e_{3},e_{4},e_{5}$
\end_inset
simply did not exist.
The act of indexing creates these vertexes and edges.
The documentation for conventional table databases does not 'talk about'
vertexes and edges; but,
\emph on
de facto
\emph default
, this is how system architects think about things.
When they think about creating an index on a table, this is what they think
of.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is not meant to be a psychological assessment; rather it is meant to
provide a translation between the 'algebraic' form of typed commands sent
to relational DB's, and an equivalent 'geometric', visual form.
It is the denotational semantics of the index.
The geometric form can be understood as being either metaphorical and abstract,
or it can be taken literally, as a collection of pointers and the things
they point to.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/partial-index.eps
width 80col%
\end_inset
\end_layout
\begin_layout Standard
The size of this structure is again
\begin_inset Formula $O\left(N\right)$
\end_inset
for
\begin_inset Formula $N$
\end_inset
employees, assuming every employee is indexed.
More precisely, it is
\begin_inset Formula $O\left(N\right)+O\left(N_{D}\right)$
\end_inset
where
\begin_inset Formula $N_{D}$
\end_inset
is the number of departments.
\end_layout
\begin_layout Standard
This diagram exposes some unusual possibilities: If one is interested only
in sales, then not every employee has to be indexed! In a graph database,
it is possible to create only one vertex,
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sales
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
, and hook up edges to only that one.
Effectively, this is a partial index, with correspondingly less RAM usage!
This is not possible in a naive table system; one needs a system which
explicitly supports partial indexes.
As it happens, most-all SQL systems do.
An experienced SQL DBA knows exactly how to achieve this effect:
\shape italic
\size small
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
CREATE INDEX ON employees(department) WHERE department=sales;
\family default
\shape default
\size default
\begin_inset Quotes erd
\end_inset
This is not a big deal, and so, here, at least, graphs do not offer any
particular advantage, other than perhaps some conceptual clarity.
Under the covers, the SQL databases effectively have more-or-less the same
format, although their internal graph-based nature is
\emph on
ad hoc
\emph default
, evolved over the decades and mostly hidden from the user.
There are no explicit graph-walking directives in SQL.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Aside from table joins; more on that later.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The key point here is that, in a properly-designed graph database, there
is no generic need for
\begin_inset Quotes eld
\end_inset
indexes
\begin_inset Quotes erd
\end_inset
\emph on
per se
\emph default
, they can be conjured into being at any time, as they are ultimately graphical
in nature.
There's even a bit of an advantage: in the graph database, the graph structure
of the index is explicit, and can be walked.
\end_layout
\begin_layout Subsection
Space and Time
\end_layout
\begin_layout Standard
Comparing RAM-usage, at first glance, there is no particular difference
between the SQL and the graph database.
Naively, both require
\begin_inset Formula $O\left(N\right)$
\end_inset
for
\begin_inset Formula $N$
\end_inset
employees, plus
\begin_inset Formula $O\left(N_{D}\right)$
\end_inset
for
\begin_inset Formula $N_{D}$
\end_inset
different departments.
Looking more carefully, there are also the edges
\begin_inset Formula $e_{1},e_{2},e_{3},e_{4},e_{5}$
\end_inset
.
In the SQL case, these edges were implicit in the index: after all, the
index was a collection of ordered pairs
\begin_inset Formula $\left(D,\left\{ R\right\} \right)$
\end_inset
: the edges run from
\begin_inset Formula $D$
\end_inset
to
\begin_inset Formula $\left\{ R\right\} $
\end_inset
.
In the graph representation, these edges become explicit: that is, they
appear in an explicit table, with attached attributes, even if the attributes
are null.
Shades of hypergraphs! Why, this was exactly the
\emph on
same
\emph default
situation as with the hypergraph! Squinting more carefully, the indexed
employee table is nothing other than a bipartite graph! Thus, one can effective
ly say: the indexes in an SQL database are
\emph on
de facto
\emph default
hypergraphs under the covers, even though no one ever explicitly says so.
The bipartite nature of the graph makes this overt.
Surprise!
\end_layout
\begin_layout Standard
The explicit hypergraph representation does cost more than its implicit
form in SQL databases.
An SQL index can be a b-tree or hash table; the only thing that the b-tree/hash
table needs to store is the row ID.
For a hypergraph, we have imposed the additional requirement that hypergraphs
must be rapidly traversable.
This forces the storage of the incoming set in addition to the outgoing
set.
Hypergraph stores necessarily use more RAM than equivalent SQL tables.
But recall why we did this: rapid graph traversal.
Graph traversal in SQL is easy for trivial graphs, but becomes profoundly
challenging for anything more complex.
Mashing up
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
SELECT INTO
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
with
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
JOIN
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
is tough.
Mashing it up two levels deep is tougher.
Can you count to three? It would be a significant challenge, even for experienc
ed DBAs.
Some more examples of challenging queries will be presented later.
\end_layout
\begin_layout Standard
Suppose you are clever enough to write deep table joins in SQL.
Is your query planner as clever as you? Most SQL systems have a query analyzer
or query compiler, which takes a given SQL statement, analyzes its structure,
and then creates a plan as to which data shall be fetched first, and in
what order.
Poor planning results in poor performance, sometimes disastrously poor
performance.
For large databases, there has been a vast (multi-billion-dollar) investment
in sophisticated query planning.
Walking graphs, represented in terms of tables and indexes, is not for
the faint of heart.
\end_layout
\begin_layout Standard
CPU usage considerations are harder to dissect.
To avoid discussions of network overhead in client-server architectures,
its easier, here, to limit discussions to databases that run in the same
address space as the application.
Thus, for SQL bench-marking, one might look at SQLite, which runs embedded,
rather than Postgres, which requires network interfaces.
Queries usually begin life as text-strings, for example,
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
SELECT name, salary FROM employees WHERE department='sales';
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
was a text-string that had to be parsed to figure out
\begin_inset Quotes eld
\end_inset
what to do
\begin_inset Quotes erd
\end_inset
.
Let's assume that this cost has been amortized, and that there is a way
to get a handle to a query that has already been analyzed.
Query run-time execution is then a matter of finding the vertex
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sales
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
, tracing the edges to each of the employees, and completing the work by
extracting fields for each employee.
If vertexes themselves are indexed (as they should be), then locating the
vertex
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sales
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
is either
\begin_inset Formula $O\left(1\right)$
\end_inset
for hash tables, or
\begin_inset Formula $O\left(\log N_{D}\right)$
\end_inset
for trees.
In the hypergraph representation, finding the set
\begin_inset Formula $\left\{ R\right\} $
\end_inset
of employees in
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sales
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
comes for free.
That is, if you have
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sales
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
, you already have the set
\begin_inset Formula $\left\{ R\right\} $
\end_inset
and no further lookups are required.
The dominant cost is almost surely the procedures needed to extract the
desired information from the record attributes.
\end_layout
\begin_layout Subsection
Partial indexes and metagraphs
\end_layout
\begin_layout Standard
The power of partial indexes together with metagraphs begins to reveal itself
when one considers query and search optimization.
Some key aspects of this are reviewed in the next two sections.
\end_layout
\begin_layout Standard
Partial indexes reveal their utility in another way.
Sticking with the management example from above, consider extending and
looking at organizational structures (org charts).
\end_layout
\begin_layout Standard
Conventionally, corporations, political and military organizations are organized
hierarchically, with divisions reporting to executives, departments rolling
up into divisions, and so on.
This is precisely the structure of a metatree.
It is tempting to gloss this, and say that the org chart is a tree, or
perhaps a DAG.
It is not! It is a metatree, and confusion arises because a metatree can
be collapsed to a DAG in several different ways.
So, consider a division chief who manages a line item.
One can draw the org-chart several ways: by drawing an edge from a manager
to each (named) employee that they manage, or from the manager to a functional
box labeled with the function.
Employees are then grouped inside these functional boxes.
This is shown below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/org-chart.eps
lyxscale 70
width 35col%
\end_inset
\end_layout
\begin_layout Standard
This is manifestly in the shape of a metatree.
It can be collapsed down to an ordinary directed tree in several ways,
left to the imagination of the reader.
The point is that the natural structure of an org chart is not a naive
tree; it contains a bit more complexity than that, and is far more readily
represented with a metatree.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is hardly the only way to represent an org-chart with a meta-tree.
One could put the department titles into boxes of their own, as well as
perhaps the names of the actual people, adding even some dashed-line cross-func
tional reporting structures.
The point here is that it is not
\begin_inset Quotes eld
\end_inset
just a tree
\begin_inset Quotes erd
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The conceptual jump here is then: rather than stopping with a single-level
hypergraph, which had
\begin_inset Quotes eld
\end_inset
tables
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
indexes
\begin_inset Quotes erd
\end_inset
that were
\begin_inset Quotes eld
\end_inset
on top of tables
\begin_inset Quotes erd
\end_inset
, one can go further: indexes of indexes: namely, the metagraph.
\end_layout
\begin_layout Subsection
Normalization
\end_layout
\begin_layout Standard
The implication for RAM usage is similar to that of
\begin_inset Quotes eld
\end_inset
database normalization
\begin_inset Quotes erd
\end_inset
.
In a naive, un-normalized table format, one might store, for each employee,
the employee name, the department, the 2nd line, the division and the name
of the company.
This is a bit silly in terms of storage: 5 columns are needed; for
\begin_inset Formula $N$
\end_inset
employees, this requires
\begin_inset Formula $O\left(5N\right)$
\end_inset
storage.
One
\begin_inset Quotes eld
\end_inset
normalizes
\begin_inset Quotes erd
\end_inset
by storing only the employee-department relationship with a table of
\begin_inset Formula $O\left(2N\right)$
\end_inset
in size, and the remainder of the org chart in a separate table, also of
two columns, encoding the directed tree reporting structure.
This offers a huge space savings.
For
\begin_inset Formula $N_{D}$
\end_inset
departments/divisions, this second table is
\begin_inset Formula $O\left(2N_{D}\right)$
\end_inset
and clearly,
\begin_inset Formula $5N\gg2N+2N_{D}$
\end_inset
.
\end_layout
\begin_layout Standard
Look-ups in a normalized database proceed through table joins.
To find all employees in a division, one looks up what 2nd lines report
to the division, what departments report to the second line, and what employees
report to the departments (this is the 'transitive closure' of a recursive
relation.) The indexing proceeds just as described before.
The table joins are an
\emph on
ad hoc
\emph default
graph walk.
The SQL for this is a bit nasty, but still effectively human-readable:
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
SELECT employees.name FROM employees, orgchart WHERE employees.department
= orgchart.dept AND orgchart.division = 'marketing & sales';
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Its nasty, because we have to
\begin_inset Quotes eld
\end_inset
join
\begin_inset Quotes erd
\end_inset
different rows in the org chart table.
SQL does not offer any basic primitives for joining different rows together;
this requires a good bit of creativity on the part of the DBA.
\end_layout
\end_inset
This SQL snippet is oversimplified by quite a bit, but it does convey the
general spirit of the thing.
It is attempting to specify a graph-walk without explicitly acknowledging
that there is a graph hidden under the covers.
\end_layout
\begin_layout Standard
The key message here is that metagraphs retain the key benefits of table
normalization, while making the graphical nature of indexing explicit.
They do even more: they effectively
\begin_inset Quotes eld
\end_inset
automate
\begin_inset Quotes erd
\end_inset
table normalization.
To some fairly large degree, you no longer have to explicitly think about
table normalization.
It
\begin_inset Quotes eld
\end_inset
just happens naturally
\begin_inset Quotes erd
\end_inset
, as you organize data into graphical form.
This is not because there is some super-clever algo running under the covers,
performing magic normalization.
It is instead purely a byproduct of changing one's perspective about data
and it's structure.
\end_layout
\begin_layout Standard
Comparing metagraphs to graph stores, one sees a different improvement.
By discarding the edge table (
\begin_inset CommandInset ref
LatexCommand vpageref
reference "graph edge table"
plural "false"
caps "false"
noprefix "false"
\end_inset
) that the graph store demands, and the associated edge attributes, one
gets the representational compactness of indexes, without paying a high
price for them.
The price one does pay (the incoming set of the metagraph link table
\begin_inset CommandInset ref
LatexCommand vpageref
reference "metagraph link table"
plural "false"
caps "false"
noprefix "false"
\end_inset
) enables something quite dramatic: an easy graph walk, which is anything-but-ea
sy in a traditional SQL database.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
OK, sure, it becomes
\begin_inset Quotes eld
\end_inset
easy
\begin_inset Quotes erd
\end_inset
if you are willing to write PL/SQL, or embedded Python, if your database
supports it.
Otherwise, you have to descend into C/C++ (or your favorite programming
language of choice), and once you are
\begin_inset Quotes eld
\end_inset
programming
\begin_inset Quotes erd
\end_inset
, it is no longer
\begin_inset Quotes eld
\end_inset
easy
\begin_inset Quotes erd
\end_inset
.
A properly designed graph query system makes (should make) graph walks
\begin_inset Quotes eld
\end_inset
easy
\begin_inset Quotes erd
\end_inset
.
A properly-designed metagraph query system makes graph walks invisible
(see next section.) And, to take one quick pot-shot: GraphQL is not properly
designed.
It is effectively a query anti-pattern.
It took what is nice about SQL, but then utterly failed to take into account
anything and everything that this text is trying to explain.
It is not for nothing that the OpenCog AtomSpace differs so dramatically
from everything else out there.
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Index Maintenance
\end_layout
\begin_layout Standard
Indexes are central to defining the relationships between bits of data.
But such relationships cannot stay fixed: as a database is used, reasons
are found to add new relationships, and to modify or delete existing relationsh
ips.
Practical issues arise: changes must be made without corrupting existing
data or (unintentionally) losing information.
\end_layout
\begin_layout Standard
This proves to be a particular challenge to SQL-style databases, and it
is educational to review the reasons.
In an SQL system, the relationships between bits of data are defined by
the initial database architect: the person who first creates the table
definitions, the
\begin_inset Quotes eld
\end_inset
database schema
\begin_inset Quotes erd
\end_inset
.
Changes to those definitions (additions of new tables, the reorganization
of columns in existing tables,
\emph on
etc.
\emph default
) requires a process of
\begin_inset Quotes eld
\end_inset
data migration
\begin_inset Quotes erd
\end_inset
.
It is conceived in this way, since one is changing not just a table definition,
but one is also moving all of the rows in that table.
This is a CPU and RAM-consuming process: for tables with millions of rows,
or more, this may take hours or days.
When migrating datasets, it is very important to not accidentally corrupt
the structures containing the data through poor data migration design (
\emph on
e.g.
\emph default
by unintentionally dropping columns, or by breaking primary-key-foreign-key
constraints, or breaking normalization by duplicating data).
A means of performing database schema migrations in an accident-free way
is important.
Defining a principled approach to table rewrites is even better.
\end_layout
\begin_layout Standard
The Functorial Query Language (FQL) provides such a principled approach.
\begin_inset CommandInset citation
LatexCommand cite
key "Spivak2014"
literal "false"
\end_inset
It is reviewed below.
The key observation here will be that data migration (database schema migration
) can be thought of as a form of rewriting, analogous to the idea of term
rewriting or graph rewriting.
Looked at more strongly, this is more than an analogy: table rewriting
\emph on
is
\emph default
graph rewriting.
The idea to be examined here is this: If one keeps the adjoint functors
\begin_inset Formula $\Sigma\dashv\Delta\dashv\Pi$
\end_inset
of FQL, but discards the SQL tables on which they are founded, can the
FQL approach provide a principled means for rewriting graphs? The answer
appears to hinge on the question of how indexes are conceived of within
the system, how they are maintained.
\end_layout
\begin_layout Subsubsection
Data Migration and Graph Rewriting
\end_layout
\begin_layout Standard
The concept of data migration in database practice refers to the idea that,
after a system architect or data architect has designed some database,
and a company has populated that database with millions of records, at
the expense of millions of dollars, it is realized that the original design
of the database schemas are inadequate to meet future business needs.
The data needs to be migrated to a new set of schemas.
\end_layout
\begin_layout Standard
It is often the case that the data is so voluminous, and so valuable, that
it will take months of system architect effort and weeks of management
review before one can press the button and cross one's fingers, hoping
that nothing is lost or corrupted.
Mistakes are not hard to make: some important
\family sans
\shape italic
\size footnotesize
PRIMARY KEY
\family default
\shape default
\size default
-
\family sans
\shape italic
\size footnotesize
FOREIGN KEY
\family default
\shape default
\size default
constraint might be accidentally dropped.
Maybe some column will be forgotten about.
Maybe normalization will be broken, resulting in duplicated data appearing
in multiple tables, with no means of keeping that duplicated data in sync,
leading to long-term data rot.
It sure would be nice to do data migrations in a less time-consuming, less
error prone fashion.
This requires a principled approach; but how?
\end_layout
\begin_layout Standard
Well, what is data migration really, at the most abstract level? It is a
graph rewrite.
The initial database design should be understood to be a graph, with the
various key constraints between tables being the directed edges of the
graph.
The revised database design, with its new table schemas, is a different
graph.
The goal of the data migration is to rewrite the first graph into the second.
Data migration is in fact graph rewriting, but narrowly conceived.
\end_layout
\begin_layout Standard
Looked at this way, the situation is jarring.
In the former case, data migration is a difficult, time-consuming manual
process playing out at a human timescale.
In the later case, any given graph rewriting system or term rewriting system
is expected to do it's operations in milliseconds.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See, for example, Maude,
\begin_inset CommandInset citation
LatexCommand cite
key "Maude1999"
literal "false"
\end_inset
a term rewriting system that stands on it's own, disassociated from any
other processing system.
\end_layout
\end_inset
How is it these two scales are so different?
\end_layout
\begin_layout Standard
The idea of doing data migrations in hours instead of days is radical; the
idea of doing it automatically at millisecond speeds is revolutionary.
Moving forward in the domain of knowledge representation requires bridging
this gap.
If one has data represented one way, one must be able to efficiently, rapidly
and easily transform it into a different representation.
Even more: for AGI, such rewrites must be fully automated and automatic.
\end_layout
\begin_layout Standard
To make data migration easy, one needs to be able to represent the graph
rewrites within the system itself.
Later sections will describe a metaquery system that accomplishes this.
This is in contrast to the situation with SQL.
The graph that is the schema of an SQL database is not itself stored in
a table, nor is it queryable with SQL commands.
When a DBA hand-crafts an SQL expression to perform a graph rewrite, they
do not store that expression within the database itself; it exists externally,
in a distinct location.
By working with metagraphs, it turns out that it is not hard to craft a
query system in which the queries themselves live as data within the database.
\end_layout
\begin_layout Subsubsection
Graph Rewriting and Indexes
\end_layout
\begin_layout Standard
The second part of automating rewrites of knowledge representation schemas
is to provide a principled approach.
One such principled approach can be found in the Functorial Query Language
(FQL).
\begin_inset CommandInset citation
LatexCommand cite
key "Spivak2014"
literal "false"
\end_inset
This theoretical development has a working open-source implementation called
Categorical Query Language (CQL).
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://github.com/CategoricalData
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://www.categoricaldata.net/
\end_layout
\end_inset
.
\end_layout
\end_inset
The approach is founded on category theory,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Category_theory
\end_layout
\end_inset
.
\end_layout
\end_inset
and so the remainder of this section will switch to that language.
The reader unfamiliar with category theory is encouraged to learn it.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
A reasonable introduction, adapted for software developers, is
\begin_inset Quotes eld
\end_inset
Category Theory for Programmers
\begin_inset Quotes erd
\end_inset
, Bartosz Milewski (2019), available at
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://github.com/hmemcpy/milewski-ctfp-pdf
\end_layout
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Basic definitions are in order.
A database schema
\begin_inset Formula $\mathcal{C}$
\end_inset
is a category.
The objects of that category are the tables; the morphisms of that category
are the indexes.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
More precisely, the category is the database schema; see Wikipedia
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Database_schema
\end_layout
\end_inset
.
This includes not just the tables and the indexes, but also all of the
triggers, stored procedures, queues, views and other elements.
For simplicity, we consider only the tables as the objects, and the integrity
constraints (the indexes) as the morphisms.
\end_layout
\end_inset
For example, given any particular row in some table, the index provides
a map from that row to some other row in some other table.
It provides the morphism between them.
The morphisms are pointer-chases, in that both are composable: given some
row, one can chase the pointer to some other row in some other table, and
then repeat this again.
\end_layout
\begin_layout Standard
An instance of a database is a functor
\begin_inset Formula $\mathcal{C}\to\mathbf{Set}$
\end_inset
.
That is, the database schema
\begin_inset Formula $\mathcal{C}$
\end_inset
itself is just the collection of empty tables, and the indexes between
them.
To populate a database with data, one must specify what goes into it.
For example, given a table of employees, there is a corresponding set of
employees that go into that table.
The mapping is from
\begin_inset Formula $\mathcal{C}$
\end_inset
to
\begin_inset Formula $\mathbf{Set}$
\end_inset
and not the other way around, because it is
\begin_inset Quotes eld
\end_inset
forgetful
\begin_inset Quotes erd
\end_inset
: the morphisms in
\begin_inset Formula $\mathbf{Set}$
\end_inset
are functions from one set to another, but they do not describe how the
individual elements of the set are to be paired up: those relationships
are forgotten.
All that remains of the database index morphism is the idea that it connected
one set to another, without specifying how the elements of the set are
connected.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Category_of_sets
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Forgetful_functor
\end_layout
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Two different database instances
\begin_inset Formula $I$
\end_inset
and
\begin_inset Formula $J$
\end_inset
(for the same schema
\begin_inset Formula $\mathcal{C}$
\end_inset
) differ by the addition, deletion or modification of rows in various tables.
The relationship between them can be phrased as a homomorphism: it maps
tables to tables (obviously) and rows to rows.
Deleted rows are mapped to the
\begin_inset Quotes eld
\end_inset
empty row
\begin_inset Quotes erd
\end_inset
, and modified rows to their modifications.
Added rows are not part of the homomorphism.
Since the instances
\begin_inset Formula $I$
\end_inset
and
\begin_inset Formula $J$
\end_inset
are both functors
\begin_inset Formula $\mathcal{C}\to\mathbf{Set}$
\end_inset
, the homomorphism between them turns out to be a
\begin_inset Quotes eld
\end_inset
natural transformation
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $I\Rightarrow J$
\end_inset
in that it obeys all of the requirements for being one.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Natural_transformation
\end_layout
\end_inset
.
It is a non-trivial and worthwhile exercise to verify that two different
database instances, defined as functors, obey the requirements for being
related to one-another as a natural transformation.
\end_layout
\end_inset
This allows the category
\begin_inset Formula $\mathcal{C}\mbox{-}\mathbf{Inst}$
\end_inset
to be defined, the objects of which are the instances
\begin_inset Formula $I$
\end_inset
, and the morphisms are the natural transformations
\begin_inset Formula $I\Rightarrow J$
\end_inset
.
\end_layout
\begin_layout Standard
A schema mapping is a functor
\begin_inset Formula $F:\mathcal{C}\to\mathcal{D}$
\end_inset
from a database schema
\begin_inset Formula $\mathcal{C}$
\end_inset
to
\begin_inset Formula $\mathcal{D}$
\end_inset
.
To be a functor, it must provide maps between the objects of each:
\begin_inset Formula $\mathit{tables}\left(\mathcal{C}\right)\to\mathit{tables}\left(\mathcal{D}\right)$
\end_inset
and between the morphisms of each:
\begin_inset Formula $\mathit{indexes}\left(\mathcal{C}\right)\to\mathit{index\mbox{-}paths}\left(\mathcal{D}\right)$
\end_inset
.
A data migration is then a lifting of this functor
\begin_inset Formula $F$
\end_inset
to a functor on
\begin_inset Formula $\mathcal{C}\mbox{-}\mathbf{Inst}$
\end_inset
to
\begin_inset Formula $\mathcal{D}\mbox{-}\mathbf{Inst}$
\end_inset
.
The FQL paper points out there is not just one such lifting, but three:
a contravariant functor
\begin_inset Formula $\Delta_{F}$
\end_inset
and it's left and right adjoints
\begin_inset Formula $\Sigma_{F}$
\end_inset
and
\begin_inset Formula $\Pi_{f}$
\end_inset
.
The contravariant functor
\begin_inset Formula $\Delta_{F}$
\end_inset
is defined by composition with a particular database instance:
\begin_inset Formula
\begin{align*}
\Delta_{F}: & \mathcal{C}\mbox{-}\mathbf{Inst}\to\mathcal{D}\mbox{-}\mathbf{Inst}\\
& I\mapsto\Delta_{F}I=I\circ F
\end{align*}
\end_inset
where a specific database instance
\begin_inset Formula
\[
I:\mathcal{C}\to\mathbf{Set}
\]
\end_inset
is mapped to
\begin_inset Formula
\[
\Delta_{F}I:F\left(\mathcal{C}\right)\to\mathbf{Set}
\]
\end_inset
where (of course, by definition)
\begin_inset Formula $\mathcal{D}=F\left(\mathcal{C}\right)$
\end_inset
, and so one can write
\begin_inset Formula
\[
\Delta_{F}I:\mathcal{D}\to\mathbf{Set}
\]
\end_inset
This is perhaps clearer with a diagram:
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
[
\backslash
begin{tikzcd}
\end_layout
\begin_layout Plain Layout
\backslash
mathcal{C}
\backslash
arrow[r,
\begin_inset Quotes erd
\end_inset
F
\begin_inset Quotes erd
\end_inset
]
\backslash
arrow[dr,
\begin_inset Quotes erd
\end_inset
\backslash
Delta_{F}I
\begin_inset Quotes erd
\end_inset
'] &
\backslash
arrow[d,
\begin_inset Quotes eld
\end_inset
I
\begin_inset Quotes erd
\end_inset
]
\backslash
mathcal{D}
\backslash
\backslash
\end_layout
\begin_layout Plain Layout
&
\backslash
mathbf{Set}
\end_layout
\begin_layout Plain Layout
\backslash
end{tikzcd}
\backslash
]
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Adjoint to the functor
\begin_inset Formula $\Delta_{F}$
\end_inset
is the left-adjoint functor
\begin_inset Formula $\Sigma_{F}\dashv\Delta_{F}$
\end_inset
, which acts as giver of an initial mapping, and the right adjoint
\begin_inset Formula $\Delta_{F}\dashv\Pi_{F}$
\end_inset
which provides a terminal mapping.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Adjoint_functors
\end_layout
\end_inset
.
See also
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Initial_and_terminal_objects
\end_layout
\end_inset
.
\end_layout
\end_inset
These two functors then provide an efficient, formulaic way to migrate
data from one database schema to another.
\end_layout
\begin_layout Standard
But what does all this abstract nonsense mean, anyway? Informally, all it
is saying is
\begin_inset Quotes eld
\end_inset
keep your indexes straight, and you'll be OK.
\begin_inset Quotes erd
\end_inset
Understanding this is best served by an example.
\end_layout
\begin_layout Subsubsection
A Data Migration Example
\end_layout
\begin_layout Standard
TODO: provide worked example.
Conclude: its still tables, in the end.
That is, FQL/CQL is formulated explicitly in terms of tables.
The abstraction, in terms of category theory, does not escape the underlying
table structure.
Yes, the schema mapping
\begin_inset Formula $F:\mathcal{C}\to\mathcal{D}$
\end_inset
is a pure graph re-write.
However, the functor
\begin_inset Formula $\Delta_{F}$
\end_inset
acts on tables, by design, since
\begin_inset Formula $\mathcal{C}\mbox{-}\mathbf{Inst}$
\end_inset
consists of populated tables (by design).
The functors just tell you how to not accidentally lose
\family sans
\shape italic
\size footnotesize
PRIMARY KEY
\family default
\shape default
\size default
-
\family sans
\shape italic
\size footnotesize
FOREIGN KEY
\family default
\shape default
\size default
constraints.
It does not provide particular insight into graph rewriting, in general.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Metatrees and String Representations
\end_layout
\begin_layout Standard
The discusion of metagraphs above has presented their abstract graphical
structure, and what the corresponding in-RAM data structure looks like.
Another important representation is the string representation: how can
a meta-tree be written as a text string? The proper representation as a
string can be mildly confusing.
Articulating this carefully is rewarding.
Consider again the generic example:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/metagraph.eps
lyxscale 60
width 23col%
\end_inset
\end_layout
\begin_layout Standard
This can be written as
\begin_inset Formula $\left(e_{4}:\left(e_{3}:\left(e_{1}:n_{1},n_{2}\right),\left(e_{2}:n_{2},n_{3}\right),n_{1},\left(e_{2}:n_{2},n_{3}\right)\right),n_{3}\right)$
\end_inset
or perhaps, with indentation, but without parenthesis, so as to improve
readability (so, Python-style,
\emph on
i.e.
\emph default
with
\begin_inset Quotes eld
\end_inset
significant whitespace
\begin_inset Quotes erd
\end_inset
):
\begin_inset Formula
\[
\begin{array}{cccc}
e_{4}: & e_{3}: & e_{1}: & n_{1}\\
& & & n_{2}\\
& & e_{2}: & n_{2}\\
& & & n_{3}\\
& & n_{1}\\
& & e_{2}: & n_{2}\\
& & & n_{3}\\
& n_{3}
\end{array}
\]
\end_inset
Alternately, in Unix directory style (URLs), with slashes.
Each
\begin_inset Formula $e_{k}$
\end_inset
and its trailing slash denotes a subdirectory.
Each
\begin_inset Formula $n_{k}$
\end_inset
denoting a file: the terminal leaf in the tree.
Observe that the same file appears in multiple locations in the directory
tree.
This is accomplished with either hard or soft links ('
\family typewriter
man ln
\family default
').
It is somewhat uncommon for ordinary users to do this, but is a widespread
technique used in package installs.
\begin_inset Formula
\[
\begin{array}{cccc}
e_{4}/ & e_{3}/ & e_{1}/ & n_{1}\\
& & & n_{2}\\
& & e_{2}/ & n_{2}\\
& & & n_{3}\\
& & n_{1}\\
& & e_{2}/ & n_{2}\\
& & & n_{3}\\
& n_{3}
\end{array}
\]
\end_inset
Either of these requires understanding indentation.
Yuck.
Even if you understand the indentation, the above are still hard to read.
Perhaps JSON will do:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
{
\end_layout
\begin_layout Plain Layout
Link: {
\end_layout
\begin_layout Plain Layout
Link: {
\end_layout
\begin_layout Plain Layout
Link: {
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
one
\begin_inset Quotes erd
\end_inset
,
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
two
\begin_inset Quotes erd
\end_inset
\end_layout
\begin_layout Plain Layout
},
\end_layout
\begin_layout Plain Layout
Link: {
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
two
\begin_inset Quotes erd
\end_inset
,
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
three
\begin_inset Quotes erd
\end_inset
\end_layout
\begin_layout Plain Layout
},
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
one
\begin_inset Quotes erd
\end_inset
,
\end_layout
\begin_layout Plain Layout
Link: {
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
two
\begin_inset Quotes erd
\end_inset
,
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
three
\begin_inset Quotes erd
\end_inset
\end_layout
\begin_layout Plain Layout
}
\end_layout
\begin_layout Plain Layout
},
\end_layout
\begin_layout Plain Layout
Node:
\begin_inset Quotes eld
\end_inset
three
\begin_inset Quotes erd
\end_inset
\end_layout
\begin_layout Plain Layout
}
\end_layout
\begin_layout Plain Layout
}
\end_layout
\end_inset
Better, but still a bit awkward.
Perhaps all the links can be replaced with square brackets, so an array
of arrays? Doing this will convert the JSON into funny-looking s-expression.
This will be presented shortly, below; in the meantime, it is left to the
reader's imagination.
\end_layout
\begin_layout Standard
A strange thing has happened here: the nodes
\begin_inset Formula $n_{1},n_{2}$
\end_inset
and
\begin_inset Formula $n_{3}$
\end_inset
appear in multiple places, yet they are supposed to be
\begin_inset Quotes eld
\end_inset
the same thing
\begin_inset Quotes erd
\end_inset
.
Likewise for
\begin_inset Formula $e_{2}$
\end_inset
, which appears twice, but is meant to be the same
\begin_inset Formula $e_{2}$
\end_inset
both times.
\end_layout
\begin_layout Standard
Consider representing the metatree with JSON (or something similar,
\emph on
e.g.
\emph default
YAML) The duplication presents a difficulty for JSON.
Ordinary JSON does not support object references; there is no way to say
the multiple
\begin_inset Formula $e_{2}$
\end_inset
's and the
\begin_inset Formula $n_{k}$
\end_inset
's are
\begin_inset Quotes eld
\end_inset
the same thing
\begin_inset Quotes erd
\end_inset
.
There is an IETF draft standard for references,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://datatracker.ietf.org/doc/html/draft-pbryan-zyp-json-ref-03
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://redoc.ly/docs/resources/ref-guide/
\end_layout
\end_inset
\end_layout
\end_inset
but it is not widely used.
Thus, although metatrees can be represented with JSON, some care must be
taken when parsing them: one must find all repeated objects and understand
them to be universally unique.
That is, one must replace all repeated objects by universally unique references.
\end_layout
\begin_layout Subsection
S-expressions
\end_layout
\begin_layout Standard
Let return to the string expression
\begin_inset Formula $\left(e_{4}:\left(e_{3}:\left(e_{1}:n_{1},n_{2}\right),\left(e_{2}:n_{2},n_{3}\right),n_{1},\left(e_{2}:n_{2},n_{3}\right)\right),n_{3}\right)$
\end_inset
.
What's wrong with just writing it as a basic s-expression? It appears to
be entirely unambiguous to just drop the colon and the comma.
It becomes:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(e4 (e3 (e1 n1 n2) (e2 n2 n3) n1 (e2 n2 n3)) n3)
\end_layout
\end_inset
Can't get any shorter than that.
\end_layout
\begin_layout Standard
This is not exactly an 'ordinary' s-expression, though.
Key differences:
\end_layout
\begin_layout Itemize
Every open-paren must be followed by a link '
\family sans
\size footnotesize
ek
\family default
\size default
': this is what a meta-edge must necessarily be.
\end_layout
\begin_layout Itemize
Every node is globally unique.
That is, each time the node '
\family sans
\size footnotesize
n2
\family default
\size default
' appears in this expression, it is exactly the same '
\family sans
\size footnotesize
n2
\family default
\size default
', instead of being a different instance.
Referring back to the metagraph node table (
\begin_inset CommandInset ref
LatexCommand vpageref
reference "metagraph node table"
plural "false"
caps "false"
noprefix "false"
\end_inset
), we see that there is only one true instance of '
\family sans
\size footnotesize
n2
\family default
\size default
': it just has one set of attributes on it.
When parsing the s-expression, whichever apparent copy of '
\family sans
\size footnotesize
n2
\family default
\size default
' that we grab hold of, the attributes attached to it will be the same.
\end_layout
\begin_layout Itemize
Every link is globally unique.
For example, the sub-expression '
\family sans
\size footnotesize
(e2 n2 n3)
\family default
\size default
' appears twice; in both cases, it is exactly the same subexpression.
This is clear by referring to the metagraph link table (
\begin_inset CommandInset ref
LatexCommand vpageref
reference "metagraph link table"
plural "false"
caps "false"
noprefix "false"
\end_inset
): there is really just one copy.
\end_layout
\begin_layout Standard
We conclude that s-expressions offer a marvelous compact string representation
for metagraphs.
Yet one should not be mislead; these are not ordinary s-expressions.
This will be further amplified below, when considering queries performed
over s-expressions.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The word
\begin_inset Quotes eld
\end_inset
representation
\begin_inset Quotes erd
\end_inset
is being used here in the formal sense.
For example, in group theory, one can talk about a specific group, as a
\begin_inset Quotes eld
\end_inset
thing in itself
\begin_inset Quotes erd
\end_inset
.
One can also have a
\begin_inset Quotes eld
\end_inset
matrix representation of a group
\begin_inset Quotes erd
\end_inset
, which is a collection of matrices that behave the same way as the group.
The matrix representation will also have additional properties and relationship
s that the group does not have.
These are termed
\begin_inset Quotes eld
\end_inset
accidental relationships
\begin_inset Quotes erd
\end_inset
.
Likewise here: there is the metagraph as the
\begin_inset Quotes eld
\end_inset
thing in itself
\begin_inset Quotes erd
\end_inset
, and the representation of it as an s-expression.
The s-expression has additional aspects to it that the metagraph does not
have.
Also, the s-expression can also represent other things, completely different
things, that are not metagraphs! Similar remarks apply to the graphical
drawings: they are not the
\begin_inset Quotes eld
\end_inset
metagraph in itself
\begin_inset Quotes erd
\end_inset
, they are a visual representation of it.
See Wikipedia,
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Representation_(mathematics)
\end_layout
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
UUID's
\end_layout
\begin_layout Standard
Because each node and link is globally unique, it is very tempting, at this
point, to say
\begin_inset Quotes eld
\end_inset
oh, hey, just use universally unique identifiers
\begin_inset Quotes erd
\end_inset
(UUID's).
This is good enough for local address spaces; if nothing else, then an
ordinary C/C++ pointer can be (effecitvely is) a UUID for the object.
But, when writing a text string, what UUID shall one use? How should they
be issued? Where should they be kept? These are difficult questions, with
no easy or obvious answers.
\end_layout
\begin_layout Standard
It gets worse.
What happens if there are two users, on opposite sides of the planet, and
they need to issue a UUID for an Atom? This is a famous issue in computing:
UUIDs cause major, fundamental problems when considering network-distributed
storage.
The problem is of UUID collision.
One solution to avoid UUID collision is to have a single centralized atomic
issuer of ID's that can guarantee uniqueness.
This introduces a single, centralized bottleneck.
Another solution is to use cryptographic hashes.
Each meta-tree string can be hashed down to a number.
To avoid collisions due to the birthday paradox, the hashes have to be
quite large.
For 1 million distinct atoms, a 64-bit hash and crossed fingers should
be enough; uncrossing the fingers requires at least a 96-bit hash.
For a trillion atoms, a 128-bit hash is just barely enough and a 192-bit
hash is preferred.
These eat up RAM (as compared to pointers) and the computation of cryptographic
hashes requires significant CPU overhead.
\end_layout
\begin_layout Standard
Just how big is a 64-bit hash, vs.
the expression it is standing in for? Well, 64-bits is 8 bytes.
Suppose that the data that one was storing consisted of English words (there
are about a million of them, if you include geographical place names, product
and corporate names, historical events and a smattering of Latin and foreign
loan-words.) The average length of these is about six letters, thus six
bytes; seven if including the null terminator.
How about the names of genes and proteins? These are not particularly lengthy
either.
\begin_inset Quotes eld
\end_inset
Ah, but tree structure!
\begin_inset Quotes erd
\end_inset
you might think.
All those parens, they need to be counted too! If you dump those plain-ASCII
(plain-UTF8) s-expressions to a file, and then run gzip on it, or better
yet, bzip2 or 7z, you find that those raw string s-expressions compress
very well, outperforming by a wide margin the 64-bit UUID hash.
\end_layout
\begin_layout Standard
\begin_inset Quotes eld
\end_inset
But
\begin_inset Quotes erd
\end_inset
, you say,
\begin_inset Quotes eld
\end_inset
we can't compress; the data lives in memory, not a file!
\begin_inset Quotes erd
\end_inset
Ah, yes, this is true.
The in-RAM representation is explosively larger than the string s-expression
form.
Reviewing the two tables
\begin_inset CommandInset ref
LatexCommand vpageref
reference "metagraph node table"
plural "false"
caps "false"
noprefix "false"
\end_inset
, each appearance of a node or link in those tables must be a (64-bit) pointer.
The example metagraph being worked here is two levels deep, and is quite
'small'.
Yet, counting the edges in the drawing of it, there are ten edges.
Each edge is bidirectional: there are pointers going both ways; those 20
pointers are required, or
\begin_inset Formula $160=20\times8$
\end_inset
bytes.
Plus three bytes each for the null terminated strings '
\family sans
\size footnotesize
n1
\family default
\size default
', '
\family sans
\size footnotesize
n2
\family default
\size default
' ...
'
\family sans
\size footnotesize
e1
\family default
\size default
', '
\family sans
\size footnotesize
e2
\family default
\size default
' for a total of
\begin_inset Formula $160+24=184$
\end_inset
bytes minimum.
The string-length of the string '
\family sans
\size footnotesize
(e4 (e3 (e1 n1 n2) (e2 n2 n3) n1 (e2 n2 n3)) n3)
\family default
\size default
' is 48 characters: 48 bytes.
The s-expression representation is four times more compact than the in-RAM
representation!
\end_layout
\begin_layout Standard
Finally, there is the problem of the UUID-to-meta-tree mapping.
Where is it stored? New meta-trees could be added weeks or months later.
Is there some UUID-to-meta-tree mapping service, live, available on-line
24x7? What happens if it goes down? How is it kept unique? With locks?
How many UUID's per second can be issued? What happens if it gets corrupted?
Who has spare copies? Do byzantine generals show up and ruin the day? How
much storage does this all require?
\end_layout
\begin_layout Standard
To conclude: having hashes around can be useful, as hashes are needed for
hash tables.
However, conceiving of them as if they were truly universally-unique ID's
is problematic in a dozen different ways.
By contrast, each and every s-expression really really is globally unique.
There is only one of any given kind! No centralized authority was needed
to issue this unique string! Anyone can mint it at any time, at very low
cost! If forgotten, it can be recreated! And it's ASCII representation,
compressed with bog-standard compression routines, is formidably tiny.
UUID's are horrible; s-expressions are smart.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Insertion, Deletion and Mutability
\end_layout
\begin_layout Standard
When a metatree is added to a metagraph, a scan must be made to determine
if the tree, or any subtree, already occurs in the metagraph.
How might we know this? By looking it up! But where is this stored?
\end_layout
\begin_layout Standard
One concludes that there is really only one option: there has to be a mutable,
top-level index that holds all of the meta-trees in the metagraph.
In a sense, it is the one link to rule them all.
Put differently, a metagraph store is,
\emph on
de facto
\emph default
, just a store for one single mutable meta-tree.
\end_layout
\begin_layout Standard
The word 'mutable' was used several times in the last few sentences.
This is important.
For all other meta-trees, it is not only convenient to treat them as if
they were immutable, it becomes a necessity.
Returning to the example meta-tree:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(e4 (e3 (e1 n1 n2) (e2 n2 n3) n1 (e2 n2 n3)) n3)
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Suppose one wishes to change
\begin_inset Quotes eld
\end_inset
just one
\begin_inset Quotes erd
\end_inset
of the '
\family sans
\size footnotesize
n3
\family default
\size default
's into an '
\family sans
\size footnotesize
n5
\family default
\size default
'.
But which one? They are, after all, all the same '
\family sans
\size footnotesize
n3
\family default
\size default
', so if edited, they all change together, atomically.
Suppose now that this meta-tree is a subtree of something larger and more
complex.
Performing an edit, changing the '
\family sans
\size footnotesize
n3
\family default
\size default
' into an '
\family sans
\size footnotesize
n5
\family default
\size default
' in this meta-tree requires examining the incoming set of this tree, and
determining what to do in each case.
This might be a non-trivial decision procedure.
Should each of these larger trees get the new, modified version, or should
they keep the original unmodified version? If the latter, then the unmodified
version becomes
\emph on
de facto
\emph default
immutable, and the new, modified version just becomes a completely new
meta-tree (
\begin_inset Quotes eld
\end_inset
copy on write.
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Standard
So, immutable meta-trees are quite all right.
Besides avoiding the decision problem of what to do with the incoming set,
there are some much more mundane advantages.
Immutable meta-trees can be traversed lock-free; there is no concern that
one thread is traversing it, even as another thread is altering it.
The importance of having small structures being lock-free cannot be overstated.
\end_layout
\begin_layout Standard
This all changes when one considers the top-most, master index.
It
\emph on
must
\emph default
be mutable.
It
\emph on
must
\emph default
be possible to add new trees, and remove stale ones from this master index.
Otherwise, it cannot be called a database!
\end_layout
\begin_layout Standard
Yet, oddly, this top-level index/table looks exactly like any other metatree.
Yes, it's large: it may have many millions of (immutable) subtrees in it.
But it itself is just another tree, and there is no particular reason why
it cannot be the subtree of yet other trees.
The only difference is that it is mutable.
\end_layout
\begin_layout Standard
Thus, we've identified two fundamentally different utilities, serving different
purposes, yet both having the same structural form.
The mutable form is a 'database'.
The immutable form is the 'data'.
In all other respects, they are the same.
\end_layout
\begin_layout Standard
Within the OpenCog system, the mutable form has been historically called
the 'AtomSpace'.
It can be stacked and nested and used to form linear or Y-shaped or diamond-sha
ped inheritance diagrams, however one wishes.
The immutable Nodes and Links have been called 'Atoms', as a stand-in term
for something that can be either a Node or a Link.
\end_layout
\begin_layout Subsection
Metagraph mutability vs.
SQL table mutability
\end_layout
\begin_layout Standard
There are two ways to delete a row from an SQL table.
Either one already knows the
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
PRIMARY KEY
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
of that row, and one asks for that key to be deleted, or one does not.
If one does not know, then one has to
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
SELECT key FROM employees WHERE name='Agent Smith';
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
and present the resulting key to be deleted.
Yes, of course, this can be done with a single statement:
\size small
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
DELETE FROM employees WHERE name='Agent Smith';
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
but this only hides the fact that, without the key, nothing can be done.
\end_layout
\begin_layout Standard
In SQL, effectively all tables have a primary key: it is the master key
for each row.
For the discussion above, it is effectively the UUID of the row.
As the
\emph on
de facto
\emph default
UUID of SQL systems, it suffers from all the UUID drawbacks previously
reviewed.
SQL databases are notoriously hard to shard across multiple network nodes.
Consistency and atomic updates are hard: this is because there is effectively
one centralized bottleneck for issuing and locking UUIDs.
Such locks are needed during updates, even if only for the
\begin_inset Quotes eld
\end_inset
short
\begin_inset Quotes erd
\end_inset
duration of the '
\family sans
\size footnotesize
COMMIT
\family default
\size default
'.
This bottleneck, and the difficulty of resolving it, is the foundation
stone on which the ACID vs.
BASE debates are built.
\end_layout
\begin_layout Standard
How does this compare to the one mutable index of all immutable meta-trees?
Well, there are at least three 'obvious' ways in which the deletion of
a meta-tree could be implemented.
\end_layout
\begin_layout Itemize
If the master index is a hash table or a tree of raw memory pointers, and
one has the raw pointer to the memory to be deleted, the deletion can be
immediately and directly performed.
This is analogous to already knowing the primary key of an SQL table row.
\end_layout
\begin_layout Itemize
If the master index is a hash table or a tree of abstract indicators, and
one has the abstract indicator of the meta-tree to be deleted, the deletion
can be immediately and directly performed.
Unlike the case of UUID's, there are abstract indicators that can be computed
uniquely and in a relatively rapid fashion.
An example of this is the Merkle tree.
It is 'decentralized', in the sense that, no matter who has a copy of a
given meta-tree, or where it might be located, everyone will agree as to
what it's Merkle tree hash will be.
It is not 'unique', in the sense that there might be hash collisions.
However, for practical use in the database, being collision-free is not
so important;
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
It's not so important, because one does not blindly delete everything with
the same hash.
One first checks to verify that the right thing is being deleted.
The hash only served to quickly find a small list of candidates.
This is as always.
\end_layout
\end_inset
being computable in a decentralized fashion is.
It avoids the UUID/primary-key pitfall.
This certainly turns the ACID vs.
BASE debate a bit on it's side.
The current actual OpenCog AtomSpace in-RAM implementation uses Merkle
trees.
\end_layout
\begin_layout Itemize
If the master index is an ordered key-value-store (OKVS)
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Ordered_Key-Value_Store
\end_layout
\end_inset
\end_layout
\end_inset
of s-expressions, and one has the s-expression corresponding to the meta-tree
to be deleted, the deletion can be immediately and directly performed.
But it is already apparent that it is easy and cheap to compute (in a decentral
ized fashion) the s-expression corresponding to a meta-tree.
This is effectively a variant of the above, where the
\begin_inset Quotes eld
\end_inset
abstract indicator
\begin_inset Quotes erd
\end_inset
is the s-exp, instead of the Merkle tree.
Given the earlier discussion concerning the size of s-expressions vs.
the size of pointers, this is certainly a viable storage format for the
in-RAM metagraph database.
That it is not used by the current in-RAM AtomSpace is largely a historical
accident.
However, one of several of the current file-storage backends to the AtomSpace
is RocksDB.
That backend
\emph on
does
\emph default
use s-expressions as the
\begin_inset Quotes eld
\end_inset
primary key
\begin_inset Quotes erd
\end_inset
, and RocksDB itself is a kind of OKVS.
\end_layout
\begin_layout Standard
Metagraph insertion can be compared to SQL table insertion along the same
lines.
\end_layout
\begin_layout Standard
As should be clear, there is not really all that much difference here, at
least conceptually.
The biggest and by far the most apparent difference is that SQL explicitly
and overtly exposes UUIDs in the form of primary keys, thus dragging all
that baggage along with it.
By contrast, a metagraph store can keep all of this hidden, and has multiple
implementation options for the analogous concept of a primary key: either
Merkle trees, or s-expressions, or possibly something else.
From the implementers point of view, this is nice: there are various possible
implementations (and they are all hidden from the user! No backwards-compat
concerns!)
\end_layout
\begin_layout Standard
This is also nice from the user's point of view: why mess with primary keys,
if one doesn't have to? One less thing to think about, and not unrelated
to the
\begin_inset Quotes eld
\end_inset
automatic
\begin_inset Quotes erd
\end_inset
nature of table normalization with metagraphs.
Metagraphs provide automatic key maintenance.
Nice!
\end_layout
\begin_layout Subsubsection
Metagraph mutability vs.
Graph databases
\end_layout
\begin_layout Standard
Lets compare the metagraph store to a graph database.
In a graph store, how, exactly is one supposed to say that
\begin_inset Quotes eld
\end_inset
this vertex is the same as that vertex
\begin_inset Quotes erd
\end_inset
? Finding a suitable solution is non-trivial; it requires either references
or some other technique to indicate sameness.
How is this to be managed in a graph store? If one is not careful, one
finds oneself performing queries at the same time that one is inserting
data.
\end_layout
\begin_layout Standard
There is a large variety of graph stores that are generally available.
Each has unique API's and differing implementations.
It is beyond the scope of this text to review them all.
Thus, the answer to be supplied here is utterly opaque.
How can one retro-fit this primary property of metagraphs, of global metatree
uniqueness, onto a graph store? What's the answer? This section is short
because the problem is a bit mind-boggling.
\end_layout
\begin_layout Standard
To conclude: we seem to have discovered, quite accidentally, with no explicit
intent, that hypergraphs offer an elegant property that graph databases
lack.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Query Languages and Graph Traversal
\end_layout
\begin_layout Standard
The majority of popular query languages (QL) are modeled on SQL, taking
SQL as not just an inspiration, but rather directly borrowing (stealing)
most of its keywords and syntax.
This is good, in that it makes it easy for users who are already familiar
with SQL to learn the new system.
This is good, in that it acts as a guidepost to the architect of the NewQL:
if things get confusing, just take a look at how SQL did it, and make NewQL
do it more-or-less the same way.
\end_layout
\begin_layout Standard
This is bad, in that, when the QL is to be applied to a new domain (such
as graphs, hypergraphs or metagraphs), the mind-set that was suitable for
table queries might not be appropriate for graphs.
But this is not obvious: just half an hour with GraphQL documentation and
examples will easily leave you with the impression that you can do anything
you want with GraphQL.
Got a graph? GraphQL can traverse it! That there might be some other way,
maybe even a better way, never really enters your mind.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is a reply to the Sapir–Whorf Hypothesis in the strong affirmative.
The Sapir–Whorf hypothesis is briefly worded as
\begin_inset Quotes eld
\end_inset
language limits thought.
\begin_inset Quotes erd
\end_inset
Originally, the language was natural language, say English or Chinese.
The hypothesis seems a bit absurd: if I speak English or Chinese, why
\emph on
wouldn't
\emph default
I be able to think of anything (if I'm smart enough)? What's limiting about
language? It's hard to imagine what one wouldn't be able think of.
In the present case, the language is SQL, and if you are a programmer/DBA
who thinks in terms of SQL, it is very hard to imagine what kind of queries
one could perform that
\emph on
don't
\emph default
look like SQL.
This is the topic of this section: exposing the limitations of SQL-thinking.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
There is no doubt that the mathematical theory of relational algebras is
the
\begin_inset Quotes eld
\end_inset
correct
\begin_inset Quotes erd
\end_inset
, or at least the
\begin_inset Quotes eld
\end_inset
best
\begin_inset Quotes erd
\end_inset
theory for tables and the records stored in them.
It's overwhelmingly dominant, and there does not appear to be any reason
to question it.
Likewise, the manifestation of relational algebras as SQL has the same
effect: it works really really well for records and tables, and there is
no compelling reason to replace it with something else.
(A little voice asks:
\begin_inset Quotes eld
\end_inset
if that's the case, then why graphs?
\begin_inset Quotes erd
\end_inset
) The success of this theory has the effect of shutting down any thought
process that might lead elsewhere.
\end_layout
\begin_layout Standard
The aim of this section is to make this thought process overt, and show
how there might be QL's that are not SQL siblings.
It begins by (once again) reviewing the actual structure of metagraphs,
and then examines how they compare to conventional table queries.
\end_layout
\begin_layout Subsection
Weak Pointers
\end_layout
\begin_layout Standard
The example metatree diagram, as originally drawn (on the left) is misleading
as to how it is actually represented in memory.
If one examines the metagraph link table (
\begin_inset CommandInset ref
LatexCommand vpageref
reference "metagraph link table"
plural "false"
caps "false"
noprefix "false"
\end_inset
) and includes arrows for both the incoming set and the outgoing list, one
gets the diagram on the right:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/metagraph.eps
lyxscale 60
width 25col%
\end_inset
\begin_inset space \qquad{}
\end_inset
\begin_inset Graphics
filename graphics/metagraph-weak.eps
lyxscale 60
width 25col%
\end_inset
\end_layout
\begin_layout Standard
The dotted arrows are back-pointers from lower levels to higher levels:
they are the incoming set pointers, in contrast to the solid arrows, which
show the outgoing links.
They are almost in one-to-one correspondence, but not quite: notice there
is only one dotted arrow from
\begin_inset Formula $e_{2}$
\end_inset
to
\begin_inset Formula $e_{3}$
\end_inset
, although there are two distinct downward links.
\end_layout
\begin_layout Standard
The back-pointers are needed to make the graph fully traversable; the need
for this is the topic of this section.
The back-pointers do eat up RAM; but this RAM usage has already been counted,
in a previous section.
Here, it is only the diagram that has been corrected to more appropriately
show the actual situation.
In actual implementations, the dotted arrows are weak pointers (as opposed
to regular pointers).
Weak pointers are required for memory management, whether through garage
collection (GC), or through reference counting (RC) with smart pointers.
Both kinds of systems (GC and RC) can only work with DAG's, and do not
tolerate loops, as these cannot be freed.
Yet, programmers sometimes need to create loops of pointers; thus, programming
languages provide weak pointers for this use.
That is what is shown here.
\end_layout
\begin_layout Standard
It is natural to use weak pointers for the incoming set, and regular pointers
for the outgoing list.
This is because, as observed earlier, metatrees must be immutable after
they have been created.
They cannot be edited; they can only be deleted.
There is, however, one minor point of confusion, illustrated in the diagram
below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/metagraph-new.eps
lyxscale 60
width 38col%
\end_inset
\end_layout
\begin_layout Standard
This shows that a new link
\begin_inset Formula $e_{5}$
\end_inset
has been added to the previous diagram.
This is
\emph on
not
\emph default
an edit! The earlier tree, rooted at
\begin_inset Formula $e_{4}$
\end_inset
, is completely unchanged.
None of the regular pointers have changed.
Two of the atoms
\begin_inset Formula $e_{2}$
\end_inset
and
\begin_inset Formula $n_{3}$
\end_inset
have enlarged incoming sets: they have gained a weak pointer each.
That the original metatree has not changed can be most easily observed
by the fact that it's corresponding s-expression is the same as before:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(e4 (e3 (e1 n1 n2) (e2 n2 n3) n1 (e2 n2 n3)) n3)
\end_layout
\end_inset
The diagram above shows two metatrees.
The second one is
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(e5 (e2 n2 n3) n3)
\end_layout
\end_inset
The new root
\begin_inset Formula $e_{5}$
\end_inset
points to two existing metatrees:
\begin_inset Formula $e_{2}$
\end_inset
and
\begin_inset Formula $n_{3}$
\end_inset
; neither has been modified.
The point here is that immutability does not conflict with creation and
deletion.
Creation and deletion do alter the weak pointers/incoming sets, but not
the metagraph itself.
\end_layout
\begin_layout Subsection
Queries and Tables
\end_layout
\begin_layout Standard
What do weak incoming sets have to do with queries? That they allow complete
traversal of the metagraph is intuitively obvious: there are plenty-enough
arrows (both regular and weak pointers) to be able to take walks from any
Atom to any other.
But are these really needed? The aim here is to show that the answer is
'yes', they really are.
\end_layout
\begin_layout Standard
As an initial example, consider the metatree without the incoming-set pointers.
Consider a tree-walk starting at
\begin_inset Formula $e_{4}$
\end_inset
.
Using conventional recursion techniques, it is easy to recurse (left to
right) down to
\begin_inset Formula $e_{3}$
\end_inset
then
\begin_inset Formula $e_{2}$
\end_inset
and then
\begin_inset Formula $n_{1}$
\end_inset
.
Implemented as a stack machine, the next step is to pop, and then visit
\begin_inset Formula $n_{2}$
\end_inset
.
The next stack pop brings us back to
\begin_inset Formula $e_{3}$
\end_inset
and traversal proceeds as normal.
Nowhere in this stack machine recursion is it possible to visit
\begin_inset Formula $e_{5}$
\end_inset
.
If one has started at
\begin_inset Formula $e_{4}$
\end_inset
, one cannot get to
\begin_inset Formula $e_{5}$
\end_inset
.
Worse: perhaps one's starting point was
\begin_inset Formula $n_{1}$
\end_inset
.
From there, one cannot get to anywhere, at least, not when there aren't
any incoming-set pointers (the dotted lines).
\end_layout
\begin_layout Standard
But is this relevant in any real-world application? Consider the following
interpretation of the above diagram, where the Nodes are individuals, taking
school classes and working part-time jobs:
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="11" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Atom
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Interpretation
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $n_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Joe
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $n_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Mary
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $n_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Rachel
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Intro Computer Science
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Intro Beauty and Hair Care
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Dean of Students
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{4}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Wossamatta University
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{5}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Ayurvedic School of Cosmetology II
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{3}-n_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Joe assists in the Dean's Office
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{5}-n_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Rachel is a TA in cosmetology
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
A natural question to pose in this interpretation is
\begin_inset Quotes eld
\end_inset
what schools does Rachel attend?
\begin_inset Quotes erd
\end_inset
.
Starting at
\begin_inset Formula $n_{3}$
\end_inset
, one can trace upwards to find that Rachel attends both Wossamatta U.
and ASCII.
\end_layout
\begin_layout Standard
How might this have worked in conventional SQL? Well, for starters, we need
something like this:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
CREATE TABLE Schools (
\end_layout
\begin_layout Plain Layout
name TEXT,
\end_layout
\begin_layout Plain Layout
uuid INT PRIMARY KEY);
\end_layout
\begin_layout Plain Layout
INSERT INTO Schools ...
;
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
CREATE TABLE Courses (
\end_layout
\begin_layout Plain Layout
name TEXT,
\end_layout
\begin_layout Plain Layout
school_uuid INT FOREIGN KEY,
\end_layout
\begin_layout Plain Layout
uuid INT PRIMARY KEY);
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
CREATE TABLE Students (
\end_layout
\begin_layout Plain Layout
name TEXT,
\end_layout
\begin_layout Plain Layout
course_id INT FOREIGN KEY,
\end_layout
\begin_layout Plain Layout
student_id INT PRIMARY KEY);
\end_layout
\end_inset
One continues in this fashion, creating a few more tables.
Denoting that Joe assists in the Dean's Office and that Rachel assists
in the School of Cosmetology poses a bit of a challenge.
Perhaps this might do?
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
CREATE TABLE Employment (
\end_layout
\begin_layout Plain Layout
name TEXT,
\end_layout
\begin_layout Plain Layout
employer TEXT,
\end_layout
\begin_layout Plain Layout
taxpayer_id INT PRIMARY KEY);
\end_layout
\end_inset
The need to denote employment adds a challenge to representing everything
properly with tables, but is not relevant to the query about the schools
that Rachel attends.
Mostly, we just observe that, even for this rather simple graph, there
already is a profusion of tables with some rather complex relationships
between one-another.
Textbooks insist that normalization is the correct thing to do; students
often find that normalization is just plain hard.
\end_layout
\begin_layout Standard
How does the query work?
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
SELECT Schools.name FROM Schools WHERE
\end_layout
\begin_layout Plain Layout
Students.name = 'Rachel' AND
\end_layout
\begin_layout Plain Layout
Students.course_id = Courses.uuid AND
\end_layout
\begin_layout Plain Layout
Courses.school_uuid = Schools.uuid;
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The above has the form of an explicit path walk.
It starts at
\begin_inset Formula $n_{3}$
\end_inset
and explicitly names a path that takes it to
\begin_inset Formula $e_{2}$
\end_inset
and then ...
Well, obviously, we've left out a few details, in that
\begin_inset Formula $e_{2}$
\end_inset
is jointly managed both by ASCII and by the Dean of WU.
Representing this properly requires a few more tables, and an additional
clause in the
\family sans
\size footnotesize
SELECT
\family default
\size default
statement.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
We've left out more than a few details.
There is the concept of '
\family typewriter
JOIN
\family default
', and its variants of '
\family typewriter
INNER JOIN
\family default
', '
\family typewriter
OUTER JOIN
\family default
' and so on, all of which exist to allow the DBA to more carefully control
and craft the nature of the graph walk needed, and how the data flows through
the query, so that the query will run in an efficient, performant manner.
The DBA really needs to actually think of what the query is doing (and
to know the concepts, and to consult the documentation).
I'd like to suggest that programming in SQL is like programming in assembly
code, but for data.
Perhaps it's time for a higher-level query language that abstracts away
these details.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
This query works precisely because the DBA who is creating the query has
a very concrete grasp of all of the tables involved, and is able to thread
an explicit path between the tables.
The reason that the SQL database engine can execute the query is because
the DBA explicitly inserted
\family sans
\size footnotesize
FOREIGN KEY
\family default
\size default
constraints into appropriate locations.
These foreign keys have the side effect of defining an index that manifests
the dashed arrows in the metagraph diagram.
The foreign keys are the dashed arrows.
Not all of them; just some of them, only the ones that the DBA saw fit
to add during the table design.
Just like the dashed weak pointers allowed the metatree to be traversed
upwards, so also the foreign keys allow the tables to be traversed
\begin_inset Quotes eld
\end_inset
upwards
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is the point of the Meijer and Bierman result.
\begin_inset CommandInset citation
LatexCommand cite
key "Meijer2011"
literal "false"
\end_inset
In a noSQL database, the arrows point in the opposite direction.
In either case, useful database queries require arrow-chasing.
Turns out that both SQL and noSQL databases are, under the covers, graph
databases with awkward API's.
\end_layout
\end_inset
\end_layout
\begin_layout Subsubsection
Query planning
\end_layout
\begin_layout Standard
Query planning concerns the topic of how the database engine will actually
perform the query.
The above example was written in a fashion that highlights an obviously
efficient and easy way to run the query.
Start at the literal '
\family sans
\shape italic
\size footnotesize
Rachel
\family default
\shape default
\size default
', use the join '
\family sans
\shape italic
\size footnotesize
Students.name = 'Rachel'
\family default
\shape default
\size default
' and trace the dashed arrows upwards, to immediately arrive at the desired
answer.
\end_layout
\begin_layout Standard
Of course, there is no guarantee that the SQL engine will actually do this.
It might decide to start with '
\family sans
\shape italic
\size footnotesize
TABLE Schools
\family default
\shape default
\size default
', examine each school in turn, and then trace downwards from the top, until
it eventually reaches Rachel, and is able to satisfy this final constraint.
Table joins are a constraint satisfaction problem.
Solving constraint satisfaction problems (CSP) is non-trivial;
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
\end_layout
\end_inset
\end_layout
\end_inset
there is a vast literature devoted to this, both for the case of general
CSP, and to the specific case of query planning.
\end_layout
\begin_layout Standard
Why would an SQL engine run this query in an unexpected or inefficient way?
Well, the query planner may have decided that it is too expensive to create
the dashed-arrow indexes.
Without the dashed arrows, one obviously has to start at the top.
Why would it decide that the dashed arrows are too expensive? Well, it
might have looked at all the tables, noted that they are all very small,
and that a direct downward-recursive query could be performed rapidly.
Why splurge on indexes if the tables are small and directly searchable?
\end_layout
\begin_layout Standard
There are also more mundane reasons to run the query top-down: the particular
SQL engine may not even have much of a query planner.
It might lack the sophistication to do anything fancy.
The reality is that it is difficult to create a good SQL query planner.
Not every system will take the effort.
\end_layout
\begin_layout Subsubsection
Example: OGRE QL
\end_layout
\begin_layout Standard
A worthwhile example to contemplate is the query language for OGRE
\begin_inset CommandInset citation
LatexCommand cite
key "OGRE"
literal "false"
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Documentation for it is currently located at this URL:
\begin_inset Flex URL
status open
\begin_layout Plain Layout
http://binaryanalysisplatform.github.io/bap/api/odoc/ogre/Ogre/Query/index.html
\end_layout
\end_inset
\end_layout
\end_inset
The influence of SQL in this query language is clear.
Interestingly, OGRE was designed to be a database for s-expressions, and,
as we've noted, s-expressions seem to make for an almost ideal representation
for metatrees.
So what's the catch?
\end_layout
\begin_layout Standard
Well, the OGRE s-expressions are just that: strings.
They are not metatrees; they are not interpreted as metatrees.
They are interpreted only as ordinary, conventional abstract syntax trees.
Because of this, there is no particularly compelling reason to automatically
manage the incoming sets for these trees.
Or rather, there is no particularly compelling reason, until one considers
the implementation of the '
\family sans
\size footnotesize
JOIN
\family default
\size default
' keyword.
In OGRE, there are no overt primary keys, and no foreign keys, so these
need to be generated implicitly, as needed, to perform a query that joins
together multiple s-expressions.
\end_layout
\begin_layout Standard
Does OGRE actually auto-create these primary-key/foreign-key relations,
under the covers? Without looking at the implementation, it is hard to
guess, but there are a few hints.
OGRE works as follows.
Each s-expression has the form
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(<attribute-name> <v1> <v2> ...
<vM>)
\end_layout
\end_inset
That is, the very first word appearing after the opening parenthesis has
a special meaning.
This is entirely conventional: in LISP/Scheme, the first word appearing
after an opening parenthesis also has a very special significance.
It is an operator.
For our metatrees written as s-expressions, that first word is necessarily
a Link.
And so in OGRE, the first word is called the
\begin_inset Quotes eld
\end_inset
name of a proposition
\begin_inset Quotes erd
\end_inset
; the subsequent words are the object (or subject) of the proposition.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The word
\begin_inset Quotes eld
\end_inset
proposition
\begin_inset Quotes erd
\end_inset
is no accident.
It is meant to make you think of propositional logic.
This point will be returned to when we look at ProLog.
It is notable that there is confusion between subject and object; that
these are taken to be synonymous.
In the general sheaf theory, subjects and objects are not synonymous; they
correspond to different connector types.
But this is a topic outside of the scope of the present text.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
As noted in the introduction to this text, an s-expression such as
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(student (name Joe) (gpa 3.5))
\end_layout
\end_inset
can be shortened to
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(student Joe 3.5)
\end_layout
\end_inset
provided that one has declared a
\begin_inset Quotes eld
\end_inset
predicate
\begin_inset Quotes erd
\end_inset
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(declare student (name str) (gpa float))
\end_layout
\end_inset
This last statement resembles a conventional table-database table declaration.
The resemblance is more than superficial.
The explicit BNF syntax for the declaration is
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
declaration ::= (declare <attribute-name> <field> <field> ...)
\end_layout
\begin_layout Plain Layout
field ::= (<field-name> <field-type>)
\end_layout
\begin_layout Plain Layout
field-type ::= int | str | bool | float
\end_layout
\end_inset
The field type is explicitly a concrete type.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is a good time to start talking about type theory.
The correct handling of metatrees requires recognizing that the first word
following the open parenthesis, the so-called Link, is a
\emph on
de facto
\emph default
type-theoretical type.
Perhaps there is some way for it to not be a type, but, as Sapir–Whorf
suggests, it proves to be difficult to imagine how it could be anything
other than a type.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The need for explicit declarations, and the explicit identification of concrete
types for fields, suggests that, under the covers, OGRE is building up
all the machinery needed to perform table joins.
Presumably this means the creation of the dashed-arrow incoming sets that
are needed for upwards traversals.
Or perhaps not: maybe the OGRE query planner always initiates queries top-down,
starting at the uppermost declaration, and running a stack machine to perform
recursive joins downwards.
If one has well-defined tables, a top-down query would seem like a viable
approach.
\end_layout
\begin_layout Standard
Note, by the way, that the declaration statement is of fixed length, and
is
\emph on
NOT
\emph default
variadic! The declaration statement really is defining fixed-length records
which can be placed into a completely conventional row-table.
This is perhaps why the OGRE query language looks a lot like SQL: it has
not departed from the table paradigm.
It has merely slapped on a prettier API, prettier in the sense that the
primary key and foreign key constraints have disappeared into the woodwork.
\end_layout
\begin_layout Standard
As a meta-comment about table declarations and queries: this all works fine,
as long as one has a small number of declarations.
A dozen, a few dozen, less than a hundred.
Pondering the situation of a million different table declarations is ..
imponderable, if one comes from an SQL background.
Because: oh good lord, how could one ever write meaningful queries if there
are a million tables? Can't even imagine.
Why, one would need to write meta-queries to query tables, and perhaps
query meta-tables of tables.
If only there was a meta-query language to query meta-tables in recursively-org
anized meta-trees...
oh wait, what?
\end_layout
\begin_layout Standard
We'll get back to you on that one.
\end_layout
\begin_layout Standard
In the meanwhile, it is important to observe that OGRE was designed to be
a plugin for OCaML.
A significant part of the query apparatus is defined in terms of OCaML
and not in terms of s-expressions.
Portions of the query are explicitly typed; many of the type declarations
are functional-programming function arrows (in type theory, these go by
the name of
\begin_inset Quotes eld
\end_inset
function type
\begin_inset Quotes erd
\end_inset
,
\begin_inset Quotes eld
\end_inset
arrow type
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
exponential
\begin_inset Quotes erd
\end_inset
, the later name harking back to size of the codomain of set-theoretic functions
).
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status collapsed
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Function_type
\end_layout
\end_inset
\end_layout
\end_inset
The query language is usable only if one is writing OCaML.
\end_layout
\begin_layout Standard
Perhaps the most innovative aspect of the OGRE query language is that it
is wrapped in a Kleisi triple (a Monad).
Somewhat oddly, though, that monad seems to reinvent some subset of LISP,
or at least of the SRFI-1 list iterators.
This is perhaps not entirely unexpected: s-expressions do look like lists,
and it is natural to want to do list operations on them.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
A Meta-Query Language
\end_layout
\begin_layout Standard
How else could the query about the schools that Rachel attends could be
formulated? Returning to the example diagram
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/metagraph-new.eps
lyxscale 60
width 37col%
\end_inset
\end_layout
\begin_layout Standard
\noindent
and once again noting that the presence of the dotted arrows allows rapid
graph traversal starting from any Atom, we can offer the following as a
possibility:
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Meet (Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Present
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
) (Node
\begin_inset Quotes eld
\end_inset
Rachel
\begin_inset Quotes erd
\end_inset
))))
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The reading of this query is as follows:
\end_layout
\begin_layout Itemize
'
\family sans
\size footnotesize
Meet
\family default
\size default
' is a special keyword defining the query.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The name '
\family sans
\size footnotesize
Meet
\family default
\size default
' comes from the mathematical concept of meets and joins on a lattice.
See
\begin_inset Flex URL
status collapsed
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Join_and_meet
\end_layout
\end_inset
.
The '
\family sans
\size footnotesize
Present
\family default
\size default
' link is a listing of several points in a lattice, all of which must be
met by any solution to the query.
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
'
\family sans
\size footnotesize
Variable
\family default
\size default
' is a special keyword, that, when it follows a '
\family sans
\size footnotesize
Meet
\family default
\size default
', it indicates what the query is to return.
It has other (related) meanings in other contexts.
\end_layout
\begin_layout Itemize
'
\family sans
\size footnotesize
Present
\family default
\size default
' is a special keyword, asking that all of the clauses must explicitly appear
in the database.
They must be matched, as patterns in a pattern matcher.
It is an unordered Link; the order of the clauses in this Link carries
no significance.
\end_layout
\begin_layout Itemize
The '
\family sans
\size footnotesize
Node
\family default
\size default
' and '
\family sans
\size footnotesize
Link
\family default
\size default
' keywords are special keywords, explicitly denoting the Nodes and Links
about which we've been talking all along.
\end_layout
\begin_layout Standard
The intent is that the '
\family sans
\size footnotesize
(Variable ?course?)
\family default
\size default
' is grounded by
\begin_inset Formula $e_{2}$
\end_inset
, a course Rachel (
\begin_inset Formula $n_{3}$
\end_inset
) is attending.
The '
\family sans
\size footnotesize
(Variable ?what-school?)
\family default
\size default
' is grounded by
\begin_inset Formula $e_{5}$
\end_inset
, the School of Cosmetology.
\end_layout
\begin_layout Standard
This should be contrasted with the earlier SQL query:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
SELECT Schools.name FROM Schools WHERE
\end_layout
\begin_layout Plain Layout
Students.name = 'Rachel' AND
\end_layout
\begin_layout Plain Layout
Students.course_id = Courses.uuid AND
\end_layout
\begin_layout Plain Layout
Schools.uuid = Courses.school_uuid;
\end_layout
\end_inset
The most notable difference is that the meta-query does not need to explicitly
name the '
\family sans
\size footnotesize
Schools
\family default
\size default
' table.
Indeed, the metagraph does not have a '
\family sans
\size footnotesize
Schools
\family default
\size default
' table, and so it is not nameable (this could be
\begin_inset Quotes eld
\end_inset
fixed
\begin_inset Quotes erd
\end_inset
by adding more nodes and links to the metagraph, but that is besides the
point.)
\end_layout
\begin_layout Standard
Another fundamental difference is that SQL embodies an explicit
\begin_inset Quotes eld
\end_inset
equational theory
\begin_inset Quotes erd
\end_inset
, whereas the meta-query does not.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Theory_of_pure_equality
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Equational_logic
\end_layout
\end_inset
.
In mathematical logic and model theory, the equational theory is the first
theory that is more complicated than the
\begin_inset Quotes eld
\end_inset
free theory
\begin_inset Quotes erd
\end_inset
(see
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Free_theory
\end_layout
\end_inset
.) In brief: with the free theory, you can freely
\begin_inset Quotes eld
\end_inset
write down anything
\begin_inset Quotes erd
\end_inset
, as long as the parenthesis balance.
Both s-expressions and the Datalog subset of Prolog can be taken to be
examples of free theories.
The theory of pure equality adds the equals sign, and says
\begin_inset Quotes eld
\end_inset
you can write down anything
\begin_inset Quotes erd
\end_inset
, as long as the parenthesis balance and you also take transitive closures
of the things that are equated.
Problems of consistency first show up here, as it is possible to write
down nonsense and paradoxes using equals signs.
Relational algebra (
\emph on
e.g.
\emph default
SQL) is the theory where you can
\begin_inset Quotes eld
\end_inset
write down anything
\begin_inset Quotes erd
\end_inset
, but you can also use relations between things.
Each relation corresponds to an SQL table.
That relation is
\begin_inset Quotes eld
\end_inset
true
\begin_inset Quotes erd
\end_inset
if the corresponding row exists in the SQL table, else it is
\begin_inset Quotes eld
\end_inset
false
\begin_inset Quotes erd
\end_inset
; thus relations are sometimes called predicates.
A pure relational algebra, without equality, is not quite interesting enough
to be practical.
As all of these examples show, you need to fold in the theory of equality
in order to perform table joins.
The equals sign just says
\begin_inset Quotes eld
\end_inset
this variable appearing in this predicate is equal to this other variable
or constant appearing in some other predicate
\begin_inset Quotes erd
\end_inset
.
\end_layout
\end_inset
The SQL statement has implicit variables in it: the expression '
\family sans
\size footnotesize
Students.course_id
\family default
\size default
' is meant to be understood as a variable, ranging over all possible values
of '
\family sans
\size footnotesize
course_id
\family default
\size default
' in the '
\family sans
\size footnotesize
Students
\family default
\size default
' table.
The '
\family sans
\size footnotesize
Courses.uuid
\family default
\size default
' is another implicit variable.
The equals sign is needed, because of the way that the variables appeared
implicitly.
There is no other way of saying
\begin_inset Quotes eld
\end_inset
hey, these two variables are really the same thing
\begin_inset Quotes erd
\end_inset
, and thus the concept of table joins is born.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The complexity of table joins is in part a side-effect of the complexity
of the theory of equality.
You might think that equality seems pretty darned easy; it's just equals
signs, right? Contemplating the complexity of SQL table joins, and the
complexity of SQL query planners in planning table joins should quickly
disabuse you of the idea that
\begin_inset Quotes eld
\end_inset
equality is simple
\begin_inset Quotes erd
\end_inset
.
It's hard.
If you are still not convinced, review the Wikipedia article on equational
logic again:
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Equational_logic
\end_layout
\end_inset
.
It has a number of axioms to make it work, and it is no accident that it
was developed by computer scientists who were also known for their contribution
s to relational algebras and query languages.
\end_layout
\end_inset
The meta-query made use of the property of meta-graphs that any given Atom
is always the same Atom.
That is, the '
\family sans
\size footnotesize
(Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
)
\family default
\size default
' is the same Atom in both subtrees.
There is no need to use an equals sign to equate these two positions; they
are already
\begin_inset Quotes eld
\end_inset
the same thing
\begin_inset Quotes erd
\end_inset
as metagraphs; they can't not be
\begin_inset Quotes eld
\end_inset
the same thing
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Variables, are, however, always named, given a name.
It is an open question as to how anonymous (unnamed) variables might be
written and used.
\end_layout
\end_inset
There is no explicit need for equality.
\end_layout
\begin_layout Standard
A third fundamental difference is that the metaquery did not require any
prior table definition.
The situation is thus quite different than the aforementioned OGRE QL.
Thanks to the implicit presence of the dashed arrows, there is no need
to explicitly define indexes (i.e.
there is no '
\family sans
\size footnotesize
CREATE INDEX ON Students(name);
\family default
\size default
' which would be needed if we wanted to have fast-running SQL queries on
student names.
The primary keys, of course, did not need explicit index declarations.)
\end_layout
\begin_layout Standard
A fourth fundamental difference is that the metaquery is itself a metatree.
It does not live outside of the system of metagraphs.
It does have a peculiar syntax and a collection of syntax rules (
\emph on
i.e.
\emph default
it must begin with '
\family sans
\size footnotesize
Meet
\family default
\size default
', it must have some variable declarations and use the '
\family sans
\size footnotesize
Present
\family default
\size default
' link, and so on) but that syntax is a sub-language within the language
of free s-expressions.
The fact that the metaquery is itself a metatree opens the possibility
of querying for queries.
This may sound utterly absurd, but is in fact very commonplace in chat-bots
and rule engines! This is expanded on, in the next section.
\end_layout
\begin_layout Standard
It is perhaps instructive to draw the metatree diagram for this query:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/metaquery.eps
lyxscale 60
width 22col%
\end_inset
\end_layout
\begin_layout Standard
The reading for this metatree, in terms of its Atoms, is as follows:
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="8" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="left" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Atom
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
S-expression
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $v_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $n_{3}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Node
\begin_inset Quotes eld
\end_inset
Rachel
\begin_inset Quotes erd
\end_inset
)
\end_layout
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Link
\end_layout
\begin_layout Plain Layout
(Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $e_{2}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Link
\end_layout
\begin_layout Plain Layout
(Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Node
\begin_inset Quotes eld
\end_inset
Rachel
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $p_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3,linewidth=40pt"
inline false
status open
\begin_layout Plain Layout
(Present
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
) (Node
\begin_inset Quotes eld
\end_inset
Rachel
\begin_inset Quotes erd
\end_inset
))))
\end_layout
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $g_{1}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Meet
\end_layout
\begin_layout Plain Layout
(Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Present
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
) (Node
\begin_inset Quotes eld
\end_inset
Rachel
\begin_inset Quotes erd
\end_inset
))))
\end_layout
\end_inset
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
Drawing the query as a graph should make it clear that performing this query
requires solving a subgraph isomorphism problem.
That is, satisfying this query requires searching for a subgraph of the
input-data graph that has exactly the same shape as the query.
After matching up the shapes, one performs a
\begin_inset Quotes eld
\end_inset
fill in the blanks
\begin_inset Quotes erd
\end_inset
to find the variable groundings.
\end_layout
\begin_layout Standard
More formally: The query implicitly demands that the variables should be
grounded.
The variables are to be grounded by Atoms, which may be either Nodes or
Links.
In the case of Links, these are (by definition) metatrees themselves, and
so the grounding matches a variable to a subgraph.
The collection of subgraphs must be those specified in the '
\family sans
\size footnotesize
Present
\family default
\size default
' link:
\emph on
i.e.
\emph default
they must be isomorphic to it.
Thus, the subgraph isomorphism problem.
\end_layout
\begin_layout Standard
The careful reader may have noticed that the above query only returns that
Rachel is a student of ASCII.
The full query, which would also reveal her to be a student of WU, is given
below.
The comparable SQL statement is considerably more complex and not given.
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Meet (Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Present
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
) (Node
\begin_inset Quotes eld
\end_inset
Rachel
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\begin_layout Plain Layout
(Choice
\end_layout
\begin_layout Plain Layout
(Present
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\begin_layout Plain Layout
(Present
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?what-school?
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?deprtment?
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(Link (Variable
\begin_inset Quotes eld
\end_inset
?department?
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?course?
\begin_inset Quotes erd
\end_inset
)))))
\end_layout
\end_inset
The above introduces the '
\family sans
\size footnotesize
Choice
\family default
\size default
' Link.
For the most part, it can be read as a logical-OR of the two predicates
that it wraps.
More precisely, it denotes a menu-choice: pick one or pick the other (but
not both).
It resembles an exclusive-OR, but is not the same: exclusive-OR returns
a truth value, whereas a menu-choice returns the chosen item.
Choice commonly appears as a fragment of intuitionist logic and of linear
logic.
\end_layout
\begin_layout Subsection
Metatree Query vs.
String Pattern Matching
\end_layout
\begin_layout Standard
Since metatrees can be written as s-expression strings, and since metaqueries
can be likewise, the question arises: can metaquery evaluation be reduced
to (regex) string matching? The initial example certainly feels like this
might be possible: the variables are just wild-cards, and everything else
is just constant strings that can be matched verbatim.
Unfortunately, this is not the case.
\end_layout
\begin_layout Standard
This is doubly unfortunate, since pattern matching is well-understood and
widely developed.
Besides regex and pcre,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Perl-compatible regular expressions.
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
http://www.pcre.org/
\end_layout
\end_inset
\end_layout
\end_inset
one has the `syntax-case` subset
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://www.gnu.org/software/guile/manual/html_node/Syntax-Case.html
\end_layout
\end_inset
\end_layout
\end_inset
of
\begin_inset Quotes eld
\end_inset
hygienic macros
\begin_inset Quotes erd
\end_inset
in the scheme programming language.
Syntax case provides rudimentary pattern matching and term rewriting.
In that direction, most (all?) functional programming languages include
pattern matchers as a basic utility.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Examples include Racket:
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://docs.racket-lang.org/reference/match.html
\end_layout
\end_inset
OCaml:
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://ocaml.org/manual/patterns.html
\end_layout
\end_inset
and Scala:
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://docs.scala-lang.org/tour/pattern-matching.html
\end_layout
\end_inset
\end_layout
\end_inset
The well-developed ones provide pattern languages that are quite expressive,
and the implementations tend to be compact and direct.
\end_layout
\begin_layout Standard
Metatree querying is not just (string) pattern matching.
Key differences are:
\end_layout
\begin_layout Itemize
In the s-expression for a metatree, when a sub-expression is repeated, it
is understood to be the
\begin_inset Quotes eld
\end_inset
same subexpression
\begin_inset Quotes erd
\end_inset
,
\emph on
i.e.
\emph default
the same Atom.
There is no such guarantee in a string match: the first occurrence of a
subexpression could be matched one way, and a second occurrence a different
way, possibly with a conflicting match.
Thus, if string pattern matching were to be used, it would need to be enhanced
with some sort of conflict-free subterm matching.
But how to implement this? That line of thinking seems to lead down the
path of reinventing metatrees, but in an application-specific setting.
\end_layout
\begin_layout Itemize
Practical metatree matching requires the ability to match into unordered
collections (sets).
This means that each and every permutation of an unordered set must be
attempted during the match.
String pattern matchers conventionally cannot do this.
When they can, there is often no ability to handle nested unordered sets,
subterms of which might need to be identical in the aforementioned conflict-fre
e fashion.
That is, if a variable occurs in multiple places in multiply-nested unordered
sets, and it is grounded one way in a specific permutation of one set,
it must be grounded exactly the same way in all permutations of all other
sets in which it occurs.
This is the 'conflict resolution' aspect.
How can this be accomplished? Well, one can use either metatrees, or one
can use a 'theory of equality'.
But, as noted above, the theory of equality provides it's own challenges
to implementation: it introduces brand new conflict resolution issues that
are difficult to resolve.
\end_layout
\begin_layout Itemize
Practical metatree matching needs to provide menu-choice alternatives for
subterms: one could match this or this or this.
The choice can be buried arbitrarily deep in the pattern.
As a string pattern matcher proceeds left-to-right through the string,
and encounters a choice, it must explore each and every choice, individually.
That means that it must backtrack if some given choice fails to match.
Backtracking means that the pattern matcher must be implemented as a stack
machine (because partial matches are held in a score-board, and that score-boar
d must now be placed on a stack).
So, two issues here.
First: regexes correspond to finite state machines, whereas stack machines
correspond to context-free languages.
So already, with choice, we've left the (simple, fast, direct) domain of
regexes and finite state machines.
Second: if the implementation of the pattern matcher is forcing you to
think recursively, then why are you still thinking
\begin_inset Quotes eld
\end_inset
strings
\begin_inset Quotes erd
\end_inset
? Why not think in terms of trees, which is what recursion (and context
free languages) really are? Once one has entered that domain, it is easier
to conceptualize in terms of graphs, than strings.
\end_layout
\begin_layout Itemize
Practical metatree matching requires the ability to quote and unquote significan
t keywords in the pattern.
For example, one might want to search for all expressions that contain
the term '
\family sans
\size footnotesize
Variable
\family default
\size default
' in it.
Obviously, this would have to be quoted (say, as '
\family sans
\size footnotesize
(Quote (Variable ?x?))
\family default
\size default
') as otherwise, the variable would be interpreted as a variable in the
pattern, instead of a constant term to be matched.
\end_layout
\begin_layout Itemize
Practical metatree matching requires the ability to match lambda expressions.
This requires the ability to find bound variables, and not only treat them
as constants, but also to alpha-rewrite them.
Consider, for example, the lambda expression
\begin_inset Formula $\lambda x.\left(x+2\right)$
\end_inset
written as a metatree: '
\family sans
\size footnotesize
(Lambda (Variable $x) (Plus (Variable $x) (Number 2)))
\family default
\size default
'.
This expression is obviously equivalent to
\begin_inset Formula $\lambda y.\left(y+2\right)$
\end_inset
or '
\family sans
\size footnotesize
(Lambda (Variable $y) (Plus (Variable $y) (Number 2)))
\family default
\size default
'.
The formal name for this kind of equivalence is
\begin_inset Quotes eld
\end_inset
alpha equivalence
\begin_inset Quotes erd
\end_inset
.
Any pattern that is searching for lambdas that involve '
\family sans
\size footnotesize
Plus
\family default
\size default
' and the number 2 must be able to determine the alpha-equivalence of the
match to the pattern.
This is no longer a simple string match: the pattern matcher needs to be
aware that '
\family sans
\size footnotesize
Lambda
\family default
\size default
' is a special keyword that binds its variable declarations.
It needs to know that bound variables can be alpha-rewritten.
\end_layout
\begin_layout Standard
After reading the above, the reader might feel as if there was a bit of
a bait-n-switch performed with the pattern matching requirements.
Some deeper thinking would have avoided this impression.
The overall topic of this text is that metagraphs are suitable for generic
knowledge representation.
This means representing not only 'simple' graphs and metagraphs, but also
quotidian systems like ontologies, phylogenies, first-order logic, Bayesian
networks, lambda calculus, probabilistic programs, functional programs,
declarative programs, genes, proteins, chemistry, natural language, visual
objects, sounds, 3D spaces, ...
As such, a knowledge representation system has to be practical and utilitarian,
useful as a tool for the day-to-day knowledge worker.
Thus, funny business like quotes and lambdas and alpha-rewrites and unordered
sets must necessarily enter into the picture, and be supportable in the
query system.
Users ask for these things, users want them.
You can't say no to users and expect them to come back.
\end_layout
\begin_layout Standard
Note, by the way, that the goals of a knowledge representation system resemble
the goals of set theory or topos theory for mathematics: generic frameworks
on which it is hoped that all of mathematics can be founded.
Knowledge representation is likewise foundational.
It is no accident that knowledge representation must borrow or steal ideas
from topos theory, ideas such as sheaf theory.
Sheaves are actually useful in mathematics.
At this time, it is not yet widely understood that sheaves are also useful
in knowledge representation.
But we wander off-track, here; this is a different topic, covered in other
texts in this series.
\end_layout
\begin_layout Standard
Assorted OpenCog documentation and web pages refer to the query engine as
\begin_inset Quotes eld
\end_inset
the pattern matcher
\begin_inset Quotes erd
\end_inset
.
This is misleading, as much of the tech industry understands
\begin_inset Quotes eld
\end_inset
pattern matchers
\begin_inset Quotes erd
\end_inset
to be simple finite state machines with pattern languages.
The actual OpenCog system is as described above, a stack machine capable
of recursive multi-component graph walks.
\end_layout
\begin_layout Subsection
Query Analysis
\end_layout
\begin_layout Standard
Graphs may include equality predicates.
In rare cases, these can be statically analyzed, without performing a query.
\end_layout
\begin_layout Standard
A full-fledged query language can include evaluatable predicates to accept
or reject a particular grounding.
During the analysis phase, these are set aside into a distinct bucket.
They cannot be grounded (by definition), they can only be evaluated after
a grounding is found.
\end_layout
\begin_layout Standard
Some evaluatable predicates, such as
\begin_inset Quotes eld
\end_inset
less than
\begin_inset Quotes erd
\end_inset
, may cause a graph to fall apart into disjoint, disconnected components
that are bridged only by evaluatable terms.
During the analysis phase, the connected components must be identified
and set aside.
During evaluation of the query, each connected component is grounded separately
, and then brought together, to evaluate
\begin_inset Quotes eld
\end_inset
less than
\begin_inset Quotes erd
\end_inset
on the resulting groundings.
Evaluatable terms, such as
\begin_inset Quotes eld
\end_inset
less than
\begin_inset Quotes erd
\end_inset
, act as a filter on the Cartesian product of the components.
Terms such as logical-or act on the disjoint union of the components.
That is, both pi-type and sigma-type arrangements of disjoint components
are possible.
\end_layout
\begin_layout Standard
A full-fledged query language can include an '
\family sans
\size footnotesize
Absent
\family default
\size default
' predicate, indicating one or more clauses that must be absent in the dataset,
in order for the query to be satisfied.
Such clauses are extracted and set aside during the analysis phase.
They resemble evaluatable clauses, but have their own distinct peculiarities.
\end_layout
\begin_layout Standard
A full-fledged query language can include an '
\family sans
\size footnotesize
Always
\family default
\size default
' predicate, required to be present in not just one grounding, but in every
grounding.
They resemble evaluatable clauses, but they cannot be evaluated until after
all possible groundings have been obtained (They can fail early, though.)
\end_layout
\begin_layout Subsection
Query Planning
\end_layout
\begin_layout Standard
The most basic query planning involves choosing a starting point for a graph
walk.
Thanks to the incoming set, the query can be started anywhere.
However, it is advantageous to start the graph walk at the thinnest, most
distant part of the graph, so that it does not need to be regularly revisited.
\end_layout
\begin_layout Standard
Sometimes, finding a starting point this way is impossible, because the
query consists entirely of variables.
In other cases, a query may consist entirely of evaluatable terms, which,
by definition, are not groundable, but only evaluatable.
These cases must be dealt with.
\end_layout
\begin_layout Standard
Queries may consist of multiple disconnected components; these must be individua
lly grounded, and then reassembled with pi-type or sigma-type bridges between
them.
\end_layout
\begin_layout Standard
It is advantageous to borrow some ideas from SAT solving, and prune simple
trees from the query, before performing an exhaustive search of a multiply-conn
ected tight nucleus.
The pruned trees can be re-attached later.
Equivalently, they might only need to be pattern-matched once.
In this case, pruning is equivalent to maintaining a cache of pattern matches
achieved earlier during traversal.
(That is, a recursive graph walk will typically revisit certain parts of
the graph.
But if those parts have already been grounded, they do not need to be revisited
again; it is sufficient to have a cache of the groundings.)
\end_layout
\begin_layout Standard
The OpenCog query engine makes use of these query optimizations.
\end_layout
\begin_layout Subsection
Attributes (Tags)
\end_layout
\begin_layout Standard
This text opened with an extended discussion of attributes, and about how
attributes are attached to the nodes and vertexes of a graph.
This is still the case, still a desirable thing to do, when working with
metagraphs.
\begin_inset Quotes eld
\end_inset
But why?
\begin_inset Quotes erd
\end_inset
you may wonder,
\begin_inset Quotes eld
\end_inset
why can't everything be encoded as as metagraph? Why are attributes needed?
\begin_inset Quotes erd
\end_inset
\end_layout
\begin_layout Standard
Well, of course, everything can be encoded as a metagraph.
However, there's a cost; several costs, actually.
One cost is that metatrees are immutable.
If one has a list of 100 floating point numbers, and wishes to change the
42nd one, it seems like overkill to be blocked from doing so by immutability.
One might like to have something mutable, for this kind of a low-level
vector.
Another cost is the weak pointer (the dashed arrow).
There is no particular need to maintain an incoming set for each floating
point in a list.
It is unlikely that two different Links will share the same floating point
number (to all of it's glorious 18 decimal places!? Really?) It is unlikely
that there will ever be any need for a query to traverse backwards (through
the incoming set) of that float.
Traversing forward into the vector of floats is plenty enough, if the only
query decision to be performed is greater-then, less-than on some arithmetic
ops on those numbers.
Saving some RAM by not storing the weak pointers is a laudable thing do
to.
\end_layout
\begin_layout Standard
If the attributes are stored as key-value pairs (KVP), then the attributes
on any given Atom can be understood conceptually as a key-value database
per Atom.
This might feel like overkill, but it isn't really any different from graph
databases in general.
If a vertex or an edge of a graph has some attributes attached to it, then
those attributes can be thought of as residing in a database specific to
that edge or vertex.
\end_layout
\begin_layout Standard
In the present case, there is one fun little twist: if the KVP's are hierarchica
l,
\emph on
i.e.
\emph default
a tree, then they can be thought of as a special case of a metatree (as,
indeed, trees are special cases of metatrees), but it is a metatree that
is shorn of it's weak back-pointers, and thus can be mutable.
One saves RAM and regains the mutability that was lost.
The price to be paid is that such attributes are no longer searchable.
(More precisely, they are no longer searchable except by brute force exhaustive
search.
The weak pointers acted as local indexes; without the ability to do an
index lookup, brute force exhaustive search is all that one has left.)
\end_layout
\begin_layout Standard
The OpenCog AtomSpace supports attributes in the form of KVP trees.
It has made one unfortunate naming choice for these attribute trees: they
got called
\begin_inset Quotes eld
\end_inset
Values
\begin_inset Quotes erd
\end_inset
with a capital V.
This naming choice forces all sorts of contortions when one wants to talk
about ordinary values with a lower-case v.
The naming choice was arrived at under the influence of model theory, where
a clear distinction is made between sentences of a language and their valuation.
In model theory, and in logic, sentences are assigned
\begin_inset Quotes eld
\end_inset
truth values
\begin_inset Quotes erd
\end_inset
.
Historically, these are crisp true/false values.
But in Bayesian belief networks and in Markov logic networks, these valuations
are given floating-point probabilities as their truth values.
On OpenCog, these were historically called TruthValues, written in CamelCase.
When generalized to arbitrary KVP valuations, they become Values.
A better name might have been Attributes or Tags, as they are treated as
...
attributes, or tags.
\end_layout
\begin_layout Subsection
Chatbots, Rule Engines and Inverted Queries
\end_layout
\begin_layout Standard
Here's something SQL cannot do: it cannot search for SQL.
Absurd, right? One of the early chatbot technologies is called SRAI (Stimulus-R
esponse AI), and the scripting language for SRAI is known as AIML (AI Markup
Language).
An example snippet of AIML is given below.
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
<aiml>
\end_layout
\begin_layout Plain Layout
<category>
\end_layout
\begin_layout Plain Layout
<pattern>I love *</pattern>
\end_layout
\begin_layout Plain Layout
<template>I like <star/> a lot.</template>
\end_layout
\begin_layout Plain Layout
</category>
\end_layout
\begin_layout Plain Layout
<category>
\end_layout
\begin_layout Plain Layout
<pattern>I * you</pattern>
\end_layout
\begin_layout Plain Layout
<template>Well, I <star/> you, too!</template>
\end_layout
\begin_layout Plain Layout
</category>
\end_layout
\begin_layout Plain Layout
</aiml>
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The goal of this is to specify some conversational patterns to be matched,
and, if matched, to produce the indicated output.
Thus, if a human says
\emph on
\begin_inset Quotes eld
\end_inset
I love baseball
\begin_inset Quotes erd
\end_inset
\emph default
, the chatbot responds
\emph on
\begin_inset Quotes eld
\end_inset
I like baseball a lot.
\begin_inset Quotes erd
\end_inset
\emph default
If the human says
\emph on
\begin_inset Quotes eld
\end_inset
I hate you
\begin_inset Quotes erd
\end_inset
\emph default
, the response
\emph on
\begin_inset Quotes eld
\end_inset
Well, I hate you, too!
\begin_inset Quotes erd
\end_inset
\emph default
is elicited.
In the case of
\emph on
\begin_inset Quotes eld
\end_inset
I love you
\begin_inset Quotes erd
\end_inset
\emph default
, there are two possible responses, and a coin is flipped to pick one.
\end_layout
\begin_layout Standard
What is being done here is a kind of inverted query.
One is presented with the 'answer',
\emph on
\begin_inset Quotes eld
\end_inset
I love you
\begin_inset Quotes erd
\end_inset
\emph default
, and the goal is to find all 'queries' which can be satisfied by that answer.
In this example, the two queries are '
\family sans
\size footnotesize
<pattern>I love *</pattern>
\family default
\size default
' and '
\family sans
\size footnotesize
<pattern>I * you</pattern>
\family default
\size default
'.
Abandoning the XML markup in favor of s-expressions, the two patterns are
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(I love (Variable
\begin_inset Quotes eld
\end_inset
?star?
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(I (Variable
\begin_inset Quotes eld
\end_inset
?star?
\begin_inset Quotes erd
\end_inset
) you)
\end_layout
\end_inset
An AIML chatbot consists of tens of thousands of such patterns, and the
matching responses.
In order to have rapid query responses, chatbot implementations organize
the patterns into a trie
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
A prefix tree, see
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Trie
\end_layout
\end_inset
\end_layout
\end_inset
and typically implement some variation of the Rete algorithm.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Rete_algorithm
\end_layout
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
All this can be expressed in the Atomese meta-query language.
It is necessarily a bit more verbose, but perhaps still readable without
assistance.
The AtomSpace is populated with SRAI rules, having the form
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Query
\end_layout
\begin_layout Plain Layout
(Present (Word
\begin_inset Quotes eld
\end_inset
I
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes eld
\end_inset
love
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?star?
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\begin_layout Plain Layout
((Word
\begin_inset Quotes eld
\end_inset
I
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes eld
\end_inset
like
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?star?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Word
\begin_inset Quotes eld
\end_inset
a
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes eld
\end_inset
lot
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
(Query
\end_layout
\begin_layout Plain Layout
(Present (Word
\begin_inset Quotes eld
\end_inset
I
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?star?
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes eld
\end_inset
you
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
((Word
\begin_inset Quotes eld
\end_inset
Well,
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes eld
\end_inset
I
\begin_inset Quotes erd
\end_inset
) (Variable
\begin_inset Quotes eld
\end_inset
?star?
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Word
\begin_inset Quotes eld
\end_inset
you
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes eld
\end_inset
too!
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\end_inset
The reading of this content is as follows:
\end_layout
\begin_layout Itemize
'
\family sans
\size footnotesize
Query
\family default
\size default
' is a special keyword defining the rewrite rule.
It is much like '
\family sans
\size footnotesize
Meet
\family default
\size default
', introduced previously, except that, this time, instead of delivering
a grounding, it delivers a rewrite making use of that grounding.
The first Atom following the query is the pattern to be matched.
The second Atom of the query is the rewrite to apply, after a match has
been found.
\end_layout
\begin_layout Itemize
The '
\family sans
\size footnotesize
Variable
\family default
\size default
' and '
\family sans
\size footnotesize
Present
\family default
\size default
' keywords are just as before.
\end_layout
\begin_layout Itemize
The '
\family sans
\size footnotesize
Word
\family default
\size default
' is a handy variant of a Node, reminding readers that the indicated string
is a natural language word.
One could have just as easily said '
\family sans
\size footnotesize
Node
\family default
\size default
', here; this is just some visual bling.
\end_layout
\begin_layout Standard
This is not SQL! We've said this before, but it is worth saying again: the
metagraph database is populated with tens of thousands of such statements,
\begin_inset Quotes eld
\end_inset
statements
\begin_inset Quotes erd
\end_inset
which just happen to have the form of queries.
In the database, these queries are dormant; they are not running, they
are just sitting there, waiting for their day in the sun.
The actual query to be performed looks like this:
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Dual (Word
\begin_inset Quotes eld
\end_inset
I
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes eld
\end_inset
love
\begin_inset Quotes erd
\end_inset
) (Word
\begin_inset Quotes erd
\end_inset
you
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Notice that this query has no variables in it: it consists entirely of constants
! It is an 'answer', not a question! The subgraph isomorphism engine, aka
the query engine, aka the 'pattern matcher', finds all matching patterns.
In this case, it is the two queries shown earlier.
To run the chatbot, one then flips a coin, picks one of the two queries,
runs it, and prints the response.
Running the query is computationally 'trivial', as there is only one pattern
to match:
\emph on
\begin_inset Quotes eld
\end_inset
I love you
\begin_inset Quotes erd
\end_inset
\emph default
.
\end_layout
\begin_layout Standard
Pay attention: the above is
\emph on
NOT
\emph default
saying that there are ten thousand queries that are each performed, until
a match is found!
\emph on
No!
\emph default
It is saying that only two queries are run: first, the '
\family sans
\size footnotesize
Dual
\family default
\size default
', to find some candidates, and then one of the candidates is chosen and
run on a tiny, itsy-bitsy dataset consisting of one sentence.
It's fast.
Insofar as all of this content is stored as metatrees, all of the prior
considerations about RAM usage, search performance and tree walking apply.
\end_layout
\begin_layout Standard
The above is more or less a peculiar variation of the Rete algorithm.
The Dual link is used to narrow down the selection of rules to apply, then
(users choice) either one of the rules is selected and fired, or maybe
all of the selected rules can be fired.
\end_layout
\begin_layout Standard
The take-away lessons are:
\end_layout
\begin_layout Itemize
Inverted queries are still queries.
\end_layout
\begin_layout Itemize
SQL-inspired languages cannot support inverted queries.
As a corollary, most graph databases cannot support inverted queries.
\end_layout
\begin_layout Itemize
Chatbots are highly specialized, customized database engines, highly tuned
for performing inverse queries.
\end_layout
\begin_layout Itemize
Rule engines are highly specialized, customized database engines, highly
tuned for performing inverse queries.
\end_layout
\begin_layout Itemize
A metagraph-style query language can easily support both queries and inverted
queries, because the query engine itself is a subgraph isomorphism solver,
and it does not particularly care about the types of the Nodes and Links
that it is matching, as long as it is able to match.
\end_layout
\begin_layout Itemize
Because metatrees contain both the forward pointers and the weak pointers
pointing backwards, they effectively have a trie (prefix tree) built in.
That is, the organizational advantages of using prefix trees to perform
rapid string-matching searches come
\begin_inset Quotes eld
\end_inset
for free
\begin_inset Quotes erd
\end_inset
in a metagraph, as a part of the general infrastructure.
\end_layout
\begin_layout Itemize
Because metaqueries can support both direct and inverted queries, they provide
a natural infrastructure on which to build both rule engines and forward-infere
ncing chainers.
\end_layout
\begin_layout Standard
That chatbots can be unified with conventional query is perhaps one of the
more entertaining aspects coming out of metaqueries.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Types
\end_layout
\begin_layout Standard
It was observed above that metatrees have a natural string representation
as s-expressions.
Every system that works with s-expressions gives a privileged interpretation
to the first word after an open parenthesis.
In Lisp and Scheme, that first word is an operator.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See John N.
Shutt's blog post
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://fexpr.blogspot.com/2011/04/fexpr.html
\end_layout
\end_inset
for careful terminology.
\end_layout
\end_inset
In a key-value store, the first element is the key, and the trailing elements
are the value.
\end_layout
\begin_layout Standard
What is the first element for metatrees?
\end_layout
\begin_layout Standard
The answer appears to be that it is a type, a type-theoretical type.
This is not a proclamation or a theoretical result, this is an experimental
result.
After working with meta-trees for a decade, and examining how they represent
data, it appears that there isn't any other obvious interpretation than
to say that it is a type.
\end_layout
\begin_layout Standard
The observational evidence is as follows:
\end_layout
\begin_layout Itemize
From the beginning, it is noted that there is a distinction between Nodes
and Links, roughly analogous to the vertexes and edges of graphs.
So it seems these are two different types.
\end_layout
\begin_layout Itemize
Could this could be reduced to just one type, by replacing Nodes with nullary
Links? Not easily.
Nodes need to be distinguishable, and thus are given unique string names.
There is no particular need to give a Link a string name: it's outgoing
list uniquely disambiguates that Link from any other.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is eerily similar to atomic physics.
All electrons are indistinguishable.
All protons are indistinguishable.
When combined into atoms, however, this changes.
An element of one type (say, carbon) is clearly different than another
(say, oxygen), but all carbon atoms are indistinguishable...
unless they appear in an organic molecule.
That is, it is the relationship of elementary particles to one-another
that gives structure to the universe.
It is not the particles themselves.
\end_layout
\end_inset
In order to get rid of the Node/Link distinction, Links would have to be
given names.
A compelling reason to do this would need to be found.
\end_layout
\begin_layout Itemize
The description of the meta-query language introduces a Variable, which
is obviously a kind of Node, but is distinguished from a conventional Node,
in that it has special semantics in the context of a query.
It is a different kind of Node.
\end_layout
\begin_layout Itemize
Similarly, the metaquery language introduces a Present Link, which is a
kind of a Link, but, again, has special semantics in the context of a query.
\end_layout
\begin_layout Itemize
In the current OpenCog Atomese system, there are well over a hundred distinct
Node and Link types, each introduced as a need arose.
Booleans: AndLink, OrLink, NotLink.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/AndLink
\end_layout
\end_inset
\end_layout
\end_inset
Arithmetic: PlusLink, MinusLink, GreaterThanLink.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/PlusLink
\end_layout
\end_inset
\end_layout
\end_inset
Set theory: SetLink, MemberLink.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/SetLink
\end_layout
\end_inset
\end_layout
\end_inset
Functionals: LambdaLink.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/LambdaLink_and_ScopeLink
\end_layout
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
For many (but not all) of these Nodes and Links, it became convenient to
create a corresponding C++ class that performs some function.
A silly example is the PlusLink: when this is executed, the arguments are
added together, if the arguments are numeric.
The C++ class performs this addition.
Now, it is generally regarded that C++ classes are types.
By extension, PlusLink must also be a type.
\end_layout
\begin_layout Itemize
After recognizing that Nodes and Links and their variations are all types,
it became easy to create a type system: SignatureLink, TypedVariableLink,
TypeNode, ArrowLink.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/SignatureLink
\end_layout
\end_inset
\end_layout
\end_inset
It appears to be entirely consistent and, as a type system, entirely convention
al.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The OpenCog AtomSpace includes all the easy type-theoretical stuff.
What's currently missing are type equations, type variables and dependent
types.
These are missing mostly because no one has asked for them yet.
Atomese has evolved on an as-needed basis: if something isn't urgently
needed, it does not get implemented.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Ergo, it is natural to take the concept of a metatree, which already distinguish
es between Node and Link, and recognize that this naturally blossoms into
a type system.
\end_layout
\begin_layout Standard
As a type system, it is dynamically typed, not static-typed.
New types can be introduced at any time.
It doesn't even make sense to talk of a
\begin_inset Quotes eld
\end_inset
static
\begin_inset Quotes erd
\end_inset
type system, because the metatrees are not being
\begin_inset Quotes eld
\end_inset
compiled
\begin_inset Quotes erd
\end_inset
into the database: they are merely being inserted.
There is a long-running REPL loop, and nothing is gained by preventing
users from defining new types at runtime.
Note that this does make the type system clash with that of OCaml, Haskell,
Scala, all of which deploy a static type system.
\end_layout
\begin_layout Standard
As a practical example: Nodes and Links are of type Atom.
The biology subsystem uses GeneNodes and ProteinNodes, since these are
useful for biological data representations.
These are also type Atom.
The biology subsystem is a distinct subsystem, and not part of the core:
it is dynamically loaded.
This creates issues for the OCaml binding, which might have known about
Atoms at compile time, but had no clue about GeneNodes and ProteinNodes
at compile time.
Static types and metatree types do not play well together.
\end_layout
\begin_layout Standard
The second bullet point above idly wondered about a monotyped system, where
everything is a Link, and Links have a string name.
This would bring the system closer to a Lisp/Scheme conception of the world.
Yet, this changes nothing: there is still a need to have variables, as
well as atoms for algebraic operations: and, or, not, set, member, plus,
minus,
\emph on
etc.
\emph default
If there were only Links with a string name, then these would then have
to be demarcated in the string name...
and thus have to be recognized
\emph on
de facto
\emph default
types.
\end_layout
\begin_layout Subsection
Examples of Types
\end_layout
\begin_layout Standard
By
\begin_inset Quotes eld
\end_inset
types
\begin_inset Quotes erd
\end_inset
it is meant both the types of computer science,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Type_system
\end_layout
\end_inset
\end_layout
\end_inset
and of type theory.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Type_theory
\end_layout
\end_inset
\end_layout
\end_inset
In conventional computer programming, ints, floats and strings are types
(these are the
\begin_inset Quotes eld
\end_inset
primitive types
\begin_inset Quotes erd
\end_inset
), and so are object-oriented classes (these are the
\begin_inset Quotes eld
\end_inset
compound types
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
product types
\begin_inset Quotes erd
\end_inset
).
Function calls have a type signature too, this is the arrow type, pointing
from the input arguments to the output type.
The ML, CaML, Haskell, Scala and F# programming languages provide an explicit
type system, allowing the programmer to define new types (In OO languages,
new types can only be defined by defining a new OO class).
\end_layout
\begin_layout Standard
Before proceeding further, a reference example will help clarify the idea.
Consider the English language sentence
\emph on
\begin_inset Quotes eld
\end_inset
The cat sat on the mat.
\begin_inset Quotes erd
\end_inset
\emph default
This encodes some information; how might it be encoded as a metagraph?
There are many possible choices, but one of the simplest is shown here:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(SittingLink
\end_layout
\begin_layout Plain Layout
(ObjectNode
\begin_inset Quotes eld
\end_inset
cat
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(ObjectNode
\begin_inset Quotes eld
\end_inset
mat
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
This clearly has the Link-Node structure of a metatree; but appears to be
using some derived types.
The denotational semantics is obviously that of the English language sentence;
the denotation of the remaining pieces is left to the imagination of the
reader.
This is not laziness on the part of the writer: the word
\begin_inset Quotes eld
\end_inset
denotation
\begin_inset Quotes erd
\end_inset
, when used in a computer science context, means
\begin_inset Quotes eld
\end_inset
what the computer programmer is imagining it to be
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Playing a bit fast and loose here:
\begin_inset Quotes eld
\end_inset
denotational semantics
\begin_inset Quotes erd
\end_inset
, see
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Denotational_semantics
\end_layout
\end_inset
is about converting what the programmer is thinking back into mathematical
formulas.
Computer science, just like math, loves to go meta whenever it can.
\end_layout
\end_inset
So, for example, a
\begin_inset Quotes eld
\end_inset
float
\begin_inset Quotes erd
\end_inset
is only a
\begin_inset Quotes eld
\end_inset
number
\begin_inset Quotes erd
\end_inset
in the programmer's head; what is actually in the machine code is just
some bytes, and not
\begin_inset Quotes eld
\end_inset
numbers
\begin_inset Quotes erd
\end_inset
.
Likewise here,
\family sans
\size footnotesize
\emph on
SittingLink
\family default
\size default
\emph default
is just some metatree sitting in RAM.
It has no inherent meaning by itself; its meaning emerges only in relation
to other metatrees in the system.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Philosophically, this is a pan-psychic view of the world: individual ur-items
are meaningless; all meaning comes from the relationships between objects.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The '
\family sans
\size footnotesize
(ObjectNode
\begin_inset Quotes eld
\end_inset
cat
\begin_inset Quotes erd
\end_inset
)
\family default
\size default
' could be replaced by a
\family sans
\size footnotesize
CatNode
\family default
\size default
, although the usage would appear to change: one would then write '
\family sans
\size footnotesize
(CatNode
\begin_inset Quotes eld
\end_inset
Fuzzykins
\begin_inset Quotes erd
\end_inset
)
\family default
\size default
'.
Alternately, one could choose to move in the opposite direction, and write:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(Link
\end_layout
\begin_layout Plain Layout
(PredicateNode
\begin_inset Quotes eld
\end_inset
Object
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Node
\begin_inset Quotes eld
\end_inset
cat
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
which denotes that cats are objects.
The '
\family sans
\size footnotesize
PredicateNode
\family default
\size default
' denotes something that behaves like a truth value; the assertion is that
it is true that cats are objects.
But there is also a different denotational idea lurking here: The above
is behaving as a kind of type declaration! It appears to be declaring that
things of type
\begin_inset Quotes eld
\end_inset
cat
\begin_inset Quotes erd
\end_inset
are things of type
\begin_inset Quotes eld
\end_inset
Object
\begin_inset Quotes erd
\end_inset
.
One could sharpen this, and write
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(TypeDefinitionLink
\end_layout
\begin_layout Plain Layout
(TypeNode
\begin_inset Quotes eld
\end_inset
CatNode
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(TypeNode
\begin_inset Quotes eld
\end_inset
ObjectNode
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
After this type definition is provided, it appears to be appropriate to
write things like '
\family sans
\size footnotesize
(CatNode
\begin_inset Quotes eld
\end_inset
Fuzzykins
\begin_inset Quotes erd
\end_inset
)
\family default
\size default
'.
\end_layout
\begin_layout Standard
To round out this example, it might also be useful to define a '
\family sans
\size footnotesize
CatLink
\family default
\size default
', which could then be used to link together disparate properties:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(CatLink
\end_layout
\begin_layout Plain Layout
(PredicateNode
\begin_inset Quotes eld
\end_inset
has
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Node
\begin_inset Quotes eld
\end_inset
fur
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(CatLink
\end_layout
\begin_layout Plain Layout
(PredicateNode
\begin_inset Quotes eld
\end_inset
URL
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(Node
\begin_inset Quotes eld
\end_inset
https://example.com/cutie-fuzball.gif
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
This is just generic knowledge representation.
Caution: although the metatrees (and metatypes) above are encoding information
about cats, they may not be the
\begin_inset Quotes eld
\end_inset
best
\begin_inset Quotes erd
\end_inset
way to represent knowledge.
A more conventional approach would be to define '
\family sans
\size footnotesize
IsALink
\family default
\size default
' and '
\family sans
\size footnotesize
HasALink
\family default
\size default
' and '
\family sans
\size footnotesize
PartOfLink
\family default
\size default
': holonyms and meronyms, and use those in one's lexical ontology.
There is freedom in how this can be done; there is nothing in the metatrees
that is forcing certain types upon the user, over other types.
\end_layout
\begin_layout Subsection
Dynamic Typing
\end_layout
\begin_layout Standard
In a metagraph, the concept of a primitive type appears to be fluid; new
types are naturally definable by means of type inheritance.
By
\begin_inset Quotes eld
\end_inset
primitive
\begin_inset Quotes erd
\end_inset
, it is meant a type that is not built with one of the usual type constructors:
a list constructor, a function-type constructor, a product (pair) constructor.
\end_layout
\begin_layout Standard
There does not seem to be any need to prevent the creation of new types
at runtime.
This is in contrast to statically-typed programming languages.
Languages such as OCaml demand static typing so that type inference can
be done at compile time.
After a module has been compiled, the resulting binary has an API with
fixed types in the interface.
This provides safety: the user cannot call into the binary with bogus arguments
, leading to undefined behavior or crashes.
In that sense, static types
\begin_inset Quotes eld
\end_inset
make sense
\begin_inset Quotes erd
\end_inset
for compiled programming languages.
The case is different here: with metagraphs, the primary goal is not programmin
g but data representation.
Metagraphs don't
\begin_inset Quotes eld
\end_inset
do anything
\begin_inset Quotes erd
\end_inset
, they are not an
\begin_inset Quotes eld
\end_inset
executable program
\begin_inset Quotes erd
\end_inset
, they just
\begin_inset Quotes eld
\end_inset
exist
\begin_inset Quotes erd
\end_inset
.
At least this particular reason for static type-safety seems to disappear.
\end_layout
\begin_layout Standard
Once a type has been defined, it does not seem reasonable to allow it to
be re-defined.
Re-definition of a type risks corrupting the meaning, if not the actual
structure of the data held in the metagraph.
For example, one would not want to redefine CatNode to allow the description
of fish; existing assertions about fur and tails become invalidated.
Thus, types are immutable: they can be created, they can be destroyed;
they cannot be altered.
\end_layout
\begin_layout Subsection
Signatures and Arrows
\end_layout
\begin_layout Standard
It appears that metatree types are also implicit type constructors, in that
they are trivially reified.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Reification_(computer_science)
\end_layout
\end_inset
\end_layout
\end_inset
Thus,
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(ListLink
\end_layout
\begin_layout Plain Layout
(ConceptNode
\begin_inset Quotes eld
\end_inset
some
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(ConceptNode
\begin_inset Quotes eld
\end_inset
thing
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
obviously has the type signature
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status collapsed
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Signature_(logic)
\end_layout
\end_inset
for the formal definition of a signature, and
\begin_inset Flex URL
status collapsed
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Type_signature
\end_layout
\end_inset
for a quotidian, non-abstract working-programmer definition.
\end_layout
\end_inset
of
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(SignatureLink
\end_layout
\begin_layout Plain Layout
(ListLink
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode)
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode))
\end_layout
\end_inset
It has two other signatures as well:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(SignatureLink
\end_layout
\begin_layout Plain Layout
(ListLink
\end_layout
\begin_layout Plain Layout
(ConceptNode
\begin_inset Quotes eld
\end_inset
some
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode))
\end_layout
\end_inset
and
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(SignatureLink
\end_layout
\begin_layout Plain Layout
(ListLink
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode)
\end_layout
\begin_layout Plain Layout
(ConceptNode
\begin_inset Quotes eld
\end_inset
thing
\begin_inset Quotes erd
\end_inset
))
\end_layout
\end_inset
\end_layout
\begin_layout Standard
This kind of easy reification makes it possible to easily attach complex
types to type definitions.
Returning to the previous example of a '
\family sans
\size footnotesize
CatLink
\family default
\size default
', one could write
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(TypeDefinitionLink
\end_layout
\begin_layout Plain Layout
(TypeNode
\begin_inset Quotes eld
\end_inset
CatLink
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(SignatureLink
\end_layout
\begin_layout Plain Layout
(TypeNode 'PredicateNode)
\end_layout
\begin_layout Plain Layout
(TypeNode 'Node)))
\end_layout
\end_inset
which indicates that the only valid way to use a '
\family sans
\size footnotesize
CatLink
\family default
\size default
' is as a binary Link, where the first element of the outgoing pair must
be a '
\family sans
\size footnotesize
PredicateNode
\family default
\size default
' and the second must be a '
\family sans
\size footnotesize
Node
\family default
\size default
' (and not a '
\family sans
\size footnotesize
Link
\family default
\size default
').
There does not appear to be anything challenging to introducing sigma types:
one could have written
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(TypeDefinitionLink
\end_layout
\begin_layout Plain Layout
(TypeNode
\begin_inset Quotes eld
\end_inset
CatLink
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(SignatureLink
\end_layout
\begin_layout Plain Layout
(TypeNode 'PredicateNode)
\end_layout
\begin_layout Plain Layout
(TypeChoice
\end_layout
\begin_layout Plain Layout
(TypeNode 'Node)
\end_layout
\begin_layout Plain Layout
(TypeNode 'Link))))
\end_layout
\end_inset
which states that the second element of the outgoing pair can be either
a Node or a Link.
To reiterate: type reification appears to be trivial with metatrees.
\end_layout
\begin_layout Standard
To round out the above examples, we present the very common case of the
signature of lambdas.
Here, the lambda
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(LambdaLink
\end_layout
\begin_layout Plain Layout
(VariableList
\end_layout
\begin_layout Plain Layout
(TypedVariable (Variable
\begin_inset Quotes eld
\end_inset
$x
\begin_inset Quotes erd
\end_inset
) (TypeNode 'ConceptNode))
\end_layout
\begin_layout Plain Layout
(TypedVariable (Variable
\begin_inset Quotes eld
\end_inset
$y
\begin_inset Quotes erd
\end_inset
) (TypeNode 'ConceptNode)))
\end_layout
\begin_layout Plain Layout
(FooBarBodyLink ...))
\end_layout
\end_inset
obviously must have the signature of
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(ArrowLink
\end_layout
\begin_layout Plain Layout
(VariableList
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode)
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode))
\end_layout
\begin_layout Plain Layout
(TypeNode 'FooBarBodyLink))
\end_layout
\end_inset
That is, the arrow points from a list of the input types to a list of the
output types.
\end_layout
\begin_layout Subsection
Jigsaw Puzzle Pieces and Sheaves
\end_layout
\begin_layout Standard
Caution: the idea of Lambdas, and of Arrows, while extremely widespread
in programming practice, is the source of tremendous confusion and difficulty
in knowledge representation.
Even worse: just as fish are unaware of water, most programmers are unaware
of alternatives to lambdas.
\end_layout
\begin_layout Standard
There is one extremely important alternative, discussed in other texts in
this series: the jigsaw puzzle piece, and its tab and slot connectors.
Telegraphically: if one has a function
\begin_inset Formula $f\left(x\right)$
\end_inset
and beta-reduces it with 42 to get
\begin_inset Formula $f\left(42\right)$
\end_inset
, one is 'connecting' the jigsaw-puzzle slot
\begin_inset Formula $x$
\end_inset
in
\begin_inset Formula $f\left(x\right)$
\end_inset
to the jigsaw-puzzle tab 42.
That is, beta reduction is an example of jigsaw-puzzle assembly.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/puzzle-beta-reduce.eps
lyxscale 70
width 40col%
\end_inset
\end_layout
\begin_layout Standard
The two pieces can be connected together only if the connector types match:
the slot and the tab must have matching types but opposite sexes.
This ensures the type-safety of beta-reduction.
Observe the coloring of the vertexes in the above diagram.
At the bottom, there are two black (
\begin_inset Quotes eld
\end_inset
full
\begin_inset Quotes erd
\end_inset
) vertexes, connected by a (full) edge.
At the top, the open-colored vertexes are (unconnected)
\begin_inset Quotes eld
\end_inset
connectors
\begin_inset Quotes erd
\end_inset
, and the edges are
\begin_inset Quotes eld
\end_inset
half-edges
\begin_inset Quotes erd
\end_inset
, not yet fully formed until the connection is made.
\end_layout
\begin_layout Standard
Full-fledged jigsaw puzzle pieces can connect in every-which way (provided
that the tabs and slots are correctly mated).
This is more general than term algebras, in which term trees are always
DAGs.
That is, a lambda is an anonymous term, an arrow is a component of a term
tree.
For computer programming (functional or imperative), one thinks about calling
functions and methods with arguments, leading to the notion of an abstract
syntax tree.
Function calls and arrow types naturally construct trees, or, more generally,
DAGs.
Graphs with loops, or graphs with undirected edges do not naturally occur
in lambda calculus or functional programming.
\end_layout
\begin_layout Standard
For knowledge representation, it does not have to be that way.
The directionality of the arrow can be discarded, and mating can be indicated
with the connectors themselves.
That is, the ArrowLink is a special case of a more general jigsaw-puzzle-piece
link:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(ConnectorSeq
\end_layout
\begin_layout Plain Layout
(Connector
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode)
\end_layout
\begin_layout Plain Layout
(DirectionNode
\begin_inset Quotes eld
\end_inset
input
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(Connector
\end_layout
\begin_layout Plain Layout
(TypeNode 'ConceptNode)
\end_layout
\begin_layout Plain Layout
(DirectionNode
\begin_inset Quotes eld
\end_inset
input
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(Connector
\end_layout
\begin_layout Plain Layout
(TypeNode 'FooBarBodyLink)
\end_layout
\begin_layout Plain Layout
(DirectionNode
\begin_inset Quotes eld
\end_inset
output
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\end_inset
This example shows only two direction types (direction
\begin_inset Quotes eld
\end_inset
sexes
\begin_inset Quotes erd
\end_inset
):
\begin_inset Quotes eld
\end_inset
input
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
output
\begin_inset Quotes erd
\end_inset
.
There is no particular need to restrict to such heterosexual connection
types or mating rules.
One can have a single sex, which, when connected, gives undirected edges.
One can have three or more sexes, with peculiar mating rules for which
can attach to which.
Natural examples occur in chemistry (bonds), in biochemistry (reactomes),
in biology (mating types of fungii) and in medicine (infectious disease
transmission.) Examples from computer science include polymorphic types.
A particularly strong example comes from linguistics: the Link Grammar,
where the notion of jigsaw puzzle pieces is made explicit.
\begin_inset CommandInset citation
LatexCommand cite
key "Sleator1991,Sleator1993"
literal "false"
\end_inset
\end_layout
\begin_layout Standard
What is the point of all of this? It is to reformulate or generalize the
notion of beta reduction and functional programming into a general setting,
more sutiable for general knowledge prepresentation.
One can, of course, fall back to earlier concepts of a directed edge, and
represent everything in terms of vertices and edges.
But the shortfalls of a conventional graph representation have already
been discussed: not just representational shortfalls, but also algorithmic
issues, with RAM and CPU consumption.
The point of the jigsaw puzzle paradigm is that it provides locality of
data and ease of assembly.
Partially assembled jigsaws obey the sheaf axioms.
Sheaves are generically useful for representing knowledge.
\end_layout
\begin_layout Standard
To conclude: metatrees are naturally typed; those types are naturally reified;
the reifications are recursive, and the level of recursion is limited by
the imagination.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Evaluation / Execution
\end_layout
\begin_layout Standard
Metatrees generalize the notion of trees.
A special case of trees are the
\begin_inset Quotes eld
\end_inset
abstract syntax tree
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Abstract_syntax_tree
\end_layout
\end_inset
\end_layout
\end_inset
The denotational semantics of abstract syntax trees is that they are executable
programs.
Thus, an expression such as
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
if (a > b) return a+b;
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
can be represented by an abstract syntax tree, given below:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(IfLink
\end_layout
\begin_layout Plain Layout
(GreaterThanLink
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
a
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
b
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(PlusLink
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
a
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
b
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\end_inset
\end_layout
\begin_layout Standard
As such, some metatrees can serve a dual purpose: both to record syntactic
structure, and to be executable.
Perhaps this feels painfully obvious at this point; if this is the case,
it should be contrasted to the situation of programming in lisp or scheme.
First of all, in lisp, one is programming, not representing data.
The source code for lisp programs resides in files, not in databases.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Let's not be silly.
Of course one could stick the source code into a database.
But how would you write a query to get it back out, and evaluate it? In
lisp? Well, yes, of course, one could write some wrappers to do that.
So what? Are you representing knowledge yet? Did you create a knowledge
query system?
\end_layout
\end_inset
In the end, a lisp program is always executable (evaluatable); if it is
not, that is because it is broken in some way (or you just quoted the whole
thing).
This is not the case here: there is nothing about metatrees that makes
them inherently evaluatable or executable.
Indeed, the above fragment is not executable until the variables are bound
to some values.
Worse, its ambiguous as to what should happen if a is not greater than
b.
As a program, it is not really valid.
As a metatree, it is as good as any other, differing only in having the
hint of being possibly, potentially evaluatable.
\end_layout
\begin_layout Standard
A subset of metatrees can be considered to be a programming language.
This may appear to be self-evident; that this has not been the case historicall
y is demonstrated below.
\end_layout
\begin_layout Subsection
Fexprs, Macros and Rewriting
\end_layout
\begin_layout Standard
In lisp, functions that act on abstract syntax trees are called
\begin_inset Quotes eld
\end_inset
fexprs
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Fexpr
\end_layout
\end_inset
\end_layout
\end_inset
Modern lisps no longer explicitly support fexprs; an influential paper
from 1980 labeled them as harmful, and made the argument that macros were
superior.
\end_layout
\begin_layout Standard
That's all well and good, but macros, as defined in lisp/scheme, can only
be
\begin_inset Quotes eld
\end_inset
run once
\begin_inset Quotes erd
\end_inset
.
Macros run on source expressions, and they expand the source expression
into something evaluatable.
That is, macro languages allow the programmer to define a set of rewrite
rules to transform input syntax trees into output syntax trees.
However, conceived of as macros, they can only be run once, during a pre-proces
sing stage; they cannot be run later, once the resulting program has started
executing.
In this sense, they are limited in a way that fexprs are not.
\end_layout
\begin_layout Standard
This is in sharp contrast to the needs of predicate logic
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/First-order_logic
\end_layout
\end_inset
\end_layout
\end_inset
and proof theory.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Proof_theory
\end_layout
\end_inset
\end_layout
\end_inset
Theorem provers are constructed out of term rewriting systems.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Rewriting
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Abstract_rewriting_system
\end_layout
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Note that SQL does offer a poor-mans term rewriting system.
It is not general, and not suited to the general needs of term rewriting,
but it is plenty enough to enable
\begin_inset Quotes eld
\end_inset
data processing
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
And I do mean
\begin_inset Quotes eld
\end_inset
data processing
\begin_inset Quotes erd
\end_inset
in all of its glorious 1960's generality: performing database queries to
associate an electric utility customer's account with their electric usage
for that month, and their mailing address, and print a bill to be mailed
to the customer.
This is, in a sense, quintessential data processing, and central to it
is the database holding names, accounts and monthly usages.
\end_layout
\end_inset
For example
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
CREATE TABLE foo (name TEXT, number INT);
\end_layout
\begin_layout Plain Layout
CREATE TABLE bar (person TEXT, phone INT, nickname TEXT);
\end_layout
\begin_layout Plain Layout
INSERT INTO bar(person, phone) SELECT name, number FROM foo;
\end_layout
\end_inset
performs a rewrite of records (rows) from one table to another.
Some sort of ability to perform rewrites is innate to any database system,
as a primary need is not only to store data, but to perform transformations
on it.
These transformations must be done at run-time, dynamically; they cannot
be done at
\begin_inset Quotes eld
\end_inset
compile time
\begin_inset Quotes erd
\end_inset
, the way that the lisp/scheme macro system performs them.
\end_layout
\begin_layout Standard
It should be clear that metagraphs in and of themselves are fairly useless
without some sort of term rewriting system to go along with them; this
was already implied in the earlier discussions concerning database queries.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Maude
\begin_inset CommandInset citation
LatexCommand cite
key "Maude1999"
literal "false"
\end_inset
is an example of a term rewriting system disassociated from theorem provers,
databases and inference engines.
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
http://maude.cs.uiuc.edu/maude1/manual/maude-manual-html/maude-manual_0.html
\end_layout
\end_inset
and
\begin_inset Flex URL
status open
\begin_layout Plain Layout
http://maude.cs.illinois.edu/w/index.php/The_Maude_System
\end_layout
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
What is new here is that, if the metagraphs are represented as s-expressions,
some of those s-expressions are potentially evaluatable, and thus lisp-like.
Unlike conventional lisp, the evaluation system must live in harmony with
the term rewriting system; thus, enabling the evaluation of metatrees seems
to require some sort of clearly defined fexpr or $vau interfaces in the
evaluator.
\end_layout
\begin_layout Subsection
ProLog
\end_layout
\begin_layout Standard
An alternative to the lisp/scheme fexpr/$vau mindset is provided by ProLog.
It is both a programming language, in that ProLog programs are executable,
and it is a knowledge store, in that the Datalog fragment of ProLog is
explicitly intended to store data.
\end_layout
\begin_layout Standard
ProLog makes abstract syntax trees explicit: it is hard to understand how
prolog works, unless one learns to think in terms of trees.
Certainly, the
\begin_inset Quotes eld
\end_inset
cut operator
\begin_inset Quotes erd
\end_inset
in prolog is one of the early stumbling blocks for programmers learning
prolog.
It's hard to see what it does, until one realizes that it is literally
cutting branches off of a tree.
At the same time, chapter one, the very first chapter of any book on prolog
programming is rife with examples of knowledge representation.
One will find something like this:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
parent_child(tom, erica).
\end_layout
\begin_layout Plain Layout
parent_child(mike, tom).
\end_layout
\begin_layout Plain Layout
sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y).
\end_layout
\end_inset
The first two statements are assertions of fact, the third is a inference
rule.
They have a very obvious representation as trees, and, more precisely as
meta-trees.
Yet, strangely, prolog programs are encoded in text files, and
\emph on
not
\emph default
as a collection of entries in a graph database!
\end_layout
\begin_layout Standard
This last observation becomes truly bizarre, if one imagines some non-trivial
knowledge representation problem.
Imagine keeping census data in prolog.
Maintaining a text file with dozens of lines of code per person, for millions
of people is absurd.
Applying transformations or graph rewrites is impossible for text files.
Consider the inference
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sibling
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
above.
It can be taken as a run-time directive, but it can also be taken as a
graph rewrite rule: find all graphs having two terms,
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
parent_child(Z, X)
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
parent_child(Z, Y)
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
and create a new term
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
sibling(X, Y)
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
.
Such a rewrite is not all that hard in a database; in SQL, some appropriate
combination of
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
SELECT INTO
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
JOIN
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The only stumbling block being the need to reference the
\begin_inset Quotes eld
\end_inset
parents
\begin_inset Quotes erd
\end_inset
table twice during the join.
Hmm...
what was that bit, about explicit graph-walking, again?
\end_layout
\end_inset
Looking at it this way, prolog
\begin_inset Quotes eld
\end_inset
wants
\begin_inset Quotes erd
\end_inset
to live in a database.
Yet it doesn't.
\end_layout
\begin_layout Standard
So, yes, superficially, databases and execution are orthogonal concerns.
But if one begins to look at what people actually do, in practice, with
SQL, and how, in practice, they design code for object-relational databases,
that orthogonality gets a bit fuzzy.
It's downright cloudy by the time one is writing PL/SQL statements.
Coming from the opposite direction, as prolog does, makes the
\begin_inset Quotes eld
\end_inset
separation of concerns
\begin_inset Quotes erd
\end_inset
even cloudier.
\end_layout
\begin_layout Subsection
Intermediate Languages
\end_layout
\begin_layout Standard
These aren't even the only examples.
Inside of compilers, one finds
\begin_inset Quotes eld
\end_inset
intermediate languages
\begin_inset Quotes erd
\end_inset
.
For Microsoft, this is the CIL or Common Intermediate Language.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://en.wikipedia.org/wiki/Common_Intermediate_Language
\end_layout
\end_inset
\end_layout
\end_inset
For Gnu GCC, it is GIMPLE.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://gcc.gnu.org/wiki/GIMPLE
\end_layout
\end_inset
\end_layout
\end_inset
For LLVM, it is the LLVM IR.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://hub.packtpub.com/introducing-llvm-intermediate-representation/
\end_layout
\end_inset
\end_layout
\end_inset
These are somewhat like assembly code, but abstract, and not specific to
CPU instruction sets.
They encode abstract syntax trees, and thus sit above the bytecode/instruction-
set layer.
Looking carefully, one will observe that
\begin_inset Quotes eld
\end_inset
compiler optimization
\begin_inset Quotes erd
\end_inset
actually consists of a very small database of the currently active, non-retired
abstract syntax trees, and that optimization is a collection of re-write
rules (in the sense of the prolog rewrite rule, above) being applied to
the trees in the active database.
\end_layout
\begin_layout Standard
Of course, what happens inside a compiler is very narrow, and very carefully
crafted to suit the needs of the compiler, and nothing more.
This is a high art that has been honed over many decades.
Intermediate languages are almost never written to disk, except during
debugging, when they are presented to the programmer as text strings.
Yet the lessons they teach can be taken as generic: creating graphs, and
then transforming them, via graph re-writing, is a generically useful operation.
Representing knowledge as trees, and specifically, as typed meta-trees,
offers a huge representational efficiency over plain graphs or SQL tables
or key-value stores.
The efficiency is both computational (RAM usage, CPU cycles) and expressive:
writing inferences in prolog really is a lot easier than writing SQL statements.
\end_layout
\begin_layout Subsection
Human-oriented vs.
Machine-oriented
\end_layout
\begin_layout Standard
ProLog is a human-oriented programming language.
It is expected that humans are going to write prolog, and thus the language
features are designed to be easy for humans to manipulate.
In this sense, it is like almost all programming languages – almost all,
but not all.
\end_layout
\begin_layout Standard
The intermediate languages are not human-oriented, but machine oriented.
It is not expected that programmers will be writing in intermediate languages,
no more than they are expected to write in assembly code.
Intermediate languages are designed to be easy to use by machines: specifically
, by the internal algorithms of compilers.
A compiler needs to turn high-level languages into assembly code.
The resulting assembly code should run fast; but how to perform the optimizatio
n, the rearrangement of terms that enables fast assembly? Some compiler
optimizations can be done directly on the input source: for example, loop
hoisting.
Some compiler optimizations can be done directly on the assembly: for example,
peephole optimizations.
The vast majority of desirable program transformations cannot be done in
either the source language or the target language.
This is why intermediate languages exist.
Intermediate languages are fine-tuned to make it easy for algorithms to
read and write them.
They are designed for machines, and not for people.
\end_layout
\begin_layout Standard
It appears that any kind of programming language constructed from raw metatree
s-expressions is more machine friendly than it is human-friendly.
The example given earlier:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\footnotesize\sffamily},tabsize=3"
inline false
status open
\begin_layout Plain Layout
(IfLink
\end_layout
\begin_layout Plain Layout
(GreaterThanLink
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
a
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
b
\begin_inset Quotes erd
\end_inset
))
\end_layout
\begin_layout Plain Layout
(PlusLink
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
a
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Plain Layout
(VariableNode
\begin_inset Quotes eld
\end_inset
b
\begin_inset Quotes erd
\end_inset
)))
\end_layout
\end_inset
is stunningly verbose, as compared to the far more succinct
\begin_inset Quotes eld
\end_inset
\family sans
\size footnotesize
\emph on
if (a > b) return a+b;
\family default
\size default
\emph default
\begin_inset Quotes erd
\end_inset
.
Although humans can (and do) write metagraph programs using the s-expression
representation, it is rather tedious to type up, and rather painful to
read.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Heh.
In fact, I (we: other users too) write metatree s-expressions daily.
Perhaps this is a case of
\begin_inset Quotes eld
\end_inset
do as I say, not as I do
\begin_inset Quotes erd
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
To conclude: although some metatrees might be executable or evaluatable,
and thus constitute a programming language, it does not appear to be a
language that is particularly human-friendly, at least, not in its s-expression
representation.
\end_layout
\begin_layout Standard
Lets ruminate one more paragraph on this.
One
\emph on
could
\emph default
create a human-readable language on top of of metatree s-expressions.
There have been at least two larger efforts:
\begin_inset Quotes eld
\end_inset
ghost
\begin_inset Quotes erd
\end_inset
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/Ghost
\end_layout
\end_inset
\end_layout
\end_inset
and
\begin_inset Quotes eld
\end_inset
MeTTa
\begin_inset Quotes erd
\end_inset
,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/wikihome/images/b/b7/MeTTa_Specification.pdf
\end_layout
\end_inset
which can be found in the
\begin_inset Flex URL
status open
\begin_layout Plain Layout
https://wiki.opencog.org/w/Hyperon:Atomese
\end_layout
\end_inset
wiki page.
\end_layout
\end_inset
as well as some lesser efforts (a chatbot triplestore).
Doing so defeats the machine-readability of the s-expressions themselves.
Much of the primary utility of using metatrees comes from being able to
apply graph rewriting rules to them.
A graph rewrite rule consists of a pattern template to be matched, and
the resultant transformation.
When the template is an s-expression, of the kind given in the section
on MetaQuery Language, then it is easy to match.
When it is something else, the application of the pattern rules becomes
difficult.
The pattern language can no longer be simple, and worse, the pattern language
diverges from the source language itself.
The s-expression form seems to hit a happy medium: the pattern language
is a valid subset of the whole language.
It is easy to parse, making it ideal for algorithmic manipulation.
It is too low-level to make it comfortable for humans; but given that we
live in a machine age, this is perhaps a not unexpected twist.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Atomese
\end_layout
\begin_layout Standard
Almost all of the various ideas articulated in this text have been implemented
in the OpenCog AtomSpace, nominally going under the name of Atomese.
Historically, it was created to be a knowledge representation system in
which probabilistic reasoning could be performed.
Regular use and the pressures of user demands have forced the sharpening
of various concepts and features, most of which have been reviewed above.
\end_layout
\begin_layout Standard
The platform continues to be deployed in production systems, while also
being an experimental platform for the development of new ideas.
As these are found to be sound, the system does, as a whole, mutate.
\end_layout
\begin_layout Standard
If the reader of this text finds any of the above concepts to be dubious,
or perhaps ill-defined and in need of sharpening, they are encouraged to
contact the mailing list.
The AtomSpace, and Atomese are malleable.
Bad ideas do need to be replaced by good ones.
\end_layout
\begin_layout Standard
If the reader of this text finds any of the above concepts to be vague,
then please note that AtomSpace source code repo contains a large variety
of example demos of each of the discussed features.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See
\begin_inset CommandInset href
LatexCommand href
name "https://github.com/opencog/atomspace/tree/master/examples"
target "https://github.com/opencog/atomspace/tree/master/examples"
literal "false"
\end_inset
\end_layout
\end_inset
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Conclusion
\end_layout
\begin_layout Standard
Several important claims were made about metagraphs and metagraph stores.
These were:
\end_layout
\begin_layout Itemize
Metagraphs are a simple and relatively minor generalization of graphs.
\end_layout
\begin_layout Itemize
Metagraphs are more representationally compact than graphs.
They are more efficient at representing data.
\end_layout
\begin_layout Itemize
Metagraph query is more general than SQL-inspired query systems, and breaks
out of the table-join paradigm that is most commonly offered in graph-query
systems.
\end_layout
\begin_layout Itemize
Table normalization, normally an intellectually demanding task for relational
database design, comes
\begin_inset Quotes eld
\end_inset
for free
\begin_inset Quotes erd
\end_inset
, when one works with metagraphs.
\end_layout
\begin_layout Itemize
Specifying metagraphs as text strings is easier than specifying graphs as
strings.
\end_layout
\begin_layout Itemize
Metatrees are naturally typed.
Ordinary graphs are not.
\end_layout
\begin_layout Itemize
Metatrees are naturally (even trivially) reified.
Ordinary graphs are not.
\end_layout
\begin_layout Itemize
Metatrees are naturally abstract syntax trees; this is possible but not
natural when working with ordinary graphs.
\end_layout
\begin_layout Itemize
Metagraphs are foundational, providing a common platform for a broad variety
of computing tasks: ranging from data storage, to symbolic computing and
inference, to functional (or imperative) programming.
\end_layout
\begin_layout Itemize
Metagraphs are low-level.
They appear to be ideal for algorithmic manipulation.
They are sufficiently human-readable to allow daily authoring, but they
are not a substitute for a proper high-level programming language targeting
humans as the programmers.
\end_layout
\begin_layout Standard
This text started out as an attempt to describe the RAM and CPU usage properties
of metagraphs, and unwittingly turned into a strong statement about the
general utility of metagraphs as a foundational system.
As such, it provides a strong statement about many of the design decisions
that went into the OpenCog AtomSpace, which is the primary research vehicle
for these ideas.
Even so, it is not the culmination of the journey.
The series of chapters in this directory are about sheaves.
These provide a general connectionist approach to data representation,
and the sheaf approach is different from metagraphs, having distinct representa
tional properties (including CPU and RAM usage).
Understanding metagraphs is a key gateway to the sheaves project.
Fortunately, the metagraph approach, taken by the current AtomSpace is
fairly mature, having more than a decade of implementation and use experience
behind it.
This text gives a flavor of where it has arrived.
\end_layout
\begin_layout Section
Thanks
\end_layout
\begin_layout Standard
The second revision of this text has benefited from the (witting or unwitting)
helpful input of Amirouche Boubekki, Kino Coursey, John Cowan, Marc Nieper-Wißk
irchen, Adam Vandervorst and Steven Wiley.
Absolutely none of this would have been possible without a decade's worth
of gracious support and tutelage of Ben Goertzel.
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Standard
\begin_inset CommandInset bibtex
LatexCommand bibtex
btprint "btPrintCited"
bibfiles "lang"
options "tufte"
\end_inset
\end_layout
\end_body
\end_document