safe_query_cert.h File Reference

Tractability certificate for the inversion-free UCQ(OBDD) path. More...

#include <stddef.h>

Include dependency graph for safe_query_cert.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	SafeCert
	Query-derived order recipe for the structured-d-DNNF builder. More...
struct	SafeCertKey

Macros
#define	SAFE_CERT_EXTRA_PREFIX_RECIPE   'C'
	Discriminator prefixes for the annotation gate's extra payload.
#define	SAFE_CERT_EXTRA_PREFIX_KEY   'K'
	Input: per-variable order key.
#define	SAFE_CERT_GUARD_FACTOR   (-1) /* factor of a shared self-join guard */
	Per-input order key carried on an input leaf's annotation gate.

Enumerations
enum	SafeCertKind { CERT_NONE = 0 , CERT_INVERSION_FREE = 1 }
	Kind of tractability certificate carried on the provenance root. More...

Functions
char *	safe_cert_serialise (const SafeCert *cert)
	Serialise a SafeCert recipe to a compact, C-prefixed string (palloc'd in the current memory context).
SafeCert *	safe_cert_parse (const char *str)
	Parse a C-prefixed recipe string (as produced by safe_cert_serialise and read back from an annotation gate's extra) into a palloc'd SafeCert.
char *	safe_cert_key_serialise (const char *root, size_t root_len, const char *sec, size_t sec_len, int factor)
	Serialise a per-input order key to a compact K-prefixed string (palloc'd).
bool	safe_cert_key_parse (const char *str, SafeCertKey *out)
	Parse a K-prefixed order-key string into out.

Detailed Description

Tractability certificate for the inversion-free UCQ(OBDD) path.

Shared between the C planner side (src/safe_query.c, which builds the certificate from a query-level analysis) and the C++ evaluation side (src/probability_evaluate.cpp, which reads it back from the annotation gate's extra and routes probability evaluation through the structured-d-DNNF builder).

The planner produces the certificate (the SafeCert "recipe") from the detector and stamps it on the per-row provenance root; the compact serialise / parse helpers below are the annotation-gate carrier the evaluator reads.

Definition in file safe_query_cert.h.

Macro Definition Documentation

SAFE_CERT_EXTRA_PREFIX_KEY

#define SAFE_CERT_EXTRA_PREFIX_KEY   'K'

Input: per-variable order key.

Definition at line 62 of file safe_query_cert.h.

SAFE_CERT_EXTRA_PREFIX_RECIPE

#define SAFE_CERT_EXTRA_PREFIX_RECIPE   'C'

Discriminator prefixes for the annotation gate's extra payload.

One transparent annotation gate type carries both roles, disambiguated by the first byte of extra: a serialised SafeCert recipe on the root, and a per-input order key on each certified input leaf. Root: serialised SafeCert recipe.

Definition at line 61 of file safe_query_cert.h.

SAFE_CERT_GUARD_FACTOR

#define SAFE_CERT_GUARD_FACTOR   (-1) /* factor of a shared self-join guard */

Per-input order key carried on an input leaf's annotation gate.

The structured-d-DNNF builder (StructuredDNNFBuilder) needs, per Boolean variable, its position in the query hierarchy: root the root-class value (one independent block per value), sec the secondary-class value (one tile per value within a block), and factor which quantified factor the atom belongs to, or SAFE_CERT_GUARD_FACTOR for a self-join atom shared by every factor of its tile. This is the wire form of StructuredDNNFBuilder's InputKey.

root and sec are the tuple's column values as text (the canonical output of the column type's I/O function), carried verbatim so the key works for any column type, not just integers. The builder uses them only for grouping (equal text => same block / tile) and a consistent total order, so an exact, type-faithful text rendering is all that is required; root / sec point into the parsed wire string and are not NUL-terminated (use the lengths).

Definition at line 96 of file safe_query_cert.h.

Enumeration Type Documentation

SafeCertKind

enum SafeCertKind

Kind of tractability certificate carried on the provenance root.

Enumerator
CERT_NONE	No certificate.
CERT_INVERSION_FREE	Inversion-free UCQ(OBDD) over TID inputs.

Definition at line 25 of file safe_query_cert.h.

Function Documentation

safe_cert_key_parse()

bool safe_cert_key_parse ( const char * str, SafeCertKey * out )

extern

Parse a K-prefixed order-key string into out.

On success out->root / out->sec point into str (valid for its lifetime). Returns false if str is NULL, not K-prefixed, or malformed (out untouched).

Definition at line 124 of file safe_query_cert.c.

Here is the caller graph for this function:

safe_cert_key_serialise()

char * safe_cert_key_serialise ( const char * root, size_t root_len, const char * sec, size_t sec_len, int factor )

extern

Serialise a per-input order key to a compact K-prefixed string (palloc'd).

Wire form: "K<factor> <root_len>:<root><sec_len>:<sec>" – the byte-length prefixes keep arbitrary value text unambiguous. Inverse of safe_cert_key_parse. (The planner builds the equivalent string per row via inversion_free_key; this C form is for the evaluator and tests.)

Definition at line 111 of file safe_query_cert.c.

safe_cert_parse()

SafeCert * safe_cert_parse ( const char * str )

extern

Parse a C-prefixed recipe string (as produced by safe_cert_serialise and read back from an annotation gate's extra) into a palloc'd SafeCert.

Returns NULL if str is NULL, not C-prefixed, or malformed.

Definition at line 55 of file safe_query_cert.c.

Here is the caller graph for this function:

safe_cert_serialise()

char * safe_cert_serialise ( const SafeCert * cert )

extern

Serialise a SafeCert recipe to a compact, C-prefixed string (palloc'd in the current memory context).

Inverse of safe_cert_parse.

Definition at line 32 of file safe_query_cert.c.

Here is the caller graph for this function: