Schema-level access control in PostgreSQL - Time & Space Complexity

Time Complexity: Schema-level access control

O(log n)

Understanding Time Complexity

We want to understand how the time to check permissions grows when controlling access to database schemas.

How does the system handle more users or schemas when deciding who can do what?

Scenario Under Consideration

Analyze the time complexity of this schema-level access control check.

-- Check if user has USAGE privilege on a schema
SELECT has_schema_privilege('username', 'schema_name', 'USAGE');

-- Grant USAGE privilege on schema to a user
GRANT USAGE ON SCHEMA schema_name TO username;

-- Revoke USAGE privilege on schema from a user
REVOKE USAGE ON SCHEMA schema_name FROM username;
    

This code checks and manages user permissions on a schema in PostgreSQL.

Identify Repeating Operations

Look for repeated checks or scans when verifying access.

• Primary operation: Checking user privileges involves looking up entries in system tables that store permissions.
• How many times: Once per access check, but can happen many times if many users or schemas exist.

How Execution Grows With Input

As the number of users or schemas grows, the system must search through more privilege entries.

Input Size (n)	Approx. Operations
10 users/schemas	Few lookups, very fast
100 users/schemas	More lookups, still quick due to indexing
1000 users/schemas	More entries to check, but indexes keep it efficient

Pattern observation: The time grows slowly because the database uses indexes to find privileges quickly.

Final Time Complexity

Time Complexity: O(log n)

This means checking schema privileges takes time that grows slowly as the number of users or schemas increases, thanks to indexing.

Common Mistake

[X] Wrong: "Checking schema privileges takes the same time no matter how many users or schemas exist."

[OK] Correct: The system must search through privilege data, so more users or schemas mean more data to check, but indexes help keep it efficient.

Interview Connect

Understanding how access control scales helps you explain how databases keep data safe without slowing down as they grow.

Self-Check

"What if we added caching for privilege checks? How would the time complexity change?"

Practice

1. What does the USAGE privilege on a schema in PostgreSQL allow a user to do?

easy

A. Access objects within the schema without creating new ones

B. Create new tables and objects inside the schema

C. Delete the schema entirely

D. Modify data in tables outside the schema

Solution

1. Step 1: Understand USAGE privilege meaning

   The USAGE privilege allows a user to access objects inside the schema, such as selecting data from tables, but does not allow creating new objects.

2. Step 2: Differentiate from CREATE privilege

   The CREATE privilege is needed to add new tables or other objects. USAGE alone does not grant this ability.

3. Final Answer:

   Access objects within the schema without creating new ones -> Option A

4. Quick Check:

   USAGE = access only [OK]

Hint: USAGE lets you use, CREATE lets you add [OK]

Common Mistakes:

• Confusing USAGE with CREATE privilege
• Thinking USAGE allows schema deletion
• Assuming USAGE grants data modification outside schema

2. Which of the following is the correct syntax to grant CREATE privilege on a schema named sales to user alice?

easy

A. GRANT CREATE ON sales TO alice;

B. GRANT CREATE TO alice ON SCHEMA sales;

C. GRANT CREATE ON SCHEMA sales TO alice;

D. GRANT CREATE ON DATABASE sales TO alice;

Solution

1. Step 1: Identify correct GRANT syntax for schema

   In PostgreSQL, to grant privileges on a schema, the syntax is: GRANT privilege ON SCHEMA schema_name TO user;

2. Step 2: Match syntax with options

   GRANT CREATE ON SCHEMA sales TO alice; matches this syntax exactly: GRANT CREATE ON SCHEMA sales TO alice;

3. Final Answer:

   GRANT CREATE ON SCHEMA sales TO alice; -> Option C

4. Quick Check:

   GRANT ... ON SCHEMA ... TO ... [OK]

Hint: Use 'ON SCHEMA' when granting schema privileges [OK]

Common Mistakes:

• Omitting 'SCHEMA' keyword
• Using 'ON DATABASE' instead of 'ON SCHEMA'
• Placing TO clause incorrectly

3. Given the commands below, what will be the result of SELECT * FROM sales.orders; when run by user bob?

GRANT USAGE ON SCHEMA sales TO bob;
REVOKE CREATE ON SCHEMA sales FROM bob;

medium

A. Query runs but returns no rows

B. Error: permission denied for schema sales

C. Error: relation sales.orders does not exist

D. Query runs successfully and returns rows from sales.orders

Solution

1. Step 1: Analyze granted privileges

   User bob has USAGE on schema sales, so can access objects inside it. CREATE privilege is revoked, so bob cannot create new objects but can read existing ones.

2. Step 2: Understand effect on SELECT query

   Since bob has USAGE, SELECT on sales.orders will work if bob has SELECT privilege on the table (assumed). The REVOKE of CREATE does not affect SELECT.

3. Final Answer:

   Query runs successfully and returns rows from sales.orders -> Option D

4. Quick Check:

   USAGE allows access, REVOKE CREATE blocks creation only [OK]

Hint: USAGE lets you read; CREATE controls adding objects [OK]

Common Mistakes:

• Confusing CREATE with SELECT privilege
• Assuming REVOKE CREATE blocks all access
• Ignoring USAGE privilege effect

4. You want to allow user carol to create tables in schema inventory, but she gets an error: permission denied for schema inventory. Which command fixes this?

medium

A. GRANT CREATE ON SCHEMA inventory TO carol;

B. GRANT USAGE ON SCHEMA inventory TO carol;

C. GRANT ALL PRIVILEGES ON SCHEMA inventory TO carol;

D. REVOKE USAGE ON SCHEMA inventory FROM carol;

Solution

1. Step 1: Understand error cause

   To create tables, user needs both USAGE and CREATE privileges on the schema. Without USAGE, permission denied error occurs.

2. Step 2: Grant missing privilege

   Granting USAGE on schema inventory to carol allows her to access the schema and create tables if CREATE is already granted.

3. Final Answer:

   GRANT USAGE ON SCHEMA inventory TO carol; -> Option B

4. Quick Check:

   USAGE needed before CREATE works [OK]

Hint: Grant USAGE before CREATE to avoid permission errors [OK]

Common Mistakes:

• Granting CREATE without USAGE privilege
• Revoking instead of granting privileges
• Assuming ALL PRIVILEGES always needed

5. You want to restrict user dave so he can only create objects in schema projects but cannot access any existing objects. Which combination of privileges achieves this?

hard

A. GRANT CREATE ON SCHEMA projects TO dave; REVOKE USAGE ON SCHEMA projects FROM dave;

B. GRANT USAGE ON SCHEMA projects TO dave; REVOKE CREATE ON SCHEMA projects FROM dave;

C. GRANT ALL ON SCHEMA projects TO dave;

D. REVOKE ALL ON SCHEMA projects FROM dave;

Solution

1. Step 1: Understand privilege effects

   CREATE allows adding new objects. USAGE allows accessing existing objects. To restrict access but allow creation, grant CREATE and revoke USAGE.

2. Step 2: Apply correct commands

   GRANT CREATE ON SCHEMA projects TO dave; REVOKE USAGE ON SCHEMA projects FROM dave; grants CREATE and revokes USAGE, so dave can create but not access existing objects.

3. Final Answer:

   GRANT CREATE ON SCHEMA projects TO dave; REVOKE USAGE ON SCHEMA projects FROM dave; -> Option A

4. Quick Check:

   Create without usage blocks access [OK]

Hint: Grant CREATE, revoke USAGE to allow creation only [OK]

Common Mistakes:

• Granting USAGE allows access to existing objects
• Revoking CREATE disables creation
• Granting ALL gives too many rights