# Databases

- Key Value Store
- Algorithms
- Theory
- SQL
- Ontology Formats
- Optimal Joins
- Vectorized Execution
- Multi Version Concurrency Control
- Duckdb
- Relational AI
- Streaming
- Data Structures
- CRDTs
- Big Data
- Graph systems
- Resources

See also:

- Datalog
- concurrency

# Key Value Store

log structured storage a log is a append only store LSM - log structured merge trees. In memory table for writes. Flushed to disk. Multiple read only written to disk, coalesced in background. sstable Tombstone records for deletes. https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

What’s the big deal about key-value databases like FoundationDB and RocksDB? lobster comments https://lobste.rs/s/avljlh/what_s_big_deal_about_embedded_key_value#c_rx0oid

wide-column store key/value store

- bigtable google internal
- cassandra
- leveldb
- redis
- indexeddb
- Foundationdb
- cockroachdb sql database originally on rocksdb now on pebbledb https://www.cockroachlabs.com/blog/pebble-rocksdb-kv-store/
- pebbledb

Embedded key value store. Backing engines. MySql has support for many backing engines

# Algorithms

B-trees

OLTP online transaction processing OLAP online analytical processing hyperloglog bloom filters cuckoo filter

# Theory

## Conjunctive Queries

Query containment

- See finite model theory

descriptive complexity NC^0 bounded fan in AC^0 https://en.wikipedia.org/wiki/AC0 unbounded fan in circuit. Constant height https://en.wikipedia.org/wiki/Circuit_complexity

https://pages.cs.wisc.edu/~paris/cs838-s16/lecture-notes/lecture1.pdf

Foundations of database

## Schema

https://en.wikipedia.org/wiki/Database_normalization

schema is finite set of relation symbol names an instance is a set of concrete relations with those symbol names. Sometimes also called a structure

## Functional Dependencies

Armstrong axioms

Normal Formals

Tuple Generating dependencies

## Query Optimization

Cascades framework https://github.com/egraphs-good/egg/discussions/189

Zetasql calcite

## The Chase

Equality Generating Dependencies The Chase Procedure and its Applications in Data Exchange

Yisu: query optimization data integration querying incomplete databases benchmarking the chase chasebench

Chasefun, DEMOo, Graal, llunatic, pdg, pegasus, dlv, e, rdfox

Stratgeies - (restricted, unrestricted, parallel, skolem, fresh-null

Chase Strategies vs SIPS

The power of the terminating chase

Is the chase meant to be applied to actual databases, symbolic databases / schema, or other dependencies? Is it fair the say that the restricted chase for full dependencies is datalog?

Alice book chapter 8-11

Graal - https://github.com/hamhec/DEFT https://hamhec.github.io/DEFT/ defeasible programming http://lidia.cs.uns.edu.ar/delp_client/ Something about extra negation power? Defeatable rules if something contradicts them Pure is part of graal

llunatic - https://github.com/donatellosantoro/Llunatic

RDfox - https://docs.oxfordsemantic.tech/

dlgp - datalog plus format. Allows variables in head = existentials. Variables in facts.
Notion of constraint `! :- `

and notion of query. Hmm.

Direct modelling of union find in z3? homomorphism is union find

# SQL

sql injection https://ctf101.org/web-exploitation/sql-injection/what-is-sql-injection/ everything is foreign keys? Interning

Recursive tables let you do datalog like stuff.

```
CREATE TABLE edge(a INTEGER, b INTEGER);
INSERT INTO edge(a,b)
VALUES
(1,2),
(2,3),
(3,4);
SELECT a,b FROM edge;
CREATE TABLE path(a INTEGER, b INTEGER);
--INSERT INTO path
--SELECT * FROM edge;
-- path(x,z) :- edge(x,y), path(y,z).
WITH RECURSIVE
path0(x,y) AS
-- SELECT 1,2
(SELECT a,b FROM edge UNION SELECT edge.a, path0.y FROM edge, path0 WHERE path0.x = edge.b )
INSERT INTO path SELECT x,y FROM path0;
SELECT a,b FROM path;
.quit
```

UF

```
WITH RECURSIVE
parent(x,y) AS
SELECT a, min(b) (SELECT (a,b) FROM eq UNION eq, parent)
```

```
import sqlite3
con = sqlite3.connect(':memory:')
cur = con.cursor()
# Create table
cur.execute('''CREATE TABLE stocks
(date text, trans text, symbol text, qty real, price real)''')
# Insert a row of data
cur.execute("INSERT INTO stocks VALUES ('2006-01-05','BUY','RHAT',100,35.14)")
#cur.executemany("insert into characters(c) values (?)", theIter)
for row in cur.execute('SELECT * FROM stocks ORDER BY price'):
print(row)
```

adapters to python types https://en.wikipedia.org/wiki/Materialized_view

```
```

## indices

## views

Saved queries that act as virtual tables

## triggers

This is interesting

## Aggregate functions

## Window Functions

# Ontology Formats

graph database OWL RDF sparql sparql slides shacl -

semantic web

Knowdlege representation handbook Course https://web.stanford.edu/class/cs227/Lectures/lec02.pdf very similar to bap knoweldge base

# Optimal Joins

worst case optimal join algorithm leapfrog triejoin https://github.com/frankmcsherry/blog/blob/master/posts/2018-05-19.md Dovetail join - relational ai unpublished. Julia specific ish? https://relational.ai/blog/dovetail-join use sparsity of all relations to narrow down search Worst case optiomal join Ngo pods 2012 leapfrog triejoin simpel worst case icdt 2015 worst case optimal join for sparql worst case optimal graph joins in almost no space Correlated subqueries: unnesting arbitrary queries How materializr and other databases optimize sql subqueries

genlteish intro to worst case optimal joins

Adopting Worst-Case Optimal Joins in Relational Database Systems tries The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases Persistent Storage of Adaptive Radix Trees in DuckDB

umbra spiritual successor to hyper. Hybridizes an in memory system to also work off ssd.

# Vectorized Execution

cmu adavanced course lecture Rethinking SIMD Vectorization for In-Memory Databases

masked/selective load masked/selective store scatter gather

selection: branched vs branchless branched checks condition to see if should copy row out branchless writes but only increments index of storage by one if condition is met. I mean. There is a “branch” in this. But I see your point

EmptyHeaded: A Relational Engine for Graph Processing “generalized hypertree decomposition” ? https://github.com/HazyResearch/EmptyHeaded

levelheaded linear algerba stuff?

# Multi Version Concurrency Control

https://en.wikipedia.org/wiki/Multiversion_concurrency_control

# Duckdb

https://duckdb.org/ sqlite for olap columnar

```
import duckdb
con = duckdb.connect(database=':memory:')
import pandas as pd
test_df = pd.DataFrame.from_dict({"i":[1, 2, 3, 4], "j":["one", "two", "three", "four"]})
con.execute('SELECT * FROM test_df')
#print(con.fetchall())
print(con.fetchdf())
add_df = pd.DataFrame(columns=["x","y","z"])
print(add_df)
counter = 0
def add(x,y):
global counter, add_df
cond = add_df["x"] == x #& add_df["y"] == y
df = add_df[cond]
if not df.empty:
return add_df["z"][0]
else:
z = counter
add_df.append((x,y,z))
counter += 1
return z
print(add(-1,-2))
```

catalog multiversion concrruncy control cimpressed execution binder

# Relational AI

https://www.youtube.com/watch?v=WRHy7M30mM4&ab_channel=CMUDatabaseGroup

snowflake databricks bigquery dbt fivetran

data apps - dapps

lookml sigma legend

Resposnive compilter - matsakis salsa.jl umbra/leanstore

incremental COnvergence of datalog over presmeirings differential dataflor cidr2013 reconciling idfferences 2011 Green F-IVM incrmenetal view mantinance with triple lock fotrization benefits

systemml vecame apache systemds https://systemds.apache.org/

Semantic optimization FAW question asked frequence : Ngo Rudra PODS 2016 What do shannon type ineuqlaities submodular width and disjunctive datalog have to do with one another pods 2017 precise complexity analysis for efficient datalog queries ppdp 2010 functional aggregate queries with additive inequalities convergence of dtalog over pr-esemirign

Relational machine learning Layered aggregate engine for analystics worloads schelich olteanu khamis leanring models over relational data using sparse tenosrs The relational data borg is learning olteanu vldb keynote sturcture aware machine learning over multi relational database relational know graphs as the ofundation for artifical intelligence km-means: fast clustering for relational data https://arxiv.org/abs/1911.06577 Learning Models over Relational Data: A Brief Tutorial

duckdb for sql support calcite postgresql parser

Fortress library traits. OPtimization and parallelism https://relational.ai/blog/categories/research

https://arxiv.org/abs/2004.03716 triangle view mantenance

# Streaming

streaming 101 unbounded data

https://en.wikipedia.org/wiki/Stream_processing

lambda architecture - low latency inaccurate, then batch provides accurate

event time vs processing time

Watermark

Flink Apache Beam millwheel spark streaming

https://materialize.com/blog

# Data Structures

## B Tree

Bw-tree The B-Tree, LSM-Tree, and the Bw-Tree in Between open bw-tree 2018

## Radix Trie

# CRDTs

Conflict Free replicated datatypes https://crdt.tech/ martin Kleppmann

CRDT of string - consider fractional positions. Tie breaking. Bad interleaving problem unique identifiers

- LSeq
- RGA
- TreeSeq

https://www.inkandswitch.com/peritext/ crdt rich text

https://github.com/josephg/diamond-types https://josephg.com/blog/crdts-go-brrr/

https://github.com/yjs/yjs

automerge: library of data structures for collab applications in javascript https://mobiuk.org/abstract/S4-P5-Kleppmann-Automerge.pdf local first. use local persistent storage. git for your app’s data. rust implementation?

isabelle crdt I was wrong. CRDTs are the future

Conflict-free Replicated Data Types” “A comprehensive study of Convergent and Commutative Replicated Data Types

Operational Transformation - sequences of insert and delete. Moves possibly.

delta-based vs state-based https://bartoszsypytkowski.com/the-state-of-a-state-based-crdts/

counters

json crdt for vibes patches?

Tree move op. Create delete subtrees.

Synthesizing CRDTs from Sequential Data Types with Verified Lifting https://arxiv.org/abs/2205.12425

# Big Data

Spark Hadoop MapReduce Dask Flink Storm

Mahout Vowpal Wabbit

## hadboop

Giraph

## Spark

https://en.wikipedia.org/wiki/Apache_Spark Databricks - company bigdatalog https://www.cis.upenn.edu/~susan/cis700/Papers/BigDataAnalyticsSPARK.pdf https://github.com/ashkapsky/BigDatalog MLlib spark streaming graphx

## Message brokrs

RabbitMQ Kafka

## Services

BigQuery Snowflake Azure AWS

# Graph systems

It isn’t that relational systems can’t express graph problems. But maybe graph systems are more optimized for the problem neo4j Giraph Powergraph graphrex graphx myria graphchi xsteam gridgraph graphlab

## SQL

`create table`

`create index`

`explain query plan`

I saw`explain analyze`

elsewhere`select`

`vacuum`

- defrag and gabrage collect the db`begin transaction`

## sqlite

sqlite commands that are interesting

`.help`

`.dump`

`.tables`

`.schema`

`.indexes`

`.expert`

suggests indices?

# Resources

## Conferences

- SIGMOD PODS https://sigmod.org/pods-home/ pods uutorials https://sigmod.org/pods-home/pods-tutorials/ Testy of time awards Cool stuff in here.
- VLDB
- HYTRADBOI https://www.hytradboi.com/ also very cool stuff.
## Misc

Datavases, types, and the relational model The third manifesto

duckdb embedded like sqlite?

Conjunctive-query containment and constraint satisfaction

Designing Data intensive systems martin kleppmann

scalability but at what cost? big systems vs laptops.

Data integration the relational logic approach

postgres indexes for newbies postgres tutorial raytracer in sql [advent of code sql(https://news.ycombinator.com/item?id=29467671)] sqllancer detecting lgoic bugs in dbms

- Differential Datalog
- CRDTs
- Differential Dataflow
- Nyberg Accumulators
- Verkle Trees
- Cryptrees
- Byzantine Eventual Consistency
- Self-renewable hash chains
- Binary pebbling

https://github.com/dbuenzli/rel

Ezra Cooper. The Script-Writer’s Dream: How to Write Great SQL in Your Own Language, and Be Sure It Will Succeed. 2009. Full text

James Cheney et al. A practical theory of language-integrated query. 2013. Full text

Suzuki et al. Finally, safely-extensible and efficient language-integrated query. 2016. Full text

Oleg Kiselyov et al. Sound and Efficient Language-Integrated Query – Maintaining the ORDER. 2017. Full text

DBSP: Automatic Incremental View Maintenance for Rich Query Languages - mcsherry et al

https://www.reddit.com/r/databasedevelopment/

https://twitter.com/phil_eaton

Ask HN: What could a modern database do that PostgreSQL and MySQL can’t