I'm pretty sure that "ALTER TABLE ... ADD COLUMN ... NULL;" holds an AccessExclusiveLock on the relation being altered for the duration of the transaction in PG 9.1 and 9.2. Is there some trick to the zero downtime schema changes that are mentioned in this slide deck? I only ask because I recently had to get creative with zero downtime schema migrations for my current project.