How to model a three-way association that involves Product, Category and Label?

I have the following three tables:

products:
    product_id,
    product_name,
    ...

categories:
    category_id,
    category_name,
    category_parent_id,
    category_priority (for sort ordering),
    .....

labels:
    label_id,
    label_name,
    .....

The idea is that products assigned to a category will be grouped within each category by labels and listed on the website in this manner:

---label1---
product_1
product_2
product_3
---label2---
product_4
product_5
---label3---
product_6
product_7
product_8
product_9
etc.

I can’t figure out how to design an association table (or tables) that glue all this together and prevent anomalies like this:

---label1---
product_1
product_2
---label2---
product_2
product_3

At the same time, I’d like to allow a situation where there will be no labels assigned to a category when there are not enough products to justify it.
Questions

Is it possible to design a structure that will hold it together or should I ‘abandon all hope’ and go with something like this:

categories:
    category_id,
    category_name,
    category_parent_id,
    categor_is_label,
    category_priority

products:
    product_id,
    product_name,
    ...

plus the association table that follows:

categories_products:
    category_id,
    product_id,
    priority

and handle all logic and checking for anomalies in the application?

I’m assuming that users won’t have direct access to the database.
Comments and chat interactions

For those interested in an in-depth conversation about the business context at hand, you can visit this chat room.

Note: This answer presents an approach to cover specifically the business rules derived by way of the earliest series of comment and chat interactions (most of which can be seen in this question revision). Nevertheless, after more in-depth clarifications and deliberations took place, @yemet indicated that the business context may require a somewhat distinct method, due to the successive identification of dfferent business rules.

The fact that you have determined that there exists a three-way association (also known as ternary or diamond shaped relationship) that involves the entity types (tables once implemented) of interest shows that you are heading in the right direction.
Business rules

The objective should be to handle the three distinct relationships at hand separately, starting with a logical level analysis before considering the implementation aspects in full. In this regard, it is quite helpful to write down some formulations that describe the relevant business rules, e.g.:

First, for the following many-to-many (M:N) relationship:

• A product is classified by one-to-many categories

• A category classifies zero-one-or-many products

Which implies the existence of an associative entity type that I am going to call product_category.

Second, for a distinct M:N relationship:

• A category is integrated by zero-one-or-many labels

• A label integrates zero-one-or-many categories

Situation that suggests that there is another associative entity type, in this case the one that I will name category_label.

Then, it is time to manage another M:N relationship, this time between the two associative entity types discussed above:

• A product_category may receive zero-one-or-many label_assignments

• A category_label may take part in zero-one-or-many label_assignments

As noted, I have included a new entity type that I denominated label_assignment but, naturally, you may name it using a term that is more meaningful with respect to your business domain.

I have assumed, based on the structure of the categories table contained in your question (specifically the column categories.category_parent_id), that there is a self-recursive one-to-many (1:M) relationship concerning the entity type called category. Later, you confirmed such situation, so the following rule applies as well:

• A category comprises zero-one-or-many categories

Logical Model

Then I have derived an IDEF1X1 logical model from the business rules formulations presented above, that is shown in Figure 1:

With this arrangement you can solve much of your needs, since:

• Each product has to first be related to a certain category before it receives a label assignment.

• A label cannot be assigned to a particular product if it has not been connected to a certain category previously.

• A product can be related to a certain category without having to be involved in a relationship with a label.

Expository DDL structure

Consequently, I coded the following DDL structure (tested on SQL Fiddle):

```
-- You should determine which are the most fitting
-- data types and sizes for all your table columns
-- depending on your business context characteristics.

-- As one would expect, you are free to make use of
-- your preferred (or required) naming conventions.

CREATE TABLE product
(
product_id INT NOT NULL,
product_code CHAR(30) NOT NULL,
name CHAR(30) NOT NULL,
description CHAR(90) NOT NULL,
created_datetime DATETIME NOT NULL,
CONSTRAINT PK_product PRIMARY KEY (product_id),
CONSTRAINT AK_product_code UNIQUE (product_code), -- (Possible?) ALTERNATE KEY.
CONSTRAINT AK_product_name UNIQUE (name), -- ALTERNATE KEY.
CONSTRAINT AK_product_description UNIQUE (description) -- ALTERNATE KEY.
);

CREATE TABLE category
(
category_number INT NOT NULL,
parent_category_number INT NULL, -- Set up as ‘NULLable’, in order to focus on the main aspects of the approach exposed.
name CHAR(30) NOT NULL,
description CHAR(90) NOT NULL,
created_datetime DATETIME NOT NULL,
CONSTRAINT PK_category PRIMARY KEY (category_number),
CONSTRAINT AK_category_name UNIQUE (name), -- ALTERNATE KEY.
CONSTRAINT AK_category_description UNIQUE (description), -- ALTERNATE KEY.
CONSTRAINT FK_FROM_category_TO_parent_category FOREIGN KEY (parent_category_number)
REFERENCES category (category_number)
);

CREATE TABLE label
(
label_number INT NOT NULL,
name CHAR(30) NOT NULL,
description CHAR(90) NOT NULL,
created_datetime DATETIME NOT NULL,
CONSTRAINT PK_label PRIMARY KEY (label_number),
CONSTRAINT AK_label_name UNIQUE (name), -- ALTERNATE KEY.
CONSTRAINT AK_label_description UNIQU

StackExchange Database Administrators Q#150865, answer score: 5