requête pour un ensemble dans une base de données relationnelle

Question

Je voudrais interroger une base de données relationnelle si un ensemble d'éléments existe.

Les données que je suis modélisation sont de la forme suivante:

key1 = [ item1, item3, item5 ] 
key2 = [ item2, item7 ] 
key3 = [ item2, item3, item4, item5 ] 
... 

Je suis les stocker dans une table avec le schéma suivant

CREATE TABLE sets (key INTEGER, item INTEGER); 

Ainsi, par exemple, les instructions d'insertion suivantes insérerions les trois ensembles ci-dessus.

INSERT INTO sets VALUES (key1, item1); 
INSERT INTO sets VALUES (key1, item3); 
INSERT INTO sets VALUES (key1, item5); 
INSERT INTO sets VALUES (key2, item2); 
INSERT INTO sets VALUES (key2, item7); 
INSERT INTO sets VALUES (key3, item2); 
INSERT INTO sets VALUES (key3, item3); 
INSERT INTO sets VALUES (key3, item4); 
INSERT INTO sets VALUES (key3, item5); 

Étant donné un ensemble d'éléments, je voudrais la clé associée à l'ensemble si elle est stockée dans la table et NULL si ce n'est pas. Est-il possible de le faire avec une requête SQL? Si oui, veuillez fournir des détails.

Des détails qui peuvent être pertinents:

• Je suis principalement intéressé par la stratégie de conception de base de données/requête, bien que je vais éventuellement implémenter dans MySQL et préforme la requête à partir avec en python utilisant le paquet mysql-python .
• J'ai la liberté de restructurer le schéma de base de données si une mise en page différente serait plus pratique pour ce type de requête.
• Chaque ensemble, s'il existe, est supposé être unique.
• Je ne suis pas intéressé par les correspondances partielles.
• L'échelle de la base de données est de l'ordre de < 1000 ensembles contenant chacun < 10 éléments chacun, donc les performances à ce stade ne sont pas une priorité.

Merci d'avance.

Answer 1

Je ne commenterai pas s'il existe un schéma mieux adapté pour ce faire (c'est tout à fait possible), mais pour un schéma ayant les colonnes name et item, la requête suivante devrait fonctionner. (Syntaxe MySQL)

SELECT k.name 
FROM (SELECT DISTINCT name FROM sets) AS k 
INNER JOIN sets i1 ON (k.name = i1.name AND i1.item = 1) 
INNER JOIN sets i2 ON (k.name = i2.name AND i2.item = 3) 
INNER JOIN sets i3 ON (k.name = i3.name AND i3.item = 5) 
LEFT JOIN sets ix ON (k.name = ix.name AND ix.item NOT IN (1, 3, 5)) 
WHERE ix.name IS NULL; 

L'idée est que nous avons toutes les clés définies dans k, que nous rejoignons ensuite avec les données de l'élément de jeu dans sets fois pour chaque élément de jeu dans l'ensemble que nous cherchons, trois ce cas. Chacune des trois jointures internes avec les alias de table i1, i2 et i3 filtre tous les noms d'ensemble qui ne contiennent pas l'élément recherché avec cette jointure. Enfin, nous avons une jointure à gauche avec sets avec l'alias de table ix, qui apporte tous les éléments supplémentaires de l'ensemble, c'est-à-dire tous les éléments que nous ne cherchions pas. ix.name est NULL dans le cas où aucun élément supplémentaire n'est trouvé, ce qui est exactement ce que nous voulons, donc la clause WHERE. La requête renvoie une ligne contenant la clé set si l'ensemble est trouvé, aucune ligne sinon.

---

Edit: L'idée derrière collapsars réponse semble être beaucoup mieux que la mienne, voici donc un peu version plus courte de cette explication avec.

SELECT sets.name 
FROM sets 
LEFT JOIN (
    SELECT DISTINCT name 
    FROM sets 
    WHERE item NOT IN (1, 3, 5) 
) s1 
ON (sets.name = s1.name) 
WHERE s1.name IS NULL 
GROUP BY sets.name 
HAVING COUNT(sets.item) = 3; 

