SQLite3

SQLite is a self-contained, public-domain, SQL database engine.

SQLite3 is built calling ./configure && make. We built and benchmarked the versions

For SQLite3 we can measure the resource usage using /usr/bin/time. Using the command .timer on, resource usage can be measured for the distinct SQL commands.

tcff

To improve performance, we used a temporary in-memory table for the par relation. We added PRAGMA temp\_store = MEMORY; in order to deactivate using temporary files.

-- tcff.sql.tbl
PRAGMA temp_store = MEMORY;
CREATE TEMP TABLE par (
  a INT NOT NULL,
  b INT NOT NULL,
  CONSTRAINT par_pk PRIMARY KEY (a, b)
) WITHOUT ROWID;

CREATE INDEX par_fb ON par (b);

.mode csv
.import INSTANCE par
-- tcff.sql
WITH RECURSIVE tc(a,b) AS (
    SELECT par.a, par.b from par
    UNION
    SELECT par.a, tc.b from par JOIN tc ON par.b = tc.a
) SELECT Count(*) FROM tc;

Launch: (sed \'s!INSTANCE!{instance}!g\' tcff.sql.tbl ; cat tcff.sql ) | sqlite

sgff

We're using the same table definitions as for the transitive closure.

-- sgff.sql
WITH RECURSIVE sg(a,b) AS (
    SELECT par.b, par.b from par
    UNION
    SELECT p1.a, p2.a from sg JOIN par p1 ON p1.b = sg.a JOIN par p2 ON p2.b = sg.b
) SELECT Count(*) FROM sg;