Representing ownership of heirarchical tree structure
I've thought of several possible solutions, but they all leave something to be desired. For example, I could add an owner_id column to the folders table, referencing users (id). The negative is that the owner would have to be repeated on every row, and ensuring that the entire tree has the same owner would be... difficult. (Maybe a foreign key on (parent_id, owner_id)? That seems... a bit gross.)


That's not true. PostgreSQL provides for CHECK constraints which make this really easy.

CREATE TABLE users (
    id   serial PRIMARY KEY,
    name text   NOT NULL
);

CREATE TABLE folders (
    id        serial PRIMARY KEY,
    parent_id int    REFERENCES folders,
    owner_id  int,
    name      text   NOT NULL,
    CHECK (
      (parent_id IS NULL AND owner_id IS NOT NULL)
      OR (parent_id IS NOT NULL AND owner_id IS NULL)
    )
);

INSERT INTO users(id,name) VALUES
  (1, 'Evan Carroll');

INSERT INTO folders(id,parent_id,owner_id,name) VALUES
  (1, null, null, '/usr');
ERROR:  new row for relation "folders" violates check constraint "folders_check"
DETAIL:  Failing row contains (1, null, null, /usr).

INSERT INTO folders(id,parent_id,owner_id,name) VALUES
  (1, null, 1, '/usr');
INSERT 0 1

INSERT INTO folders(id,parent_id,owner_id,name) VALUES
  (2, 1, null, '/usr');
INSERT 0 1


As for the space concern, that's hardly something I would worry about. It's 4 bytes on a row. Joining for that and establishing a 1:1 relationship sounds utterly silly.