Zainspirowany tym pytaniem StackOverflow:

Znajdź wspólny element w różnych faktach w swi-prologu

Mamy następujące

Opis problemu

Biorąc pod uwagę bazę danych „aktorów występujących w filmach” (na przykład starsin to relacja łącząca aktora „bob” z filmem „a”)

starsin(a,bob).
starsin(c,bob).

starsin(a,maria).
starsin(b,maria).
starsin(c,maria).

starsin(a,george).
starsin(b,george).
starsin(c,george).
starsin(d,george).

A biorąc pod uwagę zestaw filmów M , znajdź tych aktorów, którzy wystąpili we wszystkich filmach M .

Pytanie było początkowo dla Prologu.

Rozwiązanie Prolog

W Prologu eleganckie rozwiązanie zawiera predykat setof/3, który zbiera możliwe wystąpienia zmiennych w zestaw (który jest w rzeczywistości listą bez zduplikowane wartości):

actors_appearing_in_movies(MovIn,ActOut) :-
    setof(
        Ax,
        MovAx^(setof(Mx,starsin(Mx,Ax),MovAx), subset(MovIn,MovAx)),
        ActOut
    ).    

Nie będę wchodził w szczegóły na ten temat, ale spójrzmy na kod testowy, który jest tutaj interesujący. Oto pięć przypadków testowych:

actors_appearing_in_movies([],ActOut),permutation([bob, george, maria],ActOut),!. 
actors_appearing_in_movies([a],ActOut),permutation([bob, george, maria],ActOut),!.
actors_appearing_in_movies([a,b],ActOut),permutation([george, maria],ActOut),!.
actors_appearing_in_movies([a,b,c],ActOut),permutation([george, maria],ActOut),!.
actors_appearing_in_movies([a,b,c,d],ActOut),permutation([george],ActOut),!.

Test to wywołanie predykatu actors_appearing_in_movies/2, który jest podany lista wejściowa filmów (np. [a,b]), która przechwytuje wynikową listę aktorzy w ActOut.

Następnie musimy tylko sprawdzić, czy ActOut jest permutacją oczekiwanego zestaw aktorów, stąd np .:

permutation([george, maria],ActOut)`

„Czy ActOut jest listą, która jest permutacją listy [george,maria] ?.

Jeśli to wywołanie powiedzie się (pomyśl, nie wróci z false), test przechodzi.

Terminal ! jest operatorem cięcia i służy do informowania silnika Prologu, aby tego nie robił spróbuj znaleźć więcej rozwiązań, ponieważ jesteśmy w tym dobrzy.

Zwróć uwagę, że w przypadku pustego zestawu filmów otrzymujemy wszystkich aktorów . Jest to prawdopodobnie poprawne: wszyscy aktorzy występują we wszystkich filmach z pustego planu (Vacuous Truth).

Teraz w SQL.

Ten problem jest bezpośrednio związany z algebrą relacyjną i istnieje SQL, więc zajmijmy się tym. Tutaj używam MySQL.

Najpierw przedstaw fakty.

DROP TABLE IF EXISTS starsin;

CREATE TABLE starsin (movie CHAR(20) NOT NULL, actor CHAR(20) NOT NULL);

INSERT INTO starsin VALUES
   ( "a" , "bob" ),
   ( "c" , "bob" ),
   ( "a" , "maria" ),
   ( "b" , "maria" ),
   ( "c" , "maria" ),
   ( "a" , "george" ),
   ( "b" , "george" ),
   ( "c" , "george" ),
   ( "d",  "george" );

Biorąc pod uwagę zbiór filmów podanych jako dane wejściowe, podając je w postaci pliku (tymczasowy) stół brzmi naturalnie. W MySQL „tabele tymczasowe” są lokalne dla sesji. Dobrze.

DROP TABLE IF EXISTS movies_in;
CREATE TEMPORARY TABLE movies_in (movie CHAR(20) NOT NULL);
INSERT INTO movies_in VALUES ("a"), ("b");

Podejście:

Wyniki można teraz uzyskać, pobierając dla każdego aktora przecięcie zbioru filmy oznaczone przez movies_in oraz zbiór filmów, w których kiedykolwiek wystąpił aktor (utworzony dla każdego aktora za pomocą sprzężenia wewnętrznego), a następnie zliczanie (dla każdego aktora), czy plik wynikowy zbiór ma co najmniej tyle wpisów, co zbiór movies_in.

Ze względów praktycznych zawiń zapytanie w procedurę. Przydatny jest separator:

DELIMITER $$

DROP PROCEDURE IF EXISTS actors_appearing_in_movies;

CREATE PROCEDURE actors_appearing_in_movies()
BEGIN

SELECT 
     d.actor 
   FROM 
     starsin d, movies_in q
   WHERE 
     d.movie = q.movie 
   GROUP BY 
     actor 
   HAVING 
     COUNT(*) >= (SELECT COUNT(*) FROM movies_in);

END$$

DELIMITER ;

Uruchom!

Pojawia się problem A:

Czy jest lepszy sposób niż edycja + kopiowanie i wklejanie kodu tworzenia tabeli, wystawić CALL i sprawdzić wyniki „ręcznie”?

DROP TABLE IF EXISTS movies_in;
CREATE TEMPORARY TABLE movies_in (movie CHAR(20) NOT NULL);
CALL actors_appearing_in_movies();

Pusty zestaw!

Pojawia się problem B:

Powyższe nie jest pożądane, chcę „wszystkich aktorów”, tak samo jak w przypadku rozwiązania Prolog. Ponieważ nie chcę dołączać do kodu dziwnego wyjątku dotyczącego skrajnych przypadków, moje podejście musi mylić się. Czy jest taki, który naturalnie obejmuje ten przypadek, ale nie staje się zbyt skomplikowany? T-SQL i jednolinijkowe PostgreSQL też są w porządku!

Inne przypadki testowe dostarczają oczekiwanych danych:

DROP TABLE IF EXISTS movies_in;
CREATE TEMPORARY TABLE movies_in (movie CHAR(20) NOT NULL);
INSERT INTO movies_in VALUES ("a"), ("b");
CALL actors_appearing_in_movies();
+--------+
| actor  |
+--------+
| george |
| maria  |
+--------+

DROP TABLE IF EXISTS movies_in;
CREATE TEMPORARY TABLE movies_in (movie CHAR(20) NOT NULL);
INSERT INTO movies_in VALUES ("a"), ("b"), ("c");
CALL actors_appearing_in_movies();
+--------+
| actor  |
+--------+
| george |
| maria  |
+--------+

DROP TABLE IF EXISTS movies_in;
CREATE TEMPORARY TABLE movies_in (movie CHAR(20) NOT NULL);
INSERT INTO movies_in VALUES ("a"), ("b"), ("c"), ("d");
CALL actors_appearing_in_movies();
+--------+
| actor  |
+--------+
| george |
+--------+
1
David Tonhofer 9 marzec 2020, 19:27

2 odpowiedzi

Najlepsza odpowiedź

A biorąc pod uwagę zestaw filmów M, znajdź tych aktorów, którzy wystąpili we wszystkich filmach M.

Użyłbym:

select si.actor
from starsin si
where si.movie in (<M>)
group by si.actor
having count(*) = <n>;

Jeśli masz do czynienia z pustym zestawem, potrzebujesz left join:

select a.actor
from actors a left join
     starsin si
     on a.actor = si.actor and si.movie in (<M>)
group by a.actor
having count(si.movie) = <n>;

<n> tutaj jest liczba filmów w <M>.

Aktualizacja: Drugie podejście w rozszerzonej formie

create or replace temporary table 
   actor (actor char(20) primary key)
   as select distinct actor from starsin;

select 
   a.actor,
   si.actor,si.movie  -- left in for docu
from 
   actor a left join starsin si
     on a.actor = si.actor 
        and si.movie in (select * from movies_in)
group 
   by a.actor
having
   count(si.movie) = (select count(*) from movies_in);

Następnie dla pustego movies_in:

+--------+-------+-------+
| actor  | actor | movie |
+--------+-------+-------+
| bob    | NULL  | NULL  |
| george | NULL  | NULL  |
| maria  | NULL  | NULL  |
+--------+-------+-------+

A dla tego movies_in na przykład:

+-------+
| movie |
+-------+
| a     |
| b     |
+-------+

movie tutaj jest na szczycie grupy:

+--------+--------+-------+
| actor  | actor  | movie |
+--------+--------+-------+
| george | george | a     |
| maria  | maria  | a     |
+--------+--------+-------+
1
David Tonhofer 11 marzec 2020, 14:07

Poniższe rozwiązanie obejmuje liczenie i UPDATE

Napisz tutaj: Prosta operacja na relacyjnej bazie danych

Używamy MariaDB / MySQL SQL. T-SQL lub PL / SQL są bardziej kompletne.

Należy zauważyć, że SQL nie ma typów danych wektorowych, które można przekazać do procedur. Muszę pracować bez tego.

Wprowadź fakty w tabeli:

CREATE OR REPLACE TABLE starsin 
   (movie CHAR(20) NOT NULL, actor CHAR(20) NOT NULL, 
    PRIMARY KEY (movie, actor));

INSERT INTO starsin VALUES
   ( "a" , "bob" ),
   ( "c" , "bob" ),
   ( "a" , "maria" ),
   ( "b" , "maria" ),
   ( "c" , "maria" ),
   ( "a" , "george" ),
   ( "b" , "george" ),
   ( "c" , "george" ),
   ( "d",  "george" );

Wprowadź procedurę obliczania rozwiązania i faktycznie ... wydrukuj ją.

DELIMITER $$

CREATE OR REPLACE PROCEDURE actors_appearing_in_movies()
BEGIN

   -- collect all the actors
   CREATE OR REPLACE TEMPORARY TABLE tmp_actor (actor CHAR(20) PRIMARY KEY)
     AS SELECT DISTINCT actor from starsin;

   -- table of "all actors x (input movies + '--' placeholder)"
   -- (combinations that are needed for an actor to show up in the result)
   -- and a flag indicating whether that combination shows up for real
   CREATE OR REPLACE TEMPORARY TABLE tmp_needed 
     (actor CHAR(20), 
      movie CHAR(20), 
      actual TINYINT NOT NULL DEFAULT 0,
     PRIMARY KEY (actor, movie))
   AS 
     (SELECT ta.actor, mi.movie FROM tmp_actor ta, movies_in mi)
     UNION
     (SELECT ta.actor, "--" FROM tmp_actor ta);

   -- SELECT * FROM tmp_needed;

   -- Mark those (actor, movie) combinations which actually exist
   -- with a numeric 1
   UPDATE tmp_needed tn SET actual = 1 WHERE EXISTS
      (SELECT * FROM starsin si WHERE
             si.actor = tn.actor AND si.movie = tn.movie);

   -- SELECT * FROM tmp_needed;

   -- The result is the set of actors in "tmp_needed" which have as many
   -- entries flagged "actual" as there are entries in "movies_in"

   SELECT actor FROM tmp_needed GROUP BY actor 
      HAVING SUM(actual) = (SELECT COUNT(*) FROM movies_in);

END$$

DELIMITER ;

Testowanie

Nie ma gotowego do użycia frameworka do testów jednostkowych dla MariaDB, więc „testujemy ręcznie” i piszemy procedurę, z której sprawdzamy ręcznie. Argumenty zmienne nie istnieją, typy danych wektorowych nie istnieją. Przyjmijmy do 4 filmów jako dane wejściowe i sprawdźmy ręcznie wynik.

DELIMITER $$

CREATE OR REPLACE PROCEDURE 
   test_movies(IN m1 CHAR(20),IN m2 CHAR(20),IN m3 CHAR(20),IN m4 CHAR(20))
BEGIN
   CREATE OR REPLACE TEMPORARY TABLE movies_in (movie CHAR(20) PRIMARY KEY);   
   CREATE OR REPLACE TEMPORARY TABLE args (movie CHAR(20));
   INSERT INTO args VALUES (m1),(m2),(m3),(m4); -- contains duplicates and NULLs
   INSERT INTO movies_in (SELECT DISTINCT movie FROM args WHERE movie IS NOT NULL); -- clean
   DROP TABLE args;   
   CALL actors_appearing_in_movies();        
END$$

DELIMITER ;

Powyższe przechodzi wszystkie testy manualne, w szczególności:

CALL test_movies(NULL,NULL,NULL,NULL);

+--------+
| actor  |
+--------+
| bob    |
| george |
| maria  |
+--------+
3 rows in set (0.003 sec)

Na przykład dla CALL test_movies("a","b",NULL,NULL);

Najpierw przygotuj tabelę ze wszystkimi aktorami przeciwko wszystkim filmom z zestawu wejściowego, w tym Film „nie istnieje” reprezentowany przez symbol zastępczy --.

+--------+--------+-------+
| actual | actor  | movie |
+--------+--------+-------+
|      0 | bob    | --    |
|      0 | bob    | a     |
|      0 | bob    | b     |
|      0 | george | --    |
|      0 | george | a     |
|      0 | george | b     |
|      0 | maria  | --    |
|      0 | maria  | a     |
|      0 | maria  | b     |
+--------+--------+-------+

Następnie zaznacz te wiersze cyfrą 1, w których faktycznie istnieje kombinacja aktora i filmu w starsin.

+--------+--------+-------+
| actual | actor  | movie |
+--------+--------+-------+
|      0 | bob    | --    |
|      1 | bob    | a     |
|      0 | bob    | b     |
|      0 | george | --    |
|      1 | george | a     |
|      1 | george | b     |
|      0 | maria  | --    |
|      1 | maria  | a     |
|      1 | maria  | b     |
+--------+--------+-------+

Na koniec wybierz aktora do włączenia do rozwiązania, jeśli SUM(actual) jest równe liczba wpisów w tabeli filmów wejściowych (nie może być większa), ponieważ oznacza to, że plik aktor rzeczywiście pojawia się we wszystkich filmach w tabeli filmów wejściowych. W szczególnym przypadku, gdy to tabela jest pusta, tabela kombinacji aktor-film będzie zawierać tylko

+--------+--------+-------+
| actual | actor  | movie |
+--------+--------+-------+
|      0 | bob    | --    |
|      0 | george | --    |
|      0 | maria  | --    |
+--------+--------+-------+

W ten sposób wszyscy aktorzy zostaną wybrani, a tego chcemy.

0
David Tonhofer 11 marzec 2020, 14:08