Início / dba / Perguntas / 29016
Accepted
Bob Jansen
Asked: 2012-11-21 13:46:24 +0800 CST

Seleção sem repetições

  • 772

Eu tenho uma tabela com observações de objetos se movendo ao longo de arestas em um grafo, esta tabela tem a seguinte forma:

PK | TIMESTAMP | object_id | from_id | to_id

onde object_idé o id de algum objeto e from_ide to_idsão vértices.

Como os movimentos são observados em alta frequência, a tupla

(object_id, from_id, to_id)

é repetido frequentemente para diferentes PKe TIMESTAMPS. Estou interessado em todas as travessias de borda separadas, portanto, se um objeto com id 1 se mover do vértice 1 para 2, de 2 para 1 e de 1 para 2, quero ter um resultado:

object_id | from_id | to_id
        1 |       1 |     2
        1 |       2 |     1
        1 |       1 |     2

Minha pergunta: como escrever esta consulta?

mysql graph

1 respostas

  1. Best Answer

    As tuplas teriam que ser ordenadas por from_id, to_idde tal forma que, quando from_idou to_idmudasse, cairia em um agrupamento diferente. Eu estava pensando em escrever isso como um procedimento armazenado, mas pensei em algo muito mais intrigante (só tive a ideia ao responder a esta pergunta Atualizar classificação na tabela cerca de 3 horas atrás)

    vou fazer em etapas

    Estágio 1: dados de amostra

    DROP DATABASE IF EXISTS bootvis;
CREATE DATABASE bootvis;
USE bootvis
CREATE TABLE graph_edges
(
    pk int not null auto_increment,
    object_id int default null,
    tm timestamp not null default current_timestamp,
    from_id int,
    to_id int,
    primary key (pk)
);
INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
SELECT SLEEP(2);
INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
SELECT SLEEP(1);
INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2);
INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1);
INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
UPDATE graph_edges SET object_id = 1 WHERE object_id IS NULL;
INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2);
INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1);
SELECT SLEEP(2);
INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
UPDATE graph_edges SET object_id = 2 WHERE object_id IS NULL;
SELECT * FROM graph_edges;

    Estágio 2: dados de amostra carregados

    mysql> DROP DATABASE IF EXISTS bootvis;
Query OK, 1 row affected (0.03 sec)

mysql> CREATE DATABASE bootvis;
Query OK, 1 row affected (0.00 sec)

mysql> USE bootvis
Database changed
mysql> CREATE TABLE graph_edges
    -> (
    ->     pk int not null auto_increment,
    ->     object_id int default null,
    ->     tm timestamp not null default current_timestamp,
    ->     from_id int,
    ->     to_id int,
    ->     primary key (pk)
    -> );
Query OK, 0 rows affected (0.12 sec)

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
Query OK, 4 rows affected (0.05 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> SELECT SLEEP(2);
+----------+
| SLEEP(2) |
+----------+
|        0 |
+----------+
1 row in set (2.00 sec)

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
Query OK, 2 rows affected (0.05 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> SELECT SLEEP(1);
+----------+
| SLEEP(1) |
+----------+
|        0 |
+----------+
1 row in set (1.00 sec)

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2);
Query OK, 2 rows affected (0.07 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1);
Query OK, 8 rows affected (0.08 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
Query OK, 4 rows affected (0.13 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
Query OK, 2 rows affected (0.10 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> UPDATE graph_edges SET object_id = 1 WHERE object_id IS NULL;
Query OK, 22 rows affected (0.06 sec)
Rows matched: 22  Changed: 22  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2);
Query OK, 2 rows affected (0.05 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1),(2,1);
Query OK, 8 rows affected (0.05 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql> SELECT SLEEP(2);
+----------+
| SLEEP(2) |
+----------+
|        0 |
+----------+
1 row in set (2.00 sec)

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
Query OK, 4 rows affected (0.08 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
Query OK, 2 rows affected (0.05 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
Query OK, 4 rows affected (0.06 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
Query OK, 2 rows affected (0.05 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (1,2),(1,2),(1,2),(1,2);
Query OK, 4 rows affected (0.05 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> INSERT INTO graph_edges (from_id,to_id) VALUES (2,1),(2,1);
Query OK, 2 rows affected (0.06 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> UPDATE graph_edges SET object_id = 2 WHERE object_id IS NULL;
Query OK, 28 rows affected (0.06 sec)
Rows matched: 28  Changed: 28  Warnings: 0

mysql> SELECT * FROM graph_edges;
+----+-----------+---------------------+---------+-------+
| pk | object_id | tm                  | from_id | to_id |
+----+-----------+---------------------+---------+-------+
|  1 |         1 | 2012-11-20 17:29:13 |       1 |     2 |
|  2 |         1 | 2012-11-20 17:29:13 |       1 |     2 |
|  3 |         1 | 2012-11-20 17:29:13 |       1 |     2 |
|  4 |         1 | 2012-11-20 17:29:13 |       1 |     2 |
|  5 |         1 | 2012-11-20 17:29:15 |       2 |     1 |
|  6 |         1 | 2012-11-20 17:29:15 |       2 |     1 |
|  7 |         1 | 2012-11-20 17:29:16 |       1 |     2 |
|  8 |         1 | 2012-11-20 17:29:16 |       1 |     2 |
|  9 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 10 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 11 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 12 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 13 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 14 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 15 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 16 |         1 | 2012-11-20 17:29:16 |       2 |     1 |
| 17 |         1 | 2012-11-20 17:29:16 |       1 |     2 |
| 18 |         1 | 2012-11-20 17:29:16 |       1 |     2 |
| 19 |         1 | 2012-11-20 17:29:16 |       1 |     2 |
| 20 |         1 | 2012-11-20 17:29:16 |       1 |     2 |
| 21 |         1 | 2012-11-20 17:29:17 |       2 |     1 |
| 22 |         1 | 2012-11-20 17:29:17 |       2 |     1 |
| 23 |         2 | 2012-11-20 17:29:17 |       1 |     2 |
| 24 |         2 | 2012-11-20 17:29:17 |       1 |     2 |
| 25 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 26 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 27 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 28 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 29 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 30 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 31 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 32 |         2 | 2012-11-20 17:29:17 |       2 |     1 |
| 33 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 34 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 35 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 36 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 37 |         2 | 2012-11-20 17:29:19 |       2 |     1 |
| 38 |         2 | 2012-11-20 17:29:19 |       2 |     1 |
| 39 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 40 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 41 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 42 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 43 |         2 | 2012-11-20 17:29:19 |       2 |     1 |
| 44 |         2 | 2012-11-20 17:29:19 |       2 |     1 |
| 45 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 46 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 47 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 48 |         2 | 2012-11-20 17:29:19 |       1 |     2 |
| 49 |         2 | 2012-11-20 17:29:19 |       2 |     1 |
| 50 |         2 | 2012-11-20 17:29:19 |       2 |     1 |
+----+-----------+---------------------+---------+-------+
50 rows in set (0.00 sec)

mysql>

    Estágio 3: Criar consulta com contadores em execução que mudam quando a tupla é alterada (chame-a de consulta de alteração de tupla)

    SET @r=0;
SET @old_from=-1;
SET @old_to=-1;
SELECT from_id,to_id,
@inc:=((@old_from<>from_id)||(@old_to<>to_id)),
@old_from:=from_id,@old_to:=to_id,
@r:=(@r+@inc) as group_number
FROM graph_edges;

    Etapa 4: execute a consulta de alteração de tupla

    mysql> SET @r=0;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @old_from=-1;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @old_to=-1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT from_id,to_id,
    -> @inc:=((@old_from<>from_id)||(@old_to<>to_id)),
    -> @old_from:=from_id,@old_to:=to_id,
    -> @r:=(@r+@inc) as group_number
    -> FROM graph_edges;
+---------+-------+------------------------------------------------+--------------------+----------------+--------------+
| from_id | to_id | @inc:=((@old_from<>from_id)||(@old_to<>to_id)) | @old_from:=from_id | @old_to:=to_id | group_number |
+---------+-------+------------------------------------------------+--------------------+----------------+--------------+
|       1 |     2 |                                              1 |                  1 |              2 |            1 |
|       1 |     2 |                                              0 |                  1 |              2 |            1 |
|       1 |     2 |                                              0 |                  1 |              2 |            1 |
|       1 |     2 |                                              0 |                  1 |              2 |            1 |
|       2 |     1 |                                              1 |                  2 |              1 |            2 |
|       2 |     1 |                                              0 |                  2 |              1 |            2 |
|       1 |     2 |                                              1 |                  1 |              2 |            3 |
|       1 |     2 |                                              0 |                  1 |              2 |            3 |
|       2 |     1 |                                              1 |                  2 |              1 |            4 |
|       2 |     1 |                                              0 |                  2 |              1 |            4 |
|       2 |     1 |                                              0 |                  2 |              1 |            4 |
|       2 |     1 |                                              0 |                  2 |              1 |            4 |
|       2 |     1 |                                              0 |                  2 |              1 |            4 |
|       2 |     1 |                                              0 |                  2 |              1 |            4 |
|       2 |     1 |                                              0 |                  2 |              1 |            4 |
|       2 |     1 |                                              0 |                  2 |              1 |            4 |
|       1 |     2 |                                              1 |                  1 |              2 |            5 |
|       1 |     2 |                                              0 |                  1 |              2 |            5 |
|       1 |     2 |                                              0 |                  1 |              2 |            5 |
|       1 |     2 |                                              0 |                  1 |              2 |            5 |
|       2 |     1 |                                              1 |                  2 |              1 |            6 |
|       2 |     1 |                                              0 |                  2 |              1 |            6 |
|       1 |     2 |                                              1 |                  1 |              2 |            7 |
|       1 |     2 |                                              0 |                  1 |              2 |            7 |
|       2 |     1 |                                              1 |                  2 |              1 |            8 |
|       2 |     1 |                                              0 |                  2 |              1 |            8 |
|       2 |     1 |                                              0 |                  2 |              1 |            8 |
|       2 |     1 |                                              0 |                  2 |              1 |            8 |
|       2 |     1 |                                              0 |                  2 |              1 |            8 |
|       2 |     1 |                                              0 |                  2 |              1 |            8 |
|       2 |     1 |                                              0 |                  2 |              1 |            8 |
|       2 |     1 |                                              0 |                  2 |              1 |            8 |
|       1 |     2 |                                              1 |                  1 |              2 |            9 |
|       1 |     2 |                                              0 |                  1 |              2 |            9 |
|       1 |     2 |                                              0 |                  1 |              2 |            9 |
|       1 |     2 |                                              0 |                  1 |              2 |            9 |
|       2 |     1 |                                              1 |                  2 |              1 |           10 |
|       2 |     1 |                                              0 |                  2 |              1 |           10 |
|       1 |     2 |                                              1 |                  1 |              2 |           11 |
|       1 |     2 |                                              0 |                  1 |              2 |           11 |
|       1 |     2 |                                              0 |                  1 |              2 |           11 |
|       1 |     2 |                                              0 |                  1 |              2 |           11 |
|       2 |     1 |                                              1 |                  2 |              1 |           12 |
|       2 |     1 |                                              0 |                  2 |              1 |           12 |
|       1 |     2 |                                              1 |                  1 |              2 |           13 |
|       1 |     2 |                                              0 |                  1 |              2 |           13 |
|       1 |     2 |                                              0 |                  1 |              2 |           13 |
|       1 |     2 |                                              0 |                  1 |              2 |           13 |
|       2 |     1 |                                              1 |                  2 |              1 |           14 |
|       2 |     1 |                                              0 |                  2 |              1 |           14 |
+---------+-------+------------------------------------------------+--------------------+----------------+--------------+
50 rows in set (0.00 sec)

mysql>

    Observe que @incmuda apenas quando a tupla muda !!!

    Estágio 5: Coloque a consulta de alteração de tupla em uma subconsulta, extraia os dados necessários da consulta de alteração de tupla, execute GROUP BY group_number (chame-a de consulta de extração duplicada)

    SET @r=0;
SET @old_from=-1;
SET @old_to=-1;
SELECT group_number,from_id,to_id FROM
(
    SELECT from_id,to_id,
    @inc:=((@old_from<>from_id)||(@old_to<>to_id)),
    @old_from:=from_id,@old_to:=to_id,
    @r:=(@r+@inc) as group_number
    FROM graph_edges
) g GROUP BY group_number;

    Etapa 6: executar consulta de extração duplicada

    mysql> SET @r=0;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @old_from=-1;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @old_to=-1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT group_number,from_id,to_id FROM
    -> (
    ->     SELECT from_id,to_id,
    ->     @inc:=((@old_from<>from_id)||(@old_to<>to_id)),
    ->     @old_from:=from_id,@old_to:=to_id,
    ->     @r:=(@r+@inc) as group_number
    ->     FROM graph_edges
    -> ) g GROUP BY group_number;
+--------------+---------+-------+
| group_number | from_id | to_id |
+--------------+---------+-------+
|            1 |       1 |     2 |
|            2 |       2 |     1 |
|            3 |       1 |     2 |
|            4 |       2 |     1 |
|            5 |       1 |     2 |
|            6 |       2 |     1 |
|            7 |       1 |     2 |
|            8 |       2 |     1 |
|            9 |       1 |     2 |
|           10 |       2 |     1 |
|           11 |       1 |     2 |
|           12 |       2 |     1 |
|           13 |       1 |     2 |
|           14 |       2 |     1 |
+--------------+---------+-------+
14 rows in set (0.00 sec)

mysql>

    Estágio 7: (OPCIONAL) Mostrar contagem para cada group_number

    SET @r=0;
SET @old_from=-1;
SET @old_to=-1;
SELECT group_number,from_id,to_id,count(1) group_count FROM
(
    SELECT from_id,to_id,
    @inc:=((@old_from<>from_id)||(@old_to<>to_id)),
    @old_from:=from_id,@old_to:=to_id,
    @r:=(@r+@inc) as group_number
    FROM graph_edges
) g GROUP BY group_number;

    Estágio 8: (OPCIONAL) Execute a consulta Mostrar contagem para cada group_number

    mysql> SET @r=0;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @old_from=-1;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @old_to=-1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT group_number,from_id,to_id,count(1) group_count FROM
    -> (
    ->     SELECT from_id,to_id,
    ->     @inc:=((@old_from<>from_id)||(@old_to<>to_id)),
    ->     @old_from:=from_id,@old_to:=to_id,
    ->     @r:=(@r+@inc) as group_number
    ->     FROM graph_edges
    -> ) g GROUP BY group_number;
+--------------+---------+-------+-------------+
| group_number | from_id | to_id | group_count |
+--------------+---------+-------+-------------+
|            1 |       1 |     2 |           4 |
|            2 |       2 |     1 |           2 |
|            3 |       1 |     2 |           2 |
|            4 |       2 |     1 |           8 |
|            5 |       1 |     2 |           4 |
|            6 |       2 |     1 |           2 |
|            7 |       1 |     2 |           2 |
|            8 |       2 |     1 |           8 |
|            9 |       1 |     2 |           4 |
|           10 |       2 |     1 |           2 |
|           11 |       1 |     2 |           4 |
|           12 |       2 |     1 |           2 |
|           13 |       1 |     2 |           4 |
|           14 |       2 |     1 |           2 |
+--------------+---------+-------+-------------+
14 rows in set (0.00 sec)

mysql>

    Etapa 9: Experimente!!!

    • 5

relate perguntas