Querying with Provenance
=========================

Once provenance is enabled on one or more tables, ProvSQL transparently
rewrites every SQL query to propagate and combine provenance annotations.
No changes to query syntax are required.

How It Works
-------------

ProvSQL installs a PostgreSQL *planner hook* (``shared_preload_libraries``
is required for this reason). When a query involves a provenance-enabled
table, the hook intercepts the query plan before execution and:

1. Identifies all relations carrying a ``provsql`` column.
2. Builds a provenance expression that combines the input tokens using the
   appropriate semiring operations (``plus`` for alternative use of
   tuples such as in duplicate elimination,
   ``times`` for combined use of tuples such as in joins, ``monus`` for difference).
3. Appends the resulting provenance token to the output as an extra column.

The final provenance token in each output row is a UUID that represents a
gate in a *provenance circuit* – a DAG recording how that result was derived.

Supported SQL Features
-----------------------

The following SQL constructs are supported with full provenance tracking:

* ``SELECT … FROM … WHERE`` (conjunctive queries, multiset semantics)
* ``JOIN`` (inner joins, outer joins, natural joins)
* ``LATERAL`` subqueries
* Non-recursive CTEs (``WITH`` clauses)
* Recursive CTEs (``WITH RECURSIVE``) using ``UNION`` (set semantics) over
  provenance-tracked relations, on PostgreSQL 15+: the recursive CTE is
  transparently evaluated to a fixpoint and the result carries provenance like
  any other query (e.g. the provenance of s–t reachability is the disjunction
  over the s–t paths).  On **acyclic** data this works for any semiring.  On
  **cyclic** data it requires ``provsql.boolean_provenance`` (an absorptive
  setting, under which the value converges); the resulting circuit is then
  sound only for absorptive evaluation (probability / Boolean), not for
  multiplicity-counting semirings
* Subqueries in the ``FROM`` clause (including deeply nested)
* Subqueries outside ``FROM`` (``EXISTS``/``NOT EXISTS``,
  ``IN``/``NOT IN``, quantified comparisons such as ``= ANY`` or
  ``<> ALL``, scalar subqueries, ``ARRAY(SELECT …)``), correlated or
  not: they are internally decorrelated and rewritten.  The subquery
  body may involve a single provenance-tracked relation, or join
  several of them as a comma-separated ``FROM`` list; e.g., ``NOT IN``
  over a joined body carries the same antijoin provenance as the
  equivalent ``EXCEPT``.  An aggregate body can be compared against a
  constant or an outer column, including through ``IN``/``NOT IN``
  (the single-row aggregate body makes these scalar comparisons)
* ``GROUP BY``
* ``SELECT DISTINCT`` (set semantics)
* ``UNION`` and ``UNION ALL``
* ``EXCEPT`` and ``EXCEPT ALL``
* ``VALUES`` tables (treated as having no provenance)
* Aggregation (``SUM``, ``COUNT``, ``MIN``, ``MAX``, ``AVG``,
  ``COUNT(DISTINCT …)``, ``string_agg``, ``array_agg``)
* ``HAVING`` (non-matching groups receive zero provenance ``𝟘``
  rather than being filtered out)
* ``FILTER`` clause on aggregates
* ``INSERT … SELECT`` (provenance propagated when target table is
  provenance-tracked)

Unsupported SQL Features
-------------------------

The following constructs are **not** currently supported; queries using them
will either raise an error or may cause incorrect provenance tracking:

* **Subqueries outside FROM** whose body uses explicit ``JOIN``
  syntax (rewrite the body as a comma-separated ``FROM`` list with the
  join condition in ``WHERE``) or ``LIMIT``/``OFFSET`` (it would pick
  an order-dependent subset); also, when an *uncorrelated* body with
  no ``WHERE`` clause is compared against an outer column, only
  non-star aggregate bodies are supported (``max(x)``, ``count(x)``,
  …, including via ``IN``/``NOT IN``) -- a plain value body or
  ``count(*)`` in that position is not
* **Recursive CTEs** (``WITH RECURSIVE``) using ``UNION ALL`` (bag
  semantics), over cyclic data *without* ``provsql.boolean_provenance``, or on
  PostgreSQL versions before 15
* ``INTERSECT``
* ``DISTINCT ON``
* ``GROUPING SETS``, ``CUBE``, ``ROLLUP``
* **Operations on aggregate results requiring comparison or duplicate
  elimination:** ``DISTINCT`` on aggregates, ``UNION``/``EXCEPT``
  (non-ALL) with aggregates, ``ORDER BY`` or ``GROUP BY`` on aggregate
  results from a subquery
* `Window functions <https://www.postgresql.org/docs/current/tutorial-window.html>`_
  (``ROW_NUMBER``, ``RANK``, ``SUM`` ``OVER``, ``LAG``, ``LEAD``, etc.):
  the query still executes and each output row carries the tuple
  provenance of its single input row, but the windowed computation
  itself has no aggregate-provenance semantics (``SUM(x) OVER (…)`` is an
  opaque scalar, not an aggregation over the frame). A ``WARNING`` is
  emitted whenever a window function appears in a provenance-tracked
  query

For unsupported correlated subqueries, ``LATERAL`` can be used as a
workaround.
For comparison or duplicate elimination on aggregate results, explicitly
cast the aggregate column to its base type (e.g., ``cnt::bigint``),
which extracts the value but loses the provenance information on that
column.

Provenance in Nested Queries
-----------------------------

Subqueries in the ``FROM`` clause are supported. Each sub-result carries its
own provenance, which is further combined by the outer query:

.. code-block:: sql

    SELECT t.name, provenance()
    FROM (
        SELECT name FROM employees WHERE dept = 'R&D'
    ) t;

``CREATE TABLE … AS SELECT``
-----------------------------

You can materialise a provenance-tracked query result into a new table.
The new table automatically inherits provenance from its source:

.. code-block:: sql

    CREATE TABLE derived AS
    SELECT name, dept FROM employees WHERE active;

``INSERT … SELECT``
---------------------

When both the source and target tables are provenance-tracked,
``INSERT … SELECT`` propagates provenance from the source query to the
inserted rows:

.. code-block:: sql

    CREATE TABLE archive (name VARCHAR, city VARCHAR);
    SELECT add_provenance('archive');
    INSERT INTO archive SELECT name, city FROM employees WHERE dept = 'R&D';

Each inserted row receives the provenance token computed by the source
``SELECT``, rather than a fresh independent token.

If the target table does not have a ``provsql`` column, a warning is
emitted indicating that source provenance is lost.

The ``provenance()`` Function
------------------------------

In a ``SELECT`` list, ``provenance()`` returns the provenance UUID of the
current output tuple:

.. code-block:: sql

    SELECT name, provenance() FROM mytable;

The token can be passed to semiring evaluation functions
(see :doc:`semirings`) or to probability/Shapley functions.
