Schema for allowing adding tags to entities in unrelated tables

Question

I'm implementing a "tags" features to an already working solution.

Final users need to be able to add tags to three separate sections of the solution:

• Posts
• Accounts
• Groups

Each section has its corresponding table in the database, and each table contains a unique ID:

• PostID
• AccountID
• GroupID

I'm thinking about implementing a tag schema similar to the one that Wordpress uses, where I'll have:

• A tagmap table that will contain a unique ID for each "tagmap".
• A foreign key to each section's table ID.
• Another foreign key to the ID of the tag.

CREATE TABLE Posts(
  PostID int(2) NOT NULL AUTO_INCREMENT,
  Content varchar(255),
  PRIMARY KEY(PostID)
 );

CREATE TABLE Groups(
  GroupID int(2) NOT NULL AUTO_INCREMENT,
  GroupName varchar(255),
  PRIMARY KEY(GroupID)
 );

CREATE TABLE Links(
  LinkID int(2) NOT NULL AUTO_INCREMENT,
  href varchar(255),
  PRIMARY KEY(LinkID)
 );

CREATE TABLE tagmap(
  TagmapID int(2) NOT NULL AUTO_INCREMENT,
  PostID int(2),
  GroupID int(2),
  LinkID int(2),
  TagID int(2) NOT NULL,
  PRIMARY KEY(TagmapID)
 );

CREATE TABLE tags(
  TagID int(2) NOT NULL AUTO_INCREMENT,
  TagName varchar(255) NOT NULL,
  PRIMARY KEY(TagID)
);

I like this approach because it is decently normalized, but queries might get a bit complex. Also, it will have a lot of NULL columns every time a tag is assigned to a post but not to an account or to a group, so I'm unsure how it will behave performance-wise (the table will hold around 100,000 records almost immediately).

Is there a better alternative to this?

Answer 1

While this may seem "decently normalized", it's not. As you said yourself, there will be a lot of (redundant) NULL values, but also, relationships will not be enforced correctly, as this schema allows for duplicate tagmap records for any combination of Post/Group/Link and Tag. For instance, you could have two tagmap records with the same TagID and PostID.

Now, while you could add a compound key consisting of PostID, GroupID, LinkID, and TagID, then you have another problem: a single record can contain more than one (non-tag) Post/Group/Link relation. e.g. a tagmap record with TagID= 1, PostID= 1, AND GroupID= 1. This can lead to update anomalies. See Second normal form.

A normalized solution would be to have three separate tag-relation tables as abuzittin gillifirca suggested: tag_post, tag_group, and tag_link. Doing so will eliminate all the redundant NULL values and allow you to enforce relations correctly.

Having said that, I'm guessing you came up with this design, because you want to use a single query to fetch all entities assigned to one or more tags. You can still do this with multiple tag-relation tables like so:

SELECT everything.Type, everything.Id, everything.Content
FROM (
    SELECT 'post' as Type, PostID as Id, Content 
    FROM Posts 
    JOIN TagPosts ON TagPosts.PostID = Posts.PostID 
    WHERE TagPosts.TagID = ?

    UNION ALL

    SELECT 'group' as Type, GroupID as Id, GroupName as Content 
    FROM Groups 
    JOIN TagGroups ON TagGroups.GroupID = Groups.GroupID 
    WHERE TagGroups.TagID = ?

    UNION ALL

    SELECT 'link' as Type, LinkID as Id, href as Content 
    FROM Links 
    JOIN TagLinks ON TagLinks.LinkID = Links.LinkID 
    WHERE TagLinks.TagID = ?
) AS everything;

This would return records like:

"post",  1, "Some content of a post"
"post",  2, "Content for another post"
"group", 1, "Group name"
"link",  1, "http://johntron.com"

Answer 2

A simple solution is to include a table reference in the tagmap instead of many id columns.

CREATE TABLE tagmap(
  TagmapID int(2) NOT NULL AUTO_INCREMENT,
  RefTable varchar(255) NOT NULL,
  RefID int(2),
  TagID int(2) NOT NULL,
  PRIMARY KEY(TagmapID),
  INDEX(RefTable, RefID),
  UNIQUE(RefTable, RefID, TagID)
);

With that approach, you can easily make other tables taggable. To retrieve the tags for a post, you'd just say

SELECT TagName FROM tags
LEFT JOIN tagmap USING TagID
WHERE RefTable = 'posts' AND RefID = 42

Answer 3

As @abuzittingillifirca said, this isn't very normalized. Summarizing my own opinion and what I've generally gathered from the net, you'll want to normalize it completely, test it with real data, then optimize the heck out of your configuration and queries before thinking about denormalization. With proper optimization, in my experience you should be able to get to millions of rows before queries start being less than humanly instantaneous.

Also, have you studied other tagging solutions and their requirements? There's probably a lot of stuff that's already been figured out...