Postgres ON DELETE Rule Not Working With WHERE Clause I'm trying to implement "Soft Deletes" given the following schema:

CREATE TABLE categories(
  id serial not null primary key,
  num integer,
  "name" text,
  deleted_at timestamp default null
);

CREATE OR REPLACE RULE delete_categories AS
  ON DELETE TO categories
  WHERE old.deleted_at IS NULL
  DO INSTEAD
    UPDATE categories SET deleted_at = NOW()
    WHERE categories.id = old.id;


The expected behavior is that if I try to delete a record with a NULL deleted_at value, it will instead be set to the current timestamp.  If I try to delete a record with a non-NULL deleted_at value, it will be deleted normally.

Instead, running the below sequence returns no records, instead of a record with a timestamp in the deleted_at column:

insert into categories(num,name,deleted_at) values(9999,'Test Category',null);
delete from categories;
select * from categories;


It appears as though the RULE does not get triggered at all, and the record is simply deleted, whereas if I modify the RULE by commenting out the WHERE clause, the record is updated as expected but I am barred from being able to delete it fully:

CREATE OR REPLACE RULE delete_categories AS
  ON DELETE TO categories
  -- WHERE old.deleted_at IS NULL
  DO INSTEAD
    UPDATE categories SET deleted_at = NOW()
    WHERE categories.id = old.id;

insert into categories(num,name,deleted_at) values(9999,'Test Category',null);
delete from categories;
select * from categories;


Results:

+----+------+---------------+----------------------------+
| id | num  |     name      |         deleted_at         |
+----+------+---------------+----------------------------+
|  3 | 9999 | Test Category | 2015-03-03 20:05:44.660208 |
+----+------+---------------+----------------------------+
The manual in Rules on INSERT, UPDATE, and DELETE) describes the INSTEAD mechanism for the context of your rule as:


  Qualification given and INSTEAD
  
  the query tree from the rule action with the rule qualification an
  the original query tree's qualification; and the original query
  tree with the negated rule qualification added


Overlooking the part emphasized above would be the cause of the unexpected result.
I believe that in your test case, the mentioned DELETE will be transformed by the rule into commands to the same effect as:

UPDATE categories SET deleted_at = NOW()
    WHERE categories.id = categories.id AND deleted_at IS NULL;

DELETE from categories WHERE NOT old.deleted_at IS NULL;


The DELETE removes the row because the UPDATE before it has just set its deleted_at field to non-null.

Note also the categories.id = categories.id condition which is obviously not needed and comes from the misunderstanding that OLD does not reference a specific row like in a trigger, it's meant to be replaced by the table subject to the rule. 

The main point to understand is that rules don't look themselves at the rows and so they don't generate a kind of IF-THEN-ELSE construct depending on the row contents. The WHERE clauses of the RULES (the qualifications) are not evaluated by the rule system, they are injected into the commands produced by the rule system and will be evaluated by the commands themselves.

See also What are PostgreSQL RULEs good for? and links within for some interesting insights on rules and why they're hard to use.