What is the benefit of two FK, when one of them can be deduced from another table?
Category has one foreign key to Shop. The Product has two foreign keys: one to Category, another to Shop.


There should be a single foreign key referencing two columns in categories. 

create table products (
  ...
  primary key (shop_id, category_id, product_id),
  foreign key (shop_id, category_id) 
    references categories (shop_id, category_id)
);


Think about it this way. Conceptually, normalization starts with a single relation that contains all the attributes. 

shop_name  category_name    product_name
--
Wibble     Chain saws       Stihl 350
Wibble     Chain saws       Poulan 3X
Wibble     Pole saws        Black &amp; Decker 14 foot electric
Wibble     Pole saws        Corona 15 foot

Thursby    Pole saws        Hitachi electric
Thursby    Pole saws        Remington electric
Thursby    Chain saws       Husqvarna 460
Thursby    Chain saws       Poulan 3x


It should be clear that the only candidate key is {shop_name, category_name, product_name}. It's in 5NF. There's no redundant data. 

Replacing text with ID numbers won't improve that. 

A design that requires you to chase ID numbers through a hierarchy of tables is an anti-pattern. It's like building an IMS database in SQL. (IMS was a problem the relational model intended to solve.)