L'idée ici est que les sous-requête s1 sélectionne les clés de tous les ensembles qui contiennent des éléments autres que ceux que nous recherchons. Ainsi, lorsque nous quittons rejoindre sets avec s1, s1.name est NULL lorsque l'ensemble contient uniquement les éléments que nous recherchons. Nous regroupons ensuite par clé et filtrons tous les ensembles ayant le mauvais nombre d'éléments. Il ne nous reste plus alors que des ensembles qui ne contiennent que des éléments que nous recherchons et dont la longueur est correcte. Puisque les ensembles ne peuvent contenir qu'un seul élément, il ne peut y avoir qu'un seul ensemble répondant à ce critère, et c'est ce que nous recherchons.

---

Edit: Il vient sur moi comment est apparu le faire sans l'exclusion.

SELECT totals.name 
FROM (
    SELECT name, COUNT(*) count 
    FROM sets 
    GROUP BY name 
) totals 
INNER JOIN (
    SELECT name, COUNT(*) count 
    FROM sets 
    WHERE item IN (1, 3, 5) 
    GROUP BY name 
) matches 
ON (totals.name = matches.name) 
WHERE totals.count = 3 AND matches.count = 3; 

La première sous-requête trouve le nombre total d'éléments dans chaque ensemble et le second découvre le nombre d'éléments correspondant à chaque série. Lorsque matches.count est 3, l'ensemble a tous les éléments que nous recherchons, et si totals.count est également 3, l'ensemble n'a aucun élément supplémentaire.

Answer 2

La solution aleksis nécessite une requête spécifique pour chaque ensemble d'éléments possible. la suggestion suivante fournit une solution générique dans le sens où l'ensemble d'éléments à interroger peut être pris en compte en tant que jeu de résultats d'une autre requête - il suffit de remplacer les opérateurs de confinement définis par une sous-requête appropriée.

 SELECT CASE COUNT(ddd.key) WHEN 0 THEN NULL ELSE MIN(ddd.key) END 
     FROM (
       SELECT s4.key 
         , COUNT(*) icount 
        FROM sets s4 
        JOIN (
          SELECT DISTINCT d.key 
          FROM (
            SELECT s1.key 
            FROM sets s1 
            WHERE s1.item IN ('item1', 'item3', 'item5') 
            MINUS 
            SELECT s2.key 
            FROM sets s2 
            WHERE s2.item NOT IN ('item1', 'item3', 'item5') 
           ) d  
         ) dd ON (dd.key = s4.key) 
       GROUP BY s4.key 
      ) ddd 
     WHERE ddd.icount = (
          SELECT COUNT(*) 
           FROM (
             SELECT DISTINCT s3.item 
             FROM sets s3 
             WHERE s3.item IN ('item1', 'item3', 'item5') 
            ) 
         ) 
      ;     

le jeu de résultats dd délivre un ensemble candidat de clés qui n'asscociate pas avec d'autres éléments que ceux de l'ensemble à tester. la seule ambiguïté peut provenir de clés qui référencent un sous-ensemble correct de l'ensemble d'items testé. ainsi nous comptons le nombre d'éléments associés aux clés de dd et choisissons cette clé où ce nombre correspond à la cardinalité de l'ensemble d'items testé. si une telle clé existe, elle est unique (car nous savons que les ensembles d'objets sont uniques). L'expression de cas dans la sélection la plus externe est juste une manière élégante de garantir que leur ensemble de résultats ne sera pas vide, c'est-à-dire qu'une valeur nulle sera renvoyée si l'ensemble d'éléments n'est pas représenté par la relation.

peut-être cette solution sera utile pour vous,

meilleures salutations

carsten

Answer 3

Pour simplifier la solution de collapsar qui Aleksi Torhamo était déjà simplifié:

Il ne faut pas Pour obtenir toutes les clés QUI NE CORRESPONDENT PAS, qui peuvent être grandes, il suffit d'obtenir celles qui correspondent et de les appeler des correspondances partielles.

-- get all partial matches 
CREATE TEMPORARY VIEW partial_matches AS 
SELECT DISTINCT key FROM sets WHERE item IN (1,3,5); 

-- filter for full matches 
SELECT sets.key 
FROM sets, partial_matches 
WHERE sets.key = partial_matches.key 
GROUP BY sets.key HAVING COUNT(sets.key) = 3; 

Answer 4

Cette requête a un nom connu. Google "division relationnelle", "set containment rejoindre", "set égalité rejoindre".