Adding Provenance to a Table
============================

Before ProvSQL can track provenance, the extension must be loaded and
provenance must be enabled on each relevant table. ProvSQL represents
provenance as a circuit of gates following the model of
:cite:`DBLP:conf/icdt/DeutchMRT14`.

Loading the Extension
---------------------

In every database where you want provenance support:

.. code-block:: postgresql

    CREATE EXTENSION provsql CASCADE;

The ``CASCADE`` option installs the required ``uuid-ossp`` dependency
automatically.

To call ProvSQL functions without the ``provsql.`` prefix, add ``provsql``
to the search path at the start of each session:

.. code-block:: postgresql

    SET search_path TO public, provsql;

To make this permanent for a specific database:

.. code-block:: postgresql

    ALTER DATABASE mydb SET search_path TO public, provsql;

Most examples in this documentation omit the ``provsql.`` prefix, assuming
``provsql`` is in the search path.

Disabling Provenance Temporarily
----------------------------------

Setting ``provsql.active`` to ``off`` makes ProvSQL silently drop all
provenance annotations for the current session, as if the extension were
not loaded:

.. code-block:: postgresql

    SET provsql.active = off;

This is useful for running queries without provenance overhead while keeping
the extension installed. See :doc:`configuration` for all configuration
variables.

Enabling Provenance on a Table
-------------------------------

Use :sqlfunc:`add_provenance` to add provenance tracking to an existing table:

.. code-block:: postgresql

    SELECT provsql.add_provenance('mytable');

This adds a hidden ``provsql`` column of type ``uuid`` to the table. Each
row receives a freshly generated UUID that identifies a leaf (``input``) gate
in the provenance circuit.

After enabling provenance, every query that reads from ``mytable`` will
automatically carry provenance annotations in its result set.

The table is recorded as TID (tuple-independent) in ProvSQL's
per-database metadata store.  To set up a table as BID
(block-independent) instead, use :sqlfunc:`repair_key` (see
:doc:`probabilities`) on a table that does *not* yet have
provenance: it adds the ``provsql`` column itself and registers the
table as BID with the chosen block-key columns.  Do not call
:sqlfunc:`add_provenance` first; :sqlfunc:`repair_key` is an
alternative to it, not a follow-up.  This classification is consulted
by the safe-query rewriter (the ``'boolean'`` provenance-class opt-in
optimisation, see :doc:`probabilities`) to verify that any
projection it introduces preserves the table's block-key alignment.

.. note::

   :sqlfunc:`add_provenance` must be called on the base table, not on a view.

Accessing the Provenance Token
-------------------------------

The ``provsql`` column is intentionally opaque – it is silently removed
from ``WHERE`` or ``ORDER BY`` clauses. To refer to the current row's
provenance token, use the :sqlfunc:`provenance()` function:

.. code-block:: sql

    SELECT name, provenance() FROM mytable;

Within a query result, the ``provsql`` attribute carries a UUID value that represents the
provenance circuit gate for that tuple.

Removing Provenance
--------------------

To stop tracking provenance for a table (and drop the ``provsql`` column),
use :sqlfunc:`remove_provenance`:

.. code-block:: postgresql

    SELECT provsql.remove_provenance('mytable');

Provenance Mappings
--------------------

A *provenance mapping* associates provenance tokens with values from a table
column. Mappings are the bridge between abstract circuit tokens and
domain-meaningful labels used by semiring evaluation functions.
Use :sqlfunc:`create_provenance_mapping` to create one:

.. code-block:: postgresql

    SELECT create_provenance_mapping('my_mapping', 'mytable', 'column_name');

The mapping is stored as an ordinary PostgreSQL table called ``my_mapping``
with two columns: ``provenance`` (uuid) and ``value`` (the source column's
type).  By default it is a one-off snapshot of the table as it stands.

Pass ``maintained => true`` to keep it current instead:

.. code-block:: postgresql

    SELECT create_provenance_mapping('my_mapping', 'mytable', 'column_name',
                                     maintained => true);

A maintained mapping is extended automatically as new rows are inserted, and
-- crucially -- it stays correct under data modification: a delete or update
rewrites a row's ``provsql`` into a compound gate, but the value remains keyed
to the original input token, so evaluation still resolves it.  This matters
for :doc:`temporal <temporal>` validity, where a row deleted at time *T* must
keep its original interval bounded at *T* rather than losing it.  A maintained
mapping requires ``column_name`` to be a plain column.

ProvSQL Studio
---------------

ProvSQL Studio's :ref:`schema panel <studio-schema-panel>` is an
interactive surface for the operations above:

* it lists every ``SELECT``-able relation, with a purple :sc:`prov`
  pill on tables whose ``provsql`` column is injected by the planner
  (provenance tracking is active) and a gold :sc:`mapping` pill on
  relations shaped ``(value <T>, provenance uuid)``;
