GRANT and REVOKE permissions in PostgreSQL - Time & Space Complexity

Time Complexity: GRANT and REVOKE permissions

O(n * m)

Understanding Time Complexity

When we give or take away permissions in a database, it takes some time to process. We want to understand how this time changes when we have more users or more permissions.

How does the time to grant or revoke permissions grow as the number of users or permissions increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GRANT SELECT, INSERT ON employees TO user1;
REVOKE INSERT ON employees FROM user1;
GRANT UPDATE ON employees TO user2;
REVOKE ALL ON employees FROM user3;
-- Grant or revoke permissions for multiple users
GRANT SELECT ON employees TO user1, user2, user3;

This code gives or removes permissions on the "employees" table for different users.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Applying permission changes for each user and each permission.
• How many times: Once per user-permission pair in the command.

How Execution Grows With Input

When you add more users or more permissions in one command, the work grows because the database must update each user's permissions separately.

Input Size (n users x m permissions)	Approx. Operations
10 users x 2 permissions	20 permission changes
100 users x 3 permissions	300 permission changes
1000 users x 5 permissions	5000 permission changes

Pattern observation: The total work grows roughly by multiplying the number of users by the number of permissions.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to grant or revoke permissions grows in proportion to the number of users times the number of permissions involved.

Common Mistake

[X] Wrong: "Granting permissions to many users at once takes the same time as granting to one user."

[OK] Correct: The database must update each user's permissions separately, so more users mean more work and more time.

Interview Connect

Understanding how permission changes scale helps you design systems that manage access efficiently and avoid slowdowns when many users are involved.

Self-Check

"What if we grant permissions to a role instead of individual users? How would the time complexity change?"

Practice

1. What does the GRANT command do in PostgreSQL?

easy

A. It gives specific permissions to a user or role.

B. It deletes a user from the database.

C. It creates a new database.

D. It backs up the database.

Solution

1. Step 1: Understand the purpose of GRANT

   The GRANT command is used to give permissions like SELECT, INSERT, or UPDATE to users or roles.

2. Step 2: Compare with other options

   Deleting users, creating databases, or backing up are done by other commands, not GRANT.

3. Final Answer:

   It gives specific permissions to a user or role. -> Option A

4. Quick Check:

   GRANT = give permissions [OK]

Hint: GRANT means give rights; REVOKE means take away [OK]

Common Mistakes:

• Confusing GRANT with user creation
• Thinking GRANT deletes data
• Mixing GRANT with backup commands

2. Which of the following is the correct syntax to grant SELECT permission on table employees to user john?

easy

A. GRANT ON employees SELECT TO john;

B. GRANT john ON employees SELECT;

C. GRANT SELECT TO john ON employees;

D. GRANT SELECT ON employees TO john;

Solution

1. Step 1: Recall correct GRANT syntax

   The correct syntax is: GRANT permission ON object TO user;

2. Step 2: Match syntax with options

   GRANT SELECT ON employees TO john; matches the correct order: GRANT SELECT ON employees TO john;

3. Final Answer:

   GRANT SELECT ON employees TO john; -> Option D

4. Quick Check:

   GRANT + permission + ON + object + TO + user [OK]

Hint: GRANT permission ON object TO user; is the pattern [OK]

Common Mistakes:

• Mixing order of keywords
• Placing user before permission
• Omitting ON keyword

3. Given the commands:
GRANT SELECT ON customers TO alice;
REVOKE SELECT ON customers FROM alice;
What permissions does user alice have on table customers after these commands?

medium

A. Alice can SELECT from customers.

B. Alice can INSERT into customers.

C. Alice cannot SELECT from customers.

D. Alice has all permissions on customers.

Solution

1. Step 1: Analyze the GRANT command

   Alice is given SELECT permission on customers table.

2. Step 2: Analyze the REVOKE command

   The SELECT permission is then revoked from Alice, removing her ability to SELECT.

3. Final Answer:

   Alice cannot SELECT from customers. -> Option C

4. Quick Check:

   REVOKE removes permission given by GRANT [OK]

Hint: REVOKE removes permissions previously granted [OK]

Common Mistakes:

• Assuming REVOKE adds permissions
• Confusing SELECT with INSERT
• Ignoring the order of commands

4. Identify the error in the following command:
REVOKE ALL PRIVILEGES employees FROM bob;

medium

A. The order of keywords is incorrect.

B. The user name should be before the table name.

C. REVOKE cannot be used with ALL PRIVILEGES.

D. The command is correct.

Solution

1. Step 1: Check correct REVOKE syntax

   The correct syntax is: REVOKE privileges ON object FROM user;

2. Step 2: Compare with given command

   The command uses: REVOKE ALL PRIVILEGES employees FROM bob; missing ON keyword and wrong order.

3. Final Answer:

   The order of keywords is incorrect. -> Option A

4. Quick Check:

   REVOKE + privileges + ON + object + FROM + user [OK]

Hint: REVOKE syntax requires ON before object [OK]

Common Mistakes:

• Omitting ON keyword
• Swapping user and object positions
• Using ALL PRIVILEGES incorrectly

5. You want to allow user carol to insert and update data on table orders, but not delete. Which commands correctly grant these permissions?

hard

A. GRANT DELETE ON orders TO carol;

B. GRANT INSERT, UPDATE ON orders TO carol;

C. GRANT ALL PRIVILEGES ON orders TO carol;

D. GRANT SELECT, DELETE ON orders TO carol;

Solution

1. Step 1: Identify required permissions

   Carol needs INSERT and UPDATE permissions only, no DELETE.

2. Step 2: Match commands with required permissions

   GRANT INSERT, UPDATE ON orders TO carol; grants INSERT and UPDATE correctly. Options B and D grant DELETE, which is not wanted. GRANT ALL PRIVILEGES ON orders TO carol; grants all permissions, including DELETE.

3. Final Answer:

   GRANT INSERT, UPDATE ON orders TO carol; -> Option B

4. Quick Check:

   Grant only needed permissions, avoid ALL PRIVILEGES if not required [OK]

Hint: Grant only needed permissions, avoid ALL PRIVILEGES if unsure [OK]

Common Mistakes:

• Granting DELETE when not needed
• Using ALL PRIVILEGES carelessly
• Confusing SELECT with UPDATE