One of the system design interview questions I got many years ago was to design an ID (RFID) card access system. I don't remember how I answered the question back then but I attempted a solution yesterday, and was hoping to get some insights and improvements. (Please let me know if this actually belongs in Code Review or Programmers.)
In one sentence: I thought there should be a 1:1 mapping between an ID card and person, that a person can belong to a group ("Engineers"), that groups can belong to groups ("Employees"), that an access point itself ("West Elevator 04") can belong to access point groups ("West Elevator Bank"), and finally, that access is granted via mappings between person groups and access point groups.
To simplify things down the line, I thought 2 additional things. I would make access points and access groups the same thing, calling them access entities, which can be nested arbitrarily. And I would disallow specific persons being mapped to access entities, i.e. require a descriptive group even if granting access to a single individual.
So here's my database design.
CREATE TABLE card ( id INT NOT NULL AUTO_INCREMENT, PRIMARY KEY (id) ); CREATE TABLE person ( id INT NOT NULL AUTO_INCREMENT, name CHAR(100) NOT NULL, ... PRIMARY KEY (id) ); CREATE TABLE group ( id INT NOT NULL AUTO_INCREMENT, name CHAR(100) NOT NULL, ... PRIMARY KEY (id) ); CREATE TABLE card_person_mapping ( card_id INT, person_id INT, ... PRIMARY KEY (card_id), FOREIGN KEY (card_id) REFERENCES card(id), FOREIGN KEY (person_id) REFERENCES person(id) ); CREATE TABLE person_group_mapping ( person_id INT, group_id INT, PRIMARY KEY (person_id, group_id), FOREIGN KEY (person_id) REFERENCES person(id), FOREIGN KEY (group_id) REFERENCES group(id) ); CREATE TABLE group_group_mapping ( group_id INT, parent_group_id INT, PRIMARY KEY (group_id, parent_group_id) FOREIGN KEY (group_id, parent_group_id) REFERENCES group(id, id) ); CREATE TABLE access_entity ( id INT NOT NULL AUTO_INCREMENT, name CHAR(100) NOT NULL, ... PRIMARY KEY (id) ); CREATE TABLE access_entity_mapping ( ae_id INT, parent_ae_id INT, PRIMARY KEY (ae_id, parent_ae_id) FOREIGN KEY (ae_id, parent_ae_id) REFERENCES access_entity(id, id) ); CREATE TABLE group_access_entity_mapping ( group_id INT, ae_id INT, PRIMARY KEY (group_id, ae_id), FOREIGN KEY (group_id) REFERENCES group(id), FOREIGN KEY (ae_id) REFERENCES access_entity(id)
The "algorithm" for determining access then would be:
- Person swipes ID card at access entity.
- Gather all parent access entities by walking up the hierarchy.
- Look up person_id by card_id.
- Gather all of this person's groups by walking up the hierarchy.
- Do any of the person's groups have a mapping to any of the access entities? If yes, granted. If not, denied.
Some initial questions I have are:
- Is mapping from child entity to parent entity going to make implementing an administrative frontend difficult? Or do I just need to add appropriate indexes.
- Would it be fair to say that performance isn't a high priority in this application? A company wouldn't have more than say, 1 million employees. And if a million employees were to scan their card every 10 minutes, that would still only be in the order of 100 QPS.
- If the above is true then denormalization wouldn't be necessary. But for the sake of the exercise, what would be the most effective denormalization for this scenario? (Or, a totally different table design.)
I also welcome comments on naming and formatting conventions. Thank you.