Will this (normalised) database structure permit me to search by tags as I intend?

Question

I am trying to set up a normalised MySQL database containing the three following tables. The first table contains a list of items which can be described by various tags. The third table contains the various tags used to describe the items in the first table. The middle table relates the other two tables to each other. In each table's case, the id is an auto-incrementing primary key (and each is used as the foreign key in the middle table)

+---------------+---------------------+---------------+
|   Table 1     |      Table 2        |   Table 3     |
+---------------+---------------------+---------------+
|id        item |id   item_id   tag_id|id          tag|
+---------------+---------------------+---------------+
| 1      spaniel| 1         1        4| 1         bird|
| 2        tabby| 2         1       23| 4          pet|
| 3      chicken| 3         1       41|23          dog|
| 4     goldfish| 4         2        4|24          cat|
|               | 5         2       24|25      reptile|
|               | 6         3        1|38         fish|
|               | 7         3       40|40    delicious|
|               | 8         4        4|41        cheap|
|               | 9         4       38|42    expensive|
|               |10         4       41|               |
|               |                     |               |
+---------------+---------------------+---------------+

I want to run a query of one ore more tags against the three tables to return the items that match ALL of the tags.

So for example, querying for "pet" would return the items (1)spaniel, (2)tabby and (4)goldfish, because all of them are tagged "pet". Querying for "cheap" and "pet" together would return (1)spaniel and (4)goldfish because they are both tagged "cheap" and "pet". Tabby would not be returned as it is only tagged "pet" but not "cheap" (in my world tabby cats are expensive :P)

Querying for "cheap", "pet" and "dog" would only return (1)Spaniel, since it is the only one matching all three tags.

Anyway, this is the desired behaviour. I have two questions.

1. Is this the best way to set up my tables for my intended purposes? I am still new to ideas of normalising databases, and am picking this up as I go along - any input on efficiency or even if this is an appropriate layout for my database would be much appreciated.

2. Provided the above setup is workable, how could I structure a single MySQL query to achieve my intended purpose?* (that being, for a series of tags, returning ONLY the item(s) that match ALL the specified tags). I have tried doing a variety of JOINs/UNIONs but none of them are giving me the desired effect(usually return ALL the items that match ANY of the tags)． I've spent some time looking through the MySQL manual online but I feel like I'm missing something conceptually.

*I say single query since of course I could just run a series of simple WHERE/JOIN queries, one for each tag and then combine/sort the returned items in PHP or something after the fact but it seems a foolish and inefficient way of doing it. I feel like there is a way I should be able to do this with a single MySQL query, given the appropriate setup.

Answer 1

Your schema is looking fairly good. There’s no need for the ID column in your join table—just create a primary key from the ID columns of the other tables (although see Marjan Venema's comment and Should I use composite primary keys or not? for alternative views on this). The following examples show how you can create the tables, add some data, and perform the queries that you requested.

Create tables, complete with foreign key constraints. In short, foreign key constraints help to ensure database integrity. In this example, they prevent items being inserted in the join table (item_tag), if there are no matching items in the item and tag tables:

CREATE  TABLE IF NOT EXISTS `item` (
  `id` INT UNSIGNED NOT NULL AUTO_INCREMENT ,
  `item` VARCHAR(255) NOT NULL ,
  PRIMARY KEY (`id`) )
ENGINE = InnoDB;

CREATE  TABLE IF NOT EXISTS `tag` (
  `id` INT UNSIGNED NOT NULL AUTO_INCREMENT ,
  `tag` VARCHAR(255) NOT NULL ,
  PRIMARY KEY (`id`) )
ENGINE = InnoDB;

CREATE  TABLE IF NOT EXISTS `item_tag` (
  `item_id` INT UNSIGNED NOT NULL ,
  `tag_id` INT UNSIGNED NOT NULL ,
  PRIMARY KEY (`item_id`, `tag_id`) ,
  INDEX `fk_item_tag_item` (`item_id` ASC) ,
  INDEX `fk_item_tag_tag` (`tag_id` ASC) ,
  CONSTRAINT `fk_item_tag_item`
    FOREIGN KEY (`item_id` )
    REFERENCES `item` (`id` )
    ON DELETE CASCADE
    ON UPDATE CASCADE,
  CONSTRAINT `fk_item_tag_tag`
    FOREIGN KEY (`tag_id` )
    REFERENCES `tag` (`id` )
    ON DELETE CASCADE
    ON UPDATE CASCADE)
ENGINE = InnoDB;

Insert some test data:

INSERT INTO item (item) VALUES
('spaniel'),
('tabby'),
('chicken'),
('goldfish');

INSERT INTO tag (tag) VALUES
('bird'),
('pet'),
('dog'),
('cat'),
('reptile'),
('fish'),
('delicious'),
('cheap'),
('expensive');

INSERT INTO item_tag (item_id, tag_id) VALUES
(1,2),
(1,3),
(1,8),
(2,2),
(2,4),
(3,1),
(3,7),
(4,2),
(4,6),
(4,8);

Select all items and all tags:

SELECT item.id, item.item, tag.tag
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id;

+----+----------+-----------+
| id | item     | tag       |
+----+----------+-----------+
|  1 | spaniel  | pet       |
|  1 | spaniel  | dog       |
|  1 | spaniel  | cheap     |
|  2 | tabby    | pet       |
|  2 | tabby    | cat       |
|  3 | chicken  | bird      |
|  3 | chicken  | delicious |
|  4 | goldfish | pet       |
|  4 | goldfish | fish      |
|  4 | goldfish | cheap     |
+----+----------+-----------+

Select items with a specific tag:

SELECT item.id, item.item, tag.tag
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id
WHERE tag = 'pet';

+----+----------+-----+
| id | item     | tag |
+----+----------+-----+
|  1 | spaniel  | pet |
|  2 | tabby    | pet |
|  4 | goldfish | pet |
+----+----------+-----+

Select items with one or more tags. Note that this will return items that have the tags cheap OR pet:

SELECT item.id, item.item, tag.tag
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id
WHERE tag IN ('cheap', 'pet');

+----+----------+-------+
| id | item     | tag   |
+----+----------+-------+
|  1 | spaniel  | pet   |
|  1 | spaniel  | cheap |
|  2 | tabby    | pet   |
|  4 | goldfish | pet   |
|  4 | goldfish | cheap |
+----+----------+-------+

The above query produces an answer that you might not want, as highlighted by the following query. In this case, there are no items with the house tag, but this query still returns some rows:

SELECT item.id, item.item, tag.tag
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id
WHERE tag IN ('cheap', 'house');

+----+----------+-------+
| id | item     | tag   |
+----+----------+-------+
|  1 | spaniel  | cheap |
|  4 | goldfish | cheap |
+----+----------+-------+

You can fix that by adding GROUP BY and HAVING:

SELECT item.id, item.item, tag.tag
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id
WHERE tag IN ('cheap', 'house')
GROUP BY item.id HAVING COUNT(*) = 2;

Empty set (0.00 sec)

GROUP BY causes all items with the same id (or whatever column you specify) to be grouped together into a single row, effectively removing duplicates. HAVING COUNT limits the results to those where the count of the matching grouped rows is equal to two. That ensures that only items with two tags are returned - note that this value must match the number of tags specified in the IN clause. Here’s an example that produces something:

SELECT item.id, item.item, tag.tag
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id
WHERE tag IN ('cheap', 'pet')
GROUP BY item.id HAVING COUNT(*) = 2;

+----+----------+-----+
| id | item     | tag |
+----+----------+-----+
|  1 | spaniel  | pet |
|  4 | goldfish | pet |
+----+----------+-----+

Note that in the previous example, the items have been grouped together so that you don’t get duplicates. In this case, there’s no need for the tag column, as that just confuses the results—you already know what tags there are, as you have requested items with those tags. You can therefore simplify things a little by removing the tag column from the query:

SELECT item.id, item.item
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id
WHERE tag IN ('cheap', 'pet')
GROUP BY item.id HAVING COUNT(*) = 2;

+----+----------+
| id | item     |
+----+----------+
|  1 | spaniel  |
|  4 | goldfish |
+----+----------+

You could go a step further, and use GROUP_CONCAT to provide a list of matching tags. This might be handy where you want a list of items that have one or more of the specified tags, but not necessarily all of them:

SELECT item.id, item.item, GROUP_CONCAT(tag.tag) AS tags
FROM item
JOIN item_tag ON item_tag.item_id = item.id
JOIN tag ON item_tag.tag_id = tag.id
WHERE tag IN ('cheap', 'pet', 'bird', 'cat')
GROUP BY id;

+----+----------+-----------+
| id | item     | tags      |
+----+----------+-----------+
|  1 | spaniel  | pet,cheap |
|  2 | tabby    | pet,cat   |
|  3 | chicken  | bird      |
|  4 | goldfish | pet,cheap |
+----+----------+-----------+

One problem with the above schema design is that it is possible to enter duplicate items and tags. That is, you could insert bird into the tag table as many times as you like, and this is not good. One way to fix that is to add a UNIQUE INDEX to the item and tag columns. This has the added benefit of helping to speed up queries which rely on these columns. The updated CREATE TABLE commands now look like this:

CREATE  TABLE IF NOT EXISTS `item` (
  `id` INT UNSIGNED NOT NULL AUTO_INCREMENT ,
  `item` VARCHAR(255) NOT NULL ,
  UNIQUE INDEX `item` (`item`) ,
  PRIMARY KEY (`id`) )
ENGINE = InnoDB;

CREATE  TABLE IF NOT EXISTS `tag` (
  `id` INT UNSIGNED NOT NULL AUTO_INCREMENT ,
  `tag` VARCHAR(255) NOT NULL ,
  UNIQUE INDEX `tag` (`tag`) ,
  PRIMARY KEY (`id`) )
ENGINE = InnoDB;

Now if you try to insert a duplicate value, MySQL will prevent you from doing so:

INSERT INTO tag (tag) VALUES ('bird');
ERROR 1062 (23000): Duplicate entry 'bird' for key 'tag'

Answer 2

Yes. This is called relational division. A variety of techniques are discussed here http://www.simple-talk.com/sql/t-sql-programming/divided-we-stand-the-sql-of-relational-division/

One Approach would be to use a double negative. ie. to select all records from table 1 for which no tag in the list 'cheap','pet' does not have an associated record in table2

SELECT t1.id, t1.item
FROM Table1 t1
WHERE NOT EXISTS
(
    SELECT * FROM  
    table3 t3 WHERE tag IN ('cheap','pet')
    AND NOT EXISTS (
        SELECT * FROM table2 t2
        WHERE t2.tag_id = t3.id
        AND t1.id=t2.item_id
    )
)