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

Map-based storage implementation using Maps and MapSets.

This is the default storage backend. It uses immutable Elixir data structures
(Maps and MapSets) which are thread-safe and easy to inspect, but may suffer
GC pressure for very large fact sets (>100K tuples). For workloads exceeding
100K facts, use `Storage.ETS` which provides off-heap storage and better
concurrent read scalability.

## Internal structure

    %{
      relations: %{
        "parent" => MapSet.new([{:alice, :bob}, {:carol, :dave}]),
        ...
      },
      indexes: %{
        {"parent", [1]} => %{
          {:bob} => MapSet.new([{:alice, :bob}]),
          {:dave} => MapSet.new([{:carol, :dave}])
        }
      },
      schemas: %{
        "parent" => %{arity: 2, types: [:atom, :atom]},
        ...
      }
    }

Index keys are always tuples, even for single-column indexes. This avoids
ambiguity between a plain value and a 1-tuple.

# `index`

```elixir
@type index() :: %{required(ExDatalog.Storage.key_values()) => MapSet.t()}
```

# `t`

```elixir
@type t() :: %ExDatalog.Storage.Map{
  indexes: %{
    required({ExDatalog.Storage.relation_name(), ExDatalog.Storage.index_key()}) =>
      index()
  },
  relations: %{required(ExDatalog.Storage.relation_name()) => MapSet.t()},
  schemas: ExDatalog.Storage.schemas()
}
```

# `build_index`

```elixir
@spec build_index(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.index_key()
) :: t()
```

Builds a hash index on the specified columns for a relation.

Creates a lookup structure mapping projected column values to sets of
tuples. Raises `ArgumentError` if `relation` is not in the schema.

# `capabilities`

```elixir
@spec capabilities(t()) :: ExDatalog.Capabilities.t()
```

Returns the capabilities of this storage backend.

The Map backend supports arithmetic, comparison, type-check, and string
constraints, provenance, but does not support indexed lookup or concurrent
reads. It uses on-heap immutable Elixir data structures.

# `get_indexed`

```elixir
@spec get_indexed(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.index_key(),
  ExDatalog.Storage.key_values()
) :: Enumerable.t()
```

Retrieves tuples matching an indexed key.

Returns tuples from a pre-built index that match the given `key` on the
specified `columns`. Returns `[]` if the index or key does not exist.

Must call `build_index/3` before calling `get_indexed/4` for the same
relation and columns.

# `init`

```elixir
@spec init(ExDatalog.Storage.schemas()) :: t()
```

Initializes storage for the given relation schemas.

`schemas` is a map from relation name to `%{arity: n, types: [atom()]}`.
Creates an empty `MapSet` for each relation and returns the initial state.

Raises if two schemas share the same relation name (should be caught by
validation before reaching storage).

# `init`

```elixir
@spec init(
  ExDatalog.Storage.schemas(),
  keyword()
) :: t()
```

# `insert`

```elixir
@spec insert(t(), ExDatalog.Storage.relation_name(), ExDatalog.Storage.tuple_values()) ::
  t()
```

Inserts a single tuple into a relation.

Idempotent: inserting a tuple that already exists is a no-op (MapSet semantics).
Raises `ArgumentError` if `relation` is not in the schema.

# `insert_many`

```elixir
@spec insert_many(t(), ExDatalog.Storage.relation_name(), Enumerable.t()) :: t()
```

Inserts an enumerable of tuples into a relation.

More efficient than repeated `insert/3` calls for bulk loading, as it
reduces Map updates. Idempotent for individual tuples.
Raises `ArgumentError` if `relation` is not in the schema.

# `member?`

```elixir
@spec member?(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.tuple_values()
) :: boolean()
```

Checks whether a tuple exists in a relation.

Returns `true` if `tuple` is a member of the `relation`'s MapSet,
`false` otherwise. Returns `false` if `relation` is unknown.

# `relations`

```elixir
@spec relations(t()) :: [ExDatalog.Storage.relation_name()]
```

Returns a sorted list of all relation names in the storage.

Useful for debugging and introspection.

# `size`

```elixir
@spec size(t(), ExDatalog.Storage.relation_name()) :: non_neg_integer()
```

Returns the number of tuples stored in a relation.

Returns `0` if `relation` is unknown.

# `stream`

```elixir
@spec stream(t(), ExDatalog.Storage.relation_name()) :: Enumerable.t()
```

Returns all tuples in a relation as a deterministically sorted list.

Used by the engine to iterate over a relation's facts during join
evaluation. Returns `[]` if `relation` is unknown.

The output is sorted to guarantee deterministic iteration order regardless
of the underlying data structure's internal ordering. This ensures that
identical programs with identical facts produce identical results across
all storage backends.

# `teardown`

```elixir
@spec teardown(t()) :: :ok
```

Releases resources held by this storage backend.

For the Map backend, this is a no-op since all data is held in immutable
Elixir data structures that are garbage-collected automatically.

# `update_index`

```elixir
@spec update_index(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.index_key(),
  Enumerable.t()
) :: t()
```

Incrementally merges delta tuples into an existing index.

If no index exists for the given relation and columns, one is built from
the current relation data first, then the delta is merged in.

Raises `ArgumentError` if `relation` is not in the schema.

---

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