Idempotência - Idempotence

Para os conceitos de álgebra, consulte Idempotente (teoria dos anéis) e Matriz idempotente .
Em / Off botões de um trem sinal de destino do painel de controle. Pressionar o botão Ligar (verde) é uma operação idempotente, pois tem o mesmo efeito feito uma ou várias vezes. Da mesma forma, pressionar Off é idempotente.

Idempotência ( Reino Unido : / ˌ do ɪ d ɛ m p oʊ t ən s / , EUA : / ˌ aɪ d ə m - / ) é a propriedade de algumas operações em matemática e ciência computador através do qual possam ser aplicadas várias vezes sem alterar o resultado além da aplicação inicial. O conceito de idempotência surge em vários lugares na álgebra abstrata (em particular, na teoria dos projetores e operadores de fechamento ) e na programação funcional (na qual está conectado à propriedade de transparência referencial ).

O termo foi introduzido por Benjamin Peirce no contexto de elementos de álgebras que permanecem invariáveis ​​quando elevados a uma potência inteira positiva e significa literalmente "(a qualidade de ter) a mesma potência", de idem + potência (mesma + potência).

Definição

Um elemento x de um conjunto S equipado com um operador binário • é considerado idempotente sob • se

x • x = x .

A operação binária • é considerada idempotente se

∀ x ∈ S , x • x = x .

Exemplos

Funções idempotentes

No monóide ( E E , ∘) das funções de um conjunto E para si mesmo com composição de função ∘, os elementos idempotentes são as funções f : E → E tais que f ∘ f = f , ou seja, ∀ x , f ( f ( x )) = f ( x ) (a imagem de cada elemento em E é um ponto fixo de f ). Por exemplo:

Se o conjunto E tem n elementos, que pode distribui-se em k pontos fixos escolhido e n - k pontos não fixos sob F , e, em seguida, k n - k é o número de diferentes funções idempotentes. Portanto, levando em consideração todas as partições possíveis,

é o número total de funções idempotentes possíveis no conjunto. A sequência inteira do número de funções idempotentes conforme dada pela soma acima para n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... começa com 1, 1, 3, 10, 41, 196 , 1057, 6322, 41393,… (sequência A000248 no OEIS ).

Nem a propriedade de ser idempotente nem a de não ser são preservadas na composição de funções. Como um exemplo para o primeiro, f ( x ) = x mod 3 e g ( x ) = max ( x , 5) são ambos idempotentes, mas f ∘ g não é, embora g ∘ f aconteça ser. Como um exemplo para o último, a função de negação ¬ no domínio booleano não é idempotente, mas ¬ ∘ ¬ é. Da mesma forma, a negação unária - () de números reais não é idempotente, mas - () ∘ - () é.

Significado da ciência da computação

Consulte também: Transparência referencial , Reentrante (sub-rotina) e classificação Estável

Em ciência da computação , o termo idempotência pode ter um significado diferente dependendo do contexto em que é aplicado:

Esta é uma propriedade muito útil em muitas situações, pois significa que uma operação pode ser repetida ou repetida quantas vezes forem necessárias sem causar efeitos indesejados. Com operações não idempotentes, o algoritmo pode ter que controlar se a operação já foi executada ou não.

Exemplos de ciência da computação

Uma função que procura o nome e o endereço de um cliente em um banco de dados é normalmente idempotente, pois isso não fará com que o banco de dados seja alterado. Da mesma forma, uma solicitação para alterar o endereço de um cliente para XYZ é normalmente idempotente, porque o endereço final será o mesmo, não importa quantas vezes a solicitação seja enviada. No entanto, uma solicitação do cliente para fazer um pedido normalmente não é idempotente, pois várias solicitações levarão à realização de vários pedidos. Uma solicitação de cancelamento de um pedido específico é idempotente porque não importa quantas solicitações sejam feitas, o pedido permanece cancelado.

Uma sequência de sub-rotinas idempotentes onde pelo menos uma sub-rotina é diferente das outras, no entanto, não é necessariamente idempotente se uma sub-rotina posterior na sequência muda um valor do qual uma sub-rotina anterior depende - idempotência não é fechada sob composição sequencial . Por exemplo, suponha que o valor inicial de uma variável seja 3 e haja uma sequência de sub-rotina que lê a variável, a altera para 5 e a lê novamente. Cada etapa da sequência é idempotente: ambas as etapas de leitura da variável não têm efeitos colaterais e a etapa de alteração da variável para 5 sempre terá o mesmo efeito, não importa quantas vezes seja executada. No entanto, executar a sequência inteira uma vez produz a saída (3, 5), mas executá-la uma segunda vez produz a saída (5, 5), portanto, a sequência não é idempotente. 

int x = 3;
void read() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { read(); change(); read(); }

int main() {
  sequence();  // prints "3\n5\n"
  sequence();  // prints "5\n5\n"
  return 0;
}

No Protocolo de Transferência de Hipertexto (HTTP), idempotência e segurança são os principais atributos que separam os métodos HTTP . Dos principais métodos HTTP, GET, PUT e DELETE devem ser implementados de maneira idempotente de acordo com o padrão, mas POST não precisa ser. GET recupera o estado de um recurso; PUT atualiza o estado de um recurso; e DELETE exclui um recurso. Como no exemplo acima, a leitura de dados geralmente não tem efeitos colaterais, portanto é idempotente (na verdade, nulipotente ). A atualização e exclusão de determinados dados geralmente são idempotentes, desde que a solicitação identifique exclusivamente o recurso e apenas esse recurso novamente no futuro. PUT e DELETE com identificadores únicos reduzem ao simples caso de atribuição a uma variável de um valor ou valor nulo, respectivamente, e são idempotentes pelo mesmo motivo; o resultado final é sempre igual ao resultado da execução inicial, mesmo que a resposta seja diferente.

A violação do requisito de identificação única no armazenamento ou exclusão normalmente causa violação de idempotência. Por exemplo, armazenar ou excluir um determinado conjunto de conteúdo sem especificar um identificador exclusivo: solicitações POST, que não precisam ser idempotentes, muitas vezes não contêm identificadores exclusivos, portanto, a criação do identificador é delegada ao sistema de recebimento, que então cria um novo registro correspondente. Da mesma forma, as solicitações PUT e DELETE com critérios não específicos podem resultar em resultados diferentes dependendo do estado do sistema - por exemplo, uma solicitação para excluir o registro mais recente. Em cada caso, as execuções subsequentes modificarão ainda mais o estado do sistema, de forma que não sejam idempotentes.

No processamento de fluxo de eventos , idempotência se refere à capacidade de um sistema de produzir o mesmo resultado, mesmo se o mesmo arquivo, evento ou mensagem for recebido mais de uma vez.

Em uma arquitetura de carregamento-armazenamento , as instruções que podem causar uma falha de página são idempotentes. Portanto, se ocorrer uma falha de página, o sistema operacional pode carregar a página do disco e simplesmente executar novamente a instrução com falha. Em um processador em que essas instruções não são idempotentes, lidar com falhas de página é muito mais complexo.

Ao reformatar a saída, espera - se que a impressão bonita seja idempotente. Em outras palavras, se a saída já for "bonita", não deve haver nada a fazer para a impressora bonita.

Na arquitetura orientada a serviços (SOA), um processo de orquestração de várias etapas composto inteiramente de etapas idempotentes pode ser reproduzido sem efeitos colaterais se qualquer parte desse processo falhar.

Muitas operações que são idempotentes geralmente têm maneiras de "retomar" um processo se ele for interrompido - maneiras que terminam muito mais rápido do que começar do zero. Por exemplo, retomar uma transferência de arquivo , sincronizar arquivos , criar um build de software , instalar um aplicativo e todas as suas dependências com um gerenciador de pacotes , etc.

Exemplos aplicados

Um botão típico de faixa de pedestres é um exemplo de sistema idempotente

Exemplos aplicados que muitas pessoas podem encontrar em seu dia-a-dia incluem botões de chamada de elevador e botões de faixa de pedestres . A ativação inicial do botão move o sistema para um estado de solicitação, até que a solicitação seja atendida. As ativações subsequentes do botão entre a ativação inicial e o atendimento da solicitação não têm efeito, a menos que o sistema seja projetado para ajustar o tempo para atender à solicitação com base no número de ativações.

Veja também

Referências

Leitura adicional