# `ExDatalog.Storage`
[🔗](https://github.com/thanos/ex_datalog/blob/v0.5.0/lib/ex_datalog/storage.ex#L1)

Behaviour for pluggable relation storage backends.

The storage layer holds all derived facts (the "EDB" and "IDB") and provides
efficient membership tests, iteration, and indexed lookups for join
evaluation.

## Contract

- `init/1` receives relation schemas and returns an initial state.
- `insert/3` and `insert_many/3` add tuples; idempotent (MapSet semantics).
- `member?/3` and `size/2` are O(1) or O(log n) membership and cardinality.
- `stream/2` returns a deterministically sorted `Enumerable.t()` of all
  tuples for a relation.
- `relations/1` lists all relation names in sorted order.
- `capabilities/1` returns the backend's capability metadata.
- `teardown/1` releases backend resources (e.g., ETS tables).
After `teardown/1`, the state must not be used for further operations.

## Indexing

The following indexing callbacks are **optional** (`@optional_callbacks`).
They are defined for alternative engine implementations and future use. The
default engine (`Engine.Naive`) does not use them.

- `build_index/3` creates a hash index on the specified columns.
  Raises `ArgumentError` if `relation` is not in the schema.
- `get_indexed/4` retrieves tuples matching a key via a pre-built index.
- `update_index/4` incrementally merges delta tuples into an existing index.
  Raises `ArgumentError` if `relation` is not in the schema.

`Engine.Naive` uses sequential-scan joins (`Join.join/3`) exclusively. Index
support will be wired into the evaluator in a future release.

## Determinism

All backends **must** guarantee deterministic iteration order from
`stream/2`. Implementations must sort their output so that identical
programs with identical facts produce identical results regardless of the
backend's internal data structure ordering.

## Implementations

- `Storage.Map` — uses Maps and MapSets. Immutable, inspectable,
  excellent for <1M facts.
- `Storage.ETS` — uses ETS for off-heap storage and better
  GC behaviour at scale.

# `index_key`

```elixir
@type index_key() :: [non_neg_integer()]
```

# `key_values`

```elixir
@type key_values() :: tuple()
```

# `relation_name`

```elixir
@type relation_name() :: String.t()
```

# `schemas`

```elixir
@type schemas() :: %{
  required(relation_name()) =&gt; %{arity: non_neg_integer(), types: [atom()]}
}
```

# `state`

```elixir
@type state() :: term()
```

# `tuple_values`

```elixir
@type tuple_values() :: tuple()
```

# `build_index`
*optional* 

```elixir
@callback build_index(state(), relation_name(), index_key()) :: state()
```

# `capabilities`

```elixir
@callback capabilities(state()) :: ExDatalog.Capabilities.t()
```

# `get_indexed`
*optional* 

```elixir
@callback get_indexed(state(), relation_name(), index_key(), key_values()) ::
  Enumerable.t()
```

# `init`

```elixir
@callback init(schemas()) :: state()
```

# `insert`

```elixir
@callback insert(state(), relation_name(), tuple_values()) :: state()
```

# `insert_many`

```elixir
@callback insert_many(state(), relation_name(), Enumerable.t()) :: state()
```

# `member?`

```elixir
@callback member?(state(), relation_name(), tuple_values()) :: boolean()
```

# `relations`

```elixir
@callback relations(state()) :: [relation_name()]
```

# `size`

```elixir
@callback size(state(), relation_name()) :: non_neg_integer()
```

# `stream`

```elixir
@callback stream(state(), relation_name()) :: Enumerable.t()
```

# `teardown`

```elixir
@callback teardown(state()) :: :ok | {:error, term()}
```

# `update_index`
*optional* 

```elixir
@callback update_index(state(), relation_name(), index_key(), Enumerable.t()) :: state()
```

---

*Consult [api-reference.md](api-reference.md) for complete listing*