* :guilabel:`+ prov` and :guilabel:`− prov` action chips on
  provenance-eligible plain tables prefill the corresponding
  ``SELECT add_provenance(...)`` / ``SELECT remove_provenance(...)``
  call into the query box;
* clicking a column on a tracked table prefills a
  ``SELECT create_provenance_mapping('<table>_<col>_mapping',
  '<schema>.<table>', '<col>');`` call, so a fresh provenance
  mapping is two clicks away.

.. _circuit-gates:

Inspecting the Circuit
-----------------------

ProvSQL represents provenance as a *circuit*: a directed acyclic graph
(DAG) of *gates*.  Each tuple in a provenance-tracked table is
associated with an ``input`` gate, created lazily the first time that
tuple appears in a query result.  Tuples may also carry more complex
provenance -- for instance, rows created by ``INSERT ... SELECT`` or
``CREATE TABLE AS`` inherit the provenance expression of the source
query.

As queries combine tuples, internal gates record the semiring
operations that were applied:

- ``plus`` (⊕): alternative derivations (``UNION``, ``DISTINCT``)
- ``times`` (⊗): combined use (``JOIN``, cross product)
- ``monus`` (⊖): difference (``EXCEPT``)
- ``delta`` (δ): aggregation boundary (``GROUP BY``)
- ``agg``, ``semimod``: aggregate provenance
- ``project``, ``eq``: where-provenance (column tracking, equijoin)
- ``cmp``: ``HAVING`` comparisons (and the filter-on-RV comparator
  lift, see :doc:`continuous-distributions`)
- ``mulinput``: multivalued input (one alternative of a
  block-independent input; see :doc:`probabilities`)

Two constant gates represent the semiring identity elements:
:sqlfunc:`gate_zero` (additive identity, ``𝟘``) and
:sqlfunc:`gate_one` (multiplicative identity, ``𝟙``).

Additional gate types support scalar values and continuous random
variables (see :doc:`continuous-distributions`):

- ``value``: scalar constant (``HAVING`` provenance and the
  random-variable surface)
- ``rv``: random-variable leaf carrying one of the registered
  distribution families (Normal, Uniform, Exponential, Gamma, Beta…;
  :sqlfunc:`rv_families` lists them all)
- ``arith``: ``N``-ary arithmetic over scalar children
  (``+ - * /``, unary ``-``, min/max, ``pow``/``ln``/``exp``, and the
  ``percentile_cont`` order statistic)
- ``mixture``: Bernoulli or categorical mixture of scalar
  random-variable roots
- ``case``: guarded selection over random variables (``CASE``
  expressions, first-match semantics)
- ``observe``: likelihood-weighting evidence on an observed
  random-variable leaf

Further gate types serve specific features:

- ``update``: data-modification tracking (see
  :doc:`data-modification`)
- ``conditioned``: conditioning marker with children
  ``[target, evidence]`` (see :doc:`conditioning`)
- ``mobius``: signed Möbius combination over child islands, with one
  integer coefficient per child (safe-UCQ probability evaluation)

Two *transparent marker* gates wrap a single child without changing its
value, recording metadata for a later stage (a circuit carrying them
evaluates identically to one without):

- ``assumed``: structural assumption marker whose ``extra`` label names
  the assumption the wrapped sub-circuit was computed under:
  ``'boolean'`` (the default when the label is absent; added by the
  safe-query rewriter and load-time Boolean-identity folding, recording
  that only Boolean semantics are preserved) or ``'absorptive'``
  (cyclic recursion truncated at the absorptive value fixpoint).
  Evaluation under a semiring outside the recorded class refuses with
  an explicit error.
- ``annotation``: carries the inversion-free certificate on a result root,
  or a per-input order key, for the ``'inversion-free'`` probability
  method (see :doc:`probabilities`).

The following functions let you navigate and inspect the circuit:

- :sqlfunc:`get_gate_type` -- returns the type of a gate.
- :sqlfunc:`get_children` -- returns the child tokens of a gate.
- :sqlfunc:`identify_token` -- given a provenance token, returns the
  source table and row it originates from.
- :sqlfunc:`get_infos` -- returns the integer metadata attached to a gate
  (e.g., aggregate function OID, comparison operator OID).
- :sqlfunc:`get_extra` -- returns the text metadata attached to a gate
  (e.g., aggregate value, column positions for where-provenance).
- :sqlfunc:`get_nb_gates` -- returns the total number of gates in the
  circuit, useful for diagnosing circuit size and performance.

.. code-block:: postgresql

    SELECT provsql.get_gate_type(provenance()) FROM mytable;
    SELECT provsql.get_children(provenance()) FROM mytable;
