facts-db/cl-facts/doc/facts.tex

• Show log

  Commit

• Hash : d0286b85
  Author : Thomas de Grivel
  Date : 2022-11-18T18:33:51
  

  facts-db/cl-facts in-memory graph database

Download

• doc/facts.tex

• \documentclass{beamer}
  
  \usepackage[frenchb]{babel}
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{tikz}
  \usetikzlibrary{calc,shapes.multipart,chains,arrows}
  \usepackage{listings}
  \usepackage{color}
  
  \usetheme{Warsaw}
  
  \title{CL-FACTS}
  \author{Thomas de Grivel <thomasdegrivel@gmail.com>}
  \institute{ELS 2017}
  \date{2017-04-03}
  
  \renewcommand{\UrlFont}{\scriptsize}
  
  \setbeamertemplate{navigation symbols}{}
  
  \begin{document}
  
  \begin{frame}
    \titlepage
  \end{frame}
  
  \newcommand{\snode}[2]{\node(#1)[item]{\ensuremath{#2}}}
  
  \begin{frame}
    Unlabelled Skip Lists
    \begin{itemize}
    \item {\bf Skip Lists} : fast, better parallelization than trees.
      \begin{itemize}
      \item Probabillistic data structure.
      \item Search, insert, delete : $O(log\ n)$.
      \item Single link updates are atomic, no locking needed.
      \end{itemize}
      \begin{center}
      \begin{tikzpicture}[
          start chain,
          every node/.style={above,rectangle,minimum height=1mm,minimum width=1mm,
            thick},
          skip3/.style={draw,rectangle split, rectangle split parts=3, draw},
          skip2/.style={draw,rectangle split, rectangle split parts=2, draw},
          skip1/.style={draw,rectangle split, rectangle split parts=1, draw},
          >=stealth
        ]
        \node[skip3](A) at (0,0) {}; \node(AA) at (0,-0.5) {A};
        \node[skip1](B) at (1,0) {}; \node(BB) at (1,-0.5) {B};
        \node[skip2](C) at (2,0) {}; \node(CC) at (2,-0.5) {C};
        \node[skip1](D) at (3,0) {}; \node(DD) at (3,-0.5) {D};
        \node[skip1](E) at (4,0) {}; \node(EE) at (4,-0.5) {E};
        \node[skip3](F) at (5,0) {}; \node(FF) at (5,-0.5) {F};
        \node[skip1](G) at (6,0) {}; \node(GG) at (6,-0.5) {G};
        \node[skip1](H) at (7,0) {}; \node(HH) at (7,-0.5) {H};
        \draw[*->] let \p1=(A.one),  \p2=(F.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(A.two),  \p2=(C.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(A.three),\p2=(B.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(B.one),  \p2=(C.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(C.one),  \p2=(F.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(C.two),  \p2=(D.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(D.one),  \p2=(E.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(E.one),  \p2=(F.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(F.three),\p2=(G.west) in (\x1,\y1+2) -- (\x2,\y1+2);
        \draw[*->] let \p1=(G.one),  \p2=(H.west) in (\x1,\y1+2) -- (\x2,\y1+2);
      \end{tikzpicture}
      \end{center}
    \item {\bf Only values}, no keys. Content addressed memory.
    \end{itemize}
  \end{frame}
  
  \begin{frame}
    Triple store
    \begin{itemize}
    \item {\bf Store} as much data as you want as {\bf triples} $\{Subject, Predicate, Object\}$.
    \item Three {\bf sorted indexes} : $\{S, P, O\}$, $\{P, O, S\}$, $\{O, S, P\}$.
    \item {\bf Iterate} on queries with $[0..3]$ unknown ?values (sic).
    \end{itemize}
  \end{frame}
  
  \begin{frame}
    FACTS:WITH
    \medskip
    {\small
      \lstinputlisting[language=Lisp]{with.lisp}
    }
  \end{frame}
      
  \begin{frame}
    Transactions
    \begin{itemize}
    \item All operations on database are {\bf logged to a file}.
    \item Transactions can be aborted with defined {\bf rollback functions}.
    \item {\bf Persistence} : at startup the log is replayed and the database dumped.
    \end{itemize}
  \end{frame}
  
  \begin{frame}
    Future
    \begin{itemize}
    \item {\bf Disk storage}, for now all data is in-memory.
    \item {\bf Computed facts} inferred from added facts.
    \item {\bf Events} with pattern matching on inserts and deletes.
    \item User defined {\bf indexes} for arbitrarily complex patterns.
    \item RDF, turtle...
    \end{itemize}
  \end{frame}
  
  \begin{frame}
    Links
    \begin{itemize}
    \item {\bf Facts}\\
      \url{https://github.com/thodg/facts}
    \item {\bf Unlabelled Skip List}\\
      \url{https://github.com/thodg/facts/blob/master/usl.lisp}
    \item {\bf Indexes}\\
      \url{https://github.com/thodg/facts/blob/master/index.lisp}
    \item {\bf Rollback}\\
      \url{https://github.com/thodg/rollback}
    \end{itemize}
  \end{frame}
  
  \end{document}
  

Download