How to properly design this part of a database (circular reference?)

Question

Situation:

A company has many projects
A project has many tags

A project belongs to only 1 company
A tag can belong to multiple projects

A company must have access to its own tags

Example 1:

In the first image, all tags for the company are available through the projects/project_tag. But if all projects are removed, then the tags for the company will not be accessible anymore, because the link between project_tag and projects is gone. The tags should be somehow always be linked to the company, even if there are no projects.

Example 2 (where tags are also linked to the company):

In the second image, it should work, but is this now a 'circular reference' ??? What should be the best solution for a problem like this? And what about foreign keys?

The question finally is: How to properly set up a database/datamodel for this situation?

---

Example when things could go wrong in the second example:

companies:
id=1, name=MyCompany
id=2, name=OtherCompany

tags:
id=1, company_id=1, name=MyTag
id=2, company_id=2, name=OtherTag

projects:
id=1, company_id=1, name=MyProject

project_tag:
project_id=1, tag_id=1
project_id=1, tag_id=2 --> THIS ROW IS NOT VALID!

The last project_tag row is not valid because:
project 1 is linked to company_id 1
tag_id 2 is linked to company_id 2

---

UPDATED: Thanks all for the information!

Based on the accepted answer, the CREATE queries for PostgreSQL would become:

CREATE TABLE companies (
   id SERIAL PRIMARY KEY NOT NULL,
   name TEXT NOT NULL
);
CREATE TABLE projects (
   id SERIAL PRIMARY KEY NOT NULL,
   company_id INT NOT NULL,
   name TEXT NOT NULL,
   UNIQUE (id, company_id),
   FOREIGN KEY (company_id) REFERENCES companies (id) ON DELETE RESTRICT ON UPDATE CASCADE
);
CREATE TABLE tags (
   id SERIAL PRIMARY KEY NOT NULL,
   company_id INT NOT NULL,
   name TEXT NOT NULL,
   UNIQUE (id, company_id),
   FOREIGN KEY (company_id) REFERENCES companies (id) ON DELETE CASCADE ON UPDATE CASCADE
);
CREATE TABLE project_tag (
   id SERIAL PRIMARY KEY NOT NULL,
   company_id INT NOT NULL,
   project_id INT NOT NULL,
   tag_id INT NOT NULL,
   UNIQUE (company_id, project_id, tag_id),
   FOREIGN KEY (company_id, project_id) REFERENCES projects (company_id, id) ON DELETE CASCADE ON UPDATE CASCADE,
   FOREIGN KEY (company_id, tag_id) REFERENCES tags (company_id, id) ON DELETE CASCADE ON UPDATE CASCADE
);

Tested:
- Rows inserted in project_tag are checked on the same company_id (else: denied)
- Not possible to insert duplicate rows into project_tag
- If a project is removed, the linked project_tag rows are also removed
- If a tag is removed, the linked project_tag rows are also removed
- If a company is being removed while still having projects, the removal is rejected (see projects table: ON DELETE RESTRICT)
- If a company (without projects) is removed, all linked tags are removed also

Answer 1

First of all, your second model is absolutely correct and there is not any circular reference in it.

You should transmit Company_ID of Company as F.K to Tags and Project and make it Not Null.

Then, you should transmit TAG_ID and Project_ID as F.Ks into Project_Tag and make the unique together. And there is no need to transmit the Company_ID of Project and Tag (that we transmitted in previous paragraph) into Project_Tag.

Now, how about final question, Your final request:

THIS ROW IS NOT VALID!

You can not capture it by ER. You should write some functions, triggers or stored procedures to capture and control it.

Edit:
Based on @reaanb's comments and his great answer here: You can control this constraint by this way with a little redundancy:

CREATE TABLE Project(
    project_id INT NOT NULL,
    company_id INT NOT NULL,
    PRIMARY KEY (project_id),
    FOREIGN KEY (company_id) REFERENCES Company (id),
    UNIQUE KEY (project_id, company_id)
);

CREATE TABLE Tag(
    tag_id INT NOT NULL,
    company_id INT NOT NULL,
    PRIMARY KEY (tag_id),
    FOREIGN KEY (company_id) REFERENCES Company (id),
    UNIQUE KEY (tag_id, company_id)
);

CREATE TABLE Project_Tags(
    id INT NOT NULL,
    company_id INT NOT NULL,
    project_id INT NOT NULL,
    tag_id INT NOT NULL,

    PRIMARY KEY (id),
    UNIQUE KEY (tag_id, project_id)

    FOREIGN KEY (project_id, company_id) REFERENCES Project (project_id, company_id),
    FOREIGN KEY (tag_id, company_id) REFERENCES Tag (tag_id, company_id),
);