Consultas, JOINs e Produto Cartesiano em Bash

Introdução

Em tratamento de texto é comum se juntar dois ou mais arquivos com campos semelhantes com a finalidade de extrair alguma informação. Exemplo comum é um campo identificador em um arquivo casar com uma linha de outro arquivo e essa linha ser útil para extrações. Essa situação se assemelha as operações Join’s de um banco de dados e veremos com executá-las em arquivos textos.

Produto cartesiano

Imagine que você tenha dois conjuntos A e B, sendo A={“a1”, “a2”} e B={“b1”, “b2”}. O produto cartesiano, AxB resultará no conjunto: AxB={“a1b1”, “a2b2”, “a2b1”, “a2b2”}. Essa operação faz justamente associar cada elemento de A a todos os elementos de B. Se |A| é o tamanho do conjunto A, e |B| o tamanho do conjunto B, o produto cartesiano resultará em |AxB|=|A|x|B| elementos.

Essa operação será bastante útil pois nos permite obter todas as relações entre as linhas de dois ou mais arquivos. Para implementar isso em bash veja o código abaixo (referência [1] + algumas modificações próprias)

#!/bin/bash
# Qua Dez  7 21:17:24 BRST 2016
# [cartesian.sh]

foreachline() {

    _foreachline() {
        DELIM=' '

        if [ $#  -lt 2 ]; then
            printf "$1\n"
            return
        fi

        local prefix=$1
        local file=$2
        shift 2

        while read line; do
            _foreachline "$prefix$line$DELIM" $*
        done <$file
    }

    _foreachline "" $*
}

foreachline $*

Salve como cartesian.sh e digite:

$ chmod +x cartesian.sh

Para testá-lo, vamos considerar dois arquivos simples: ids.txt e acessos.txt. Os dois arquivos simulam um log de acesso onde o primeiro associa um id numérico a um site e o segundo arquivo contém o número de acessos daquele site em um dia da semana.

$ cat ids.txt
1 www.google.com
2 www.facebook.com
3 www.youtube.com
4 www.slashdot.com
5 www.reddit.com

$ cat acessos.txt
1 122 119 88 80 111 199 67
2 13 14 18 80 66 77 11
3 4 6 11 18 6 8 19
4 20 11 17 80 18 10 21
5 40 41 30 20 22 21 11

O produto cartesiano é dado por:

$ ./cartesian.sh ids.txt acessos.txt
1 www.google.com 1 122 119 88 80 111 199 67 
1 www.google.com 2 13 14 18 80 66 77 11 
1 www.google.com 3 4 6 11 18 6 8 19 
1 www.google.com 4 20 11 17 80 18 10 21 
1 www.google.com 5 40 41 30 20 22 21 11 
2 www.facebook.com 1 122 119 88 80 111 199 67 
2 www.facebook.com 2 13 14 18 80 66 77 11 
2 www.facebook.com 3 4 6 11 18 6 8 19 
2 www.facebook.com 4 20 11 17 80 18 10 21 
2 www.facebook.com 5 40 41 30 20 22 21 11 
3 www.youtube.com 1 122 119 88 80 111 199 67 
3 www.youtube.com 2 13 14 18 80 66 77 11 
3 www.youtube.com 3 4 6 11 18 6 8 19 
3 www.youtube.com 4 20 11 17 80 18 10 21 
3 www.youtube.com 5 40 41 30 20 22 21 11 
4 www.slashdot.com 1 122 119 88 80 111 199 67 
4 www.slashdot.com 2 13 14 18 80 66 77 11 
4 www.slashdot.com 3 4 6 11 18 6 8 19 
4 www.slashdot.com 4 20 11 17 80 18 10 21 
4 www.slashdot.com 5 40 41 30 20 22 21 11 
5 www.reddit.com 1 122 119 88 80 111 199 67 
5 www.reddit.com 2 13 14 18 80 66 77 11 
5 www.reddit.com 3 4 6 11 18 6 8 19 
5 www.reddit.com 4 20 11 17 80 18 10 21 
5 www.reddit.com 5 40 41 30 20 22 21 11 

Semanticamente temos linhas inválidas, pois o acesso de determinado site está associado a outro, isso é, algumas linhas possuem identificadores que não se casam. Podemos retirar essas linhas inválidas realizando uma operação JOIN, que nada mais é que um produto cartesiano com condição de junção.

Vamos mostrar o endereço do site seguido de seus acessos:

$ ./cartesian.sh ids.txt acessos.txt | awk '$1 == $3 {$3=""; print}'
1 www.google.com  122 119 88 80 111 199 67
2 www.facebook.com  13 14 18 80 66 77 11
3 www.youtube.com  4 6 11 18 6 8 19
4 www.slashdot.com  20 11 17 80 18 10 21
5 www.reddit.com  40 41 30 20 22 21 11

Se os identificadores são iguais ($1 igual a $3) então imprima toda a linha ignorando o terceiro campo (para não mostrar o id duas vezes).

O exemplo acima pode ser reescrito usando o comando join:

$ join ids.txt acessos.txt
1 www.google.com  122 119 88 80 111 199 67
2 www.facebook.com  13 14 18 80 66 77 11
3 www.youtube.com  4 6 11 18 6 8 19
4 www.slashdot.com  20 11 17 80 18 10 21
5 www.reddit.com  40 41 30 20 22 21 11

Por padrão ele iguala o primeiro campo de cada arquivo, mas esse comportamento pode ser mudado através das opções -1 e -2. O comando join só funciona para dois arquivos de entrada e eles devem estar ordenados.

Além da condição de junção, podemos realizar filtros nas linhas (simular um where) e também selecionar (ou projetar) colunas. O seguinte exemplo mostra os endereços que possuem acessos no primeiro dia da semana menor que o segundo (condição: $4 < $5).

$ ./cartesian.sh ids.txt acessos.txt | awk '($1 == $3) && ($4 < $5) {print $2}'
www.facebook.com
www.youtube.com
www.reddit.com

Quais pares de sites possuem o mesmo número de acesso no quarto dia da semana?

$ ./cartesian.sh ids.txt ids.txt acessos.txt acessos.txt | awk '($1 == $5) && ($3 == $13) && ($1 > $3) && ($9 == $17) { print $2, $4 }'
www.facebook.com www.google.com
www.slashdot.com www.google.com
www.slashdot.com www.facebook.com

É preciso repetir os arquivos de entrada para se obter os nomes em cada par. As duas primeiras condições do awk associam as linhas dos arquivos de acessos aos respectivos identificadores. A terceira condição impede que o mesmo site apareça duas vezes no par e a última condição iguala o quarto dia da semana. A ideia geral é fazer o produto cartesiano e igualar as colunas correspondentes e depois usar alguma condição mais específica.

Sabendo usar a linguagem do awk podemos criar scripts mais interessantes. O exemplo abaixo mostra o endereço do site seguido da soma total de seus acessos:

$ ./cartesian.sh ids.txt acessos.txt | awk '(sum=$4+$5+$6+$7+$8+$9+$10) && $1 == $3 {print $2, sum}'
www.google.com 786
www.facebook.com 279
www.youtube.com 72
www.slashdot.com 177
www.reddit.com 185

LEFT/RIGHT/FULL OUTER JOIN

Imagine que um identificador em ids.txt não case com alguma linha em acessos.txt — para os exemplos mostrados, essa linha seria suprimida. Existem casos em que recuperar essas linhas não casadas (ou órfãs) é interessante porque elas contêm informações do tipo “não está associado a”. Um LEFT OUTER JOIN, em banco de dados, é um JOIN que também mostra as linhas que não casaram do arquivo à esquerda. Similarmente, o RIGHT OUTER JOIN mostra linhas que não casaram do arquivo à direita.  O FULL OUTER JOIN mostra todas as linhas casadas e todas as órfãs.

Vamos inserir linhas em nossos arquivos.

$ echo “6 daemoniolabs.wordpress.com” >> ids.txt
$ echo “10 20 21 22 23 24 25 26” >> acessos.txt

De cara vemos que há dados inconsistentes, pois não existe id 6 no arquivo acessos.txt e também não existe id 10 no arquivo ids.txt.

O uso do join torna o tratamento mais conveniente:

# join (natural)
$ join ids.txt acessos.txt
1 www.google.com 122 119 88 80 111 199 67
2 www.facebook.com 13 14 18 80 66 77 11
3 www.youtube.com 4 6 11 18 6 8 19
4 www.slashdot.com 20 11 17 80 18 10 21
5 www.reddit.com 40 41 30 20 22 21 11

# left outer join
$ join -a 1 ids.txt acessos.txt
1 www.google.com 122 119 88 80 111 199 67
2 www.facebook.com 13 14 18 80 66 77 11
3 www.youtube.com 4 6 11 18 6 8 19
4 www.slashdot.com 20 11 17 80 18 10 21
5 www.reddit.com 40 41 30 20 22 21 11
6 daemoniolabs.wordpress.com

# right outer join
$ join -a 2 ids.txt acessos.txt
1 www.google.com 122 119 88 80 111 199 67
2 www.facebook.com 13 14 18 80 66 77 11
3 www.youtube.com 4 6 11 18 6 8 19
4 www.slashdot.com 20 11 17 80 18 10 21
5 www.reddit.com 40 41 30 20 22 21 11
10 20 21 22 23 24 25 26

# full outer join
$ join -a 1 -a 2 ids.txt acessos.txt
1 www.google.com 122 119 88 80 111 199 67
2 www.facebook.com 13 14 18 80 66 77 11
3 www.youtube.com 4 6 11 18 6 8 19
4 www.slashdot.com 20 11 17 80 18 10 21
5 www.reddit.com 40 41 30 20 22 21 11
10 20 21 22 23 24 25 26
6 daemoniolabs.wordpress.com

Destaquei em negrito as linhas órfãs. A opção -a do join mostra linhas órfãs, sendo que o argumento 1 se refere às linhas do primeiro arquivo e o 2 linhas do segundo. Vale lembrar que o join só trabalha com arquivos ordenados, dois arquivos de entradas e com a união de uma só coluna.

Se for útil, podemos projetar colunas com a opção -o e usar a palavra “NULL” na coluna omitida pela linha órfã:

$ join -a 1 ids.txt acessos.txt -o 1.2,2.3 -e NULL
www.google.com 119
www.facebook.com 14
www.youtube.com 6
www.slashdot.com 11
www.reddit.com 41
daemoniolabs.wordpress.com NULL

A opção -o indica o formato de saída, sendo que 1.2 se refere a segunda coluna do arquivo 1 e 2.3 a terceira coluna do arquivo 2. A opção -e coloca a palavra NULL nas colunas vazias.

O seguinte comando mostra a linha do site que ninguém acessa:

$ join -v 1 ids.txt acessos.txt
6 daemoniolabs.wordpress.com

A opção -v é semelhante a -a porém filtra as linhas casadas, mostrando somente as linhas não pareadas (ou órfãs).

Ou, através do awk, selecionando linhas que possuem colunas vazias:

$ join -a 1 ids.txt acessos.txt | awk '$3=="" { print $2 }'
daemoniolabs.wordpress.com

No exemplo acima projetamos somente o endereço do site. Por fim, o exemplo abaixo mostra o ID que não está cadastrado:

$ join -v 2 ids.txt acessos.txt -o 2.1
10

Quando usar?

Se comandos do bash simulam algumas consultas em banco de dados, então quando devemos usar um ou outro? Se a consulta for simples e o tamanho do produto cartesiano for pequeno então vale a pena executar via bash, pois assim pouparemos tempo por não precisar de criar um banco de dados do zero. Arquivos relativamente maiores poderão ainda ser usados se a consulta for feita usando o comando join.
Por outro lado, problemas complexos, grandes e com várias consultas são melhores tratados em um SGDB já que ele fornece todo um arcabouço otimizado para tratar os dados e as consultas.

Conclusão

Através do produto cartesiano e do comando join, podemos simular consultas específicas de banco de dados no terminal. Tal recurso pode ser utilizado no lugar de um SGDB quando o problema for tratável — não muito grande ou complexo — pois poupa-se tempo para se criar um banco de dados desde o zero.

Referências

Cartesian product of two files as sets of lines in GNU Linux by stackoverflow (http://archive.is/nhpVI) (Acessado em: Dezembro/2016)
http://stackoverflow.com/questions/1620946/cartesian-product-of-two-files-as-sets-of-lines-in-gnu-linux

Unix-Join by shapeshed (http://archive.is/ZJpxK) (Acessado em: Dezembro/2016)
https://shapeshed.com/unix-join/

O comando join by vivaolinux (http://archive.is/Cbo9M)  (Acessado em: Dezembro/2016)
https://www.vivaolinux.com.br/dica/O-comando-join

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s