pg_gaps

This Release
pg_gaps 0.1.0
Date
Status
Stable
Abstract
Probabilistic graphical models over incomplete relations
Description
pg_gaps brings BayesStore (Wang, Michelakis, Garofalakis and Hellerstein, VLDB 2008) to ordinary PostgreSQL tables. Columns may be missing values; a first-order Bayesian network stored in the gaps schema says how those values are distributed and correlated, and functions return the posterior distribution of every missing value, the most likely completion of each row, and maximum-likelihood CPTs learned from the data. Inference is exact (variable elimination over a bucket tree, cross-checked against brute force and pgmpy), with opt-in Gibbs sampling for components too large to solve exactly.
Released By
gregburd
License
PostgreSQL
Resources
Special Files
Tags

Extensions

pg_gaps 0.1.0
Bayesian-network inference over tables with missing values

Documentation

ROADMAP
pg_gaps roadmap
CHANGELOG
Changelog
DESIGN
pg_gaps design
CONTRIBUTING
Contributing to pg_gaps

README

pg_gaps

Probabilistic graphical models over incomplete relations, for PostgreSQL.

pg_gaps brings the ideas of BayesStore (Wang, Michelakis, Garofalakis and Hellerstein, VLDB 2008) to ordinary PostgreSQL tables. Some columns of a table may be missing values. A separately stored first-order Bayesian network says how those values are distributed and how they correlate, with each other and with the values that are present. Queries return the distribution of each missing value, or the most likely completion of each row, computed by exact inference conditioned on the data you have.

Status: 0.1.0, the first release. The model catalog, exact inference, learning (counts with Dirichlet priors, and EM), restricted queries, parameterised and composite models are built and tested. Probabilistic selection, projection and joins (select_rows and friends) are not yet; ROADMAP.md lists what is next and doc/DESIGN.md describes the data model and how it maps onto PostgreSQL.

Requirements

PostgreSQL 17, 18 or 19, a C compiler, and the server headers.

Build and install

From PGXN:

pgxn install pg_gaps

From a source tree or a release zip:

make PG_CONFIG=/path/to/pg_config
sudo make install PG_CONFIG=/path/to/pg_config
CREATE EXTENSION pg_gaps;   -- installs into schema "gaps"; needs a superuser

A first model

A survey where some people did not answer “smoker” or “cough”, and smoking makes coughing more likely:

CREATE TABLE survey (id int PRIMARY KEY, smoker text, cough text);
-- ... rows, some with NULLs ...

SELECT gaps.create_model('health');
SELECT gaps.declare_attribute('health', 'survey', 'smoker', ARRAY['no', 'yes']);
SELECT gaps.declare_attribute('health', 'survey', 'cough',  ARRAY['no', 'yes']);
SELECT gaps.add_stripe('health', 's', 'survey', 'smoker');
SELECT gaps.add_stripe('health', 'c', 'survey', 'cough');
SELECT gaps.add_factor('health', 'p_smoker', 's');                 -- P(smoker)
SELECT gaps.add_factor('health', 'p_cough',  'c', ARRAY['s']);     -- P(cough | smoker)

SELECT * FROM gaps.learn_cpts('health');          -- from the data
SELECT * FROM gaps.marginals('health');           -- every missing value's distribution
SELECT * FROM gaps.impute('health');              -- the most likely completion

A row that coughs and did not say whether it smokes comes back more likely a smoker than the base rate, and one that does not cough less likely; every distribution sums to 1 and says which method computed it.

What else is there:

  • Correlated rows. A factor’s parent may be another row’s value (sensor 2 depends on sensor 1 at the same time and room), through gaps.map_factor; inference solves each connected group of rows exactly.
  • Learning. learn_cpts(model, alpha) takes the posterior mean under a symmetric Dirichlet(alpha), or per-cell pseudocounts set with gaps.set_prior; method => 'em' also learns from rows with missing values.
  • Some entities only. gaps.marginals(model, rel, entities) grounds only the components that hold the given entities, with the same answers as the whole-model call.
  • Views, binned numbers, weighted factors. A model may sit over a view; declare_attribute(..., edges => ...) bins a numeric column; add_factor(..., kind => 'logistic' | 'noisy_or', params => ...) computes a CPT from weights, and an aggregating parent takes any number of rows (all of a person’s e-mails).
  • Several networks as one. gaps.add_member builds a composite model whose members are grounded and solved together, so combining them never multiplies dependent probabilities in SQL.
  • Checks. gaps.validate(model) proves a model acyclic from its declaration alone; gaps.cpt_rows(model, factor) shows a CPT as rows.

Limits worth knowing

  • Domains are discrete and finite; bin continuous values.
  • Exact inference is bounded by gaps.max_factor_cells and gaps.max_total_cells; a model past them is an error, not a hang. Setting gaps.samples lets a too-large component be sampled (Gibbs, four chains, refused when they disagree). Sampling is experimental: chains that all settle in the same wrong mode give a wrong answer without an error; see doc/DESIGN.md.
  • Do not join two marginals results and multiply: that assumes the values are independent, which the model does not. Ask for one call.
  • marginals and friends create temporary tables, so they do not run on a hot standby.
  • Functions whose names start with an underscore are internal and may change between releases.

Testing

make installcheck runs the regression suite. With Nix, nix flake check builds and tests against all three majors, plus the standalone engine tests and the pgmpy cross-check; see CONTRIBUTING.md.

License

PostgreSQL License; see LICENSE.