Como diferem chaves primárias e estrangeiras no PostgreSQL?

A primária identifica linhas por valores únicos e não NULL. A estrangeira exige correspondência com valores da chave referenciada, segundo suas regras de NULL. Pode referenciar uma chave UNIQUE elegível ou uma primária da mesma tabela ou de outra.

Porque é que quicksort pode levar Θ(n²) e como a aleatoriedade ajuda?

Partições repetidamente desequilibradas, como escolher sempre a menor chave entre chaves distintas, causam trabalho quadrático. Com chaves distintas ou tratamento adequado de duplicados, pivôs aleatórios dão tempo esperado O(n log n). A mediana de três é uma heurística útil, não uma garantia para o pior caso.

Porque é que a programação dinâmica é útil em muitos problemas de otimização?

A subestrutura ótima permite expressar um ótimo por meio de ótimos dos subproblemas. Quando eles se sobrepõem, guardar as respostas evita trabalho repetido. Os estados e a recorrência precisam representar corretamente o problema original.

Quando counting sort ou radix sort podem levar tempo linear?

Counting sort custa O(n+k) para n chaves num intervalo de k valores. Radix sort com d passadas estáveis por dígitos e base b custa O(d(n+b)). Só são lineares quando esses parâmetros permitem; exploram a estrutura das chaves além das comparações.

O que é uma leitura fantasma e como evitá-la?

Repetir uma consulta com predicado encontra outro conjunto de linhas correspondentes após alterações confirmadas por outra transação. SERIALIZABLE a impede no modelo definido na norma; algumas implementações, como REPEATABLE READ do PostgreSQL, também a impedem num nível inferior.

Como INNER JOIN e LEFT JOIN diferem?

INNER JOIN devolve combinações de linhas que satisfazem a condição de junção. LEFT JOIN também mantém cada linha esquerda sem correspondência, com NULL nas colunas direitas. Várias correspondências podem produzir várias linhas por linha esquerda.

Como funciona a ordenação por inserção e de que depende seu custo em dados quase ordenados?

Ela insere cada item num prefixo ordenado. A versão usual com deslocamentos ou trocas adjacentes leva Θ(n+I), sendo I o número de inversões. É linear quando I=O(n); uma entrada pequena não muda o pior caso Θ(n²).

O que é uma leitura não repetível e qual é o nível da norma que a impede?

Ao reler uma linha, seus dados mudaram ou ela desapareceu após outra transação confirmar uma atualização ou eliminação. REPEATABLE READ e SERIALIZABLE impedem essa anomalia.

Como o WAL apoia a durabilidade do PostgreSQL com commit síncrono normal?

Os registos necessários chegam ao armazenamento durável antes da confirmação do commit e antes da gravação das páginas alteradas. Após uma falha, o WAL pode reproduzir alterações ausentes nas páginas. O commit assíncrono pode perder transações recentes já confirmadas.

Como se comparam matriz de adjacência e listas de adjacência comuns?

Com V vértices e E arestas, a matriz usa O(V²) espaço e verifica uma aresta em O(1). As listas usam O(V+E); procurar (u,v) numa lista não ordenada custa O(deg(u)), sendo deg(u) o comprimento dessa lista.

Como funciona o merge sort habitual para vetores e quais são os seus custos?

Ordena recursivamente duas metades e intercala-as em tempo linear. A versão habitual leva Θ(n log n) tempo e O(n) espaço auxiliar, supondo comparações de tempo constante.

Como Bellman–Ford trata arestas negativas e detecta um ciclo negativo alcançável?

Relaxa todas as arestas até V−1 vezes. Uma melhoria adicional a partir de um vértice alcançável revela um ciclo negativo alcançável da origem. O pior caso custa O(VE); vértices alcançáveis desse ciclo não têm custo mínimo finito.

O que a pesquisa binária exige e quando leva O(log n)?

Ela divide repetidamente o intervalo de pesquisa ao meio em dados ordenados segundo o critério de comparação. Num vetor com acesso por índice O(1) e comparações de tempo constante, pesquisar entre n elementos custa O(log n).

O que é uma leitura suja e qual é o primeiro nível de isolamento da norma que a impede?

Ler dados não confirmados de outra transação, independentemente de esta ser depois anulada. READ COMMITTED e os níveis superiores definidos na norma proíbem leituras sujas.

Quais são as duas fases do bloqueio em duas fases (2PL)?

Crescimento: adquirir bloqueios sem os libertar. Encolhimento: libertar bloqueios sem adquirir novos. Com bloqueios adequados para leituras e escritas conflitantes, 2PL garante escalonamentos serializáveis por conflito, mas bloqueios mútuos continuam possíveis.

O que torna estável um algoritmo de ordenação?

Itens com chaves iguais mantêm sua ordem relativa original. Merge sort pode ser estável se escolher primeiro o item da esquerda em empates; o quicksort usual no próprio vetor geralmente é instável. A estabilidade depende da implementação.

Como a pesquisa em largura encontra caminhos mínimos num grafo não ponderado?

BFS usa uma fila FIFO e explora por distância em número de arestas. Marcar um vértice ao inseri-lo na fila evita visitas repetidas. O primeiro caminho descoberto até um vértice alcançável tem o menor número de arestas.

Como WHERE e HAVING diferem numa consulta agrupada?

WHERE filtra linhas de entrada antes do agrupamento. HAVING filtra os grupos resultantes e pode usar condições com agregações, como COUNT(*)>1.

Como um algoritmo guloso difere da programação dinâmica?

O guloso assume uma escolha local e exige prova de que essas escolhas preservam um ótimo. A programação dinâmica compara alternativas por uma recorrência e reutiliza resultados. O ótimo global exige modelo e recorrência corretos, não apenas o nome “DP”.

Qual é a recorrência para o comprimento da maior subsequência comum (LCS)?

L[i,j] é o comprimento da LCS de prefixos de comprimentos i,j. L[0,j]=L[i,0]=0. Se os últimos caracteres coincidem, L[i,j]=1+L[i−1,j−1]; senão, L[i,j]=max(L[i−1,j],L[i,j−1]). A tabela completa usa O(mn) tempo e espaço.

Qual é uma ordem lógica simplificada de processamento de uma consulta SQL SELECT?

Sem CTEs, funções de janela nem operações de conjuntos: FROM/JOIN → WHERE → GROUP BY e agregações → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. É um modelo lógico, não necessariamente a ordem física escolhida pelo otimizador.

O que exigem a primeira, segunda e terceira formas normais?

1FN: valores atómicos. 2FN: 1FN e nenhum atributo não primo depende de uma parte própria de qualquer chave candidata. 3FN: 1FN e, em toda dependência não trivial X→A, X é superchave ou A é primo. Um atributo primo pertence a alguma chave candidata.

O que é uma ordem topológica e como o algoritmo de Kahn a encontra?

Num DAG, cada aresta u→v coloca u antes de v. Retira-se repetidamente um vértice de grau de entrada zero, removendo suas arestas de saída e colocando na fila os novos vértices de grau zero. Se saírem menos de V vértices, há um ciclo dirigido.

Como diferem índices clustered e nonclustered de armazenamento por linhas no SQL Server?

O clustered armazena as linhas em ordem de chave, então há no máximo um por tabela. O nonclustered possui suas próprias chaves e localizadores de linhas e pode incluir outras colunas. Termos e detalhes de armazenamento variam entre sistemas.

Quando Dijkstra é válido e qual é um custo usual com heap?

Com pesos não negativos, ele fixa repetidamente o vértice com menor distância provisória. Uma implementação com listas de adjacência e heap binário mínimo leva O((V+E) log V). Arestas negativas podem invalidar o argumento de distância definitiva.

O que significam as propriedades ACID de uma transação?

Atomicidade: todos os efeitos ou nenhum. Consistência: transações corretas preservam restrições e invariantes da aplicação. Isolamento: a concorrência respeita o nível escolhido. Durabilidade: efeitos confirmados sobrevivem às falhas cobertas pelas garantias configuradas.

Como é que Kruskal e Prim constroem uma árvore geradora mínima?

Num grafo conexo, não dirigido e ponderado, Kruskal considera arestas por peso crescente e usa Union–Find para rejeitar ciclos. Prim expande uma árvore escolhendo uma aresta de peso mínimo que conecta a árvore a um vértice externo.

Como diferem memoização e programação dinâmica de baixo para cima?

A memoização avalia subproblemas a pedido, geralmente por recursão, e guarda os resultados. A abordagem de baixo para cima avalia estados quando suas dependências já estão disponíveis, normalmente preenchendo uma tabela.

Quais são o tempo no pior caso e o espaço extra do heapsort no próprio vetor?

Construir o heap custa O(n); as extrações somam O(n log n). Com descida iterativa no vetor de entrada, heapsort leva O(n log n) no pior caso e usa O(1) espaço extra.

Como a pesquisa em profundidade detecta um ciclo num grafo dirigido?

DFS aprofunda a exploração usando recursão ou uma pilha explícita. Uma aresta para um vértice ainda ativo no caminho DFS atual é de retorno e comprova um ciclo dirigido; apontar para qualquer vértice já visitado não basta.

Porque é que árvores B+ são úteis para índices e consultas por intervalo?

A alta ramificação mantém a árvore baixa e reduz acessos a páginas. Chaves ordenadas e folhas encadeadas permitem percorrer intervalos. Índices hash visam pesquisas por igualdade e não oferecem por si só o mesmo acesso ordenado por intervalo.

Qual é a recorrência habitual da mochila 0/1 com capacidade inteira W?

D[i,w] é o melhor valor usando os primeiros i itens, capacidade w e pesos inteiros positivos wᵢ. D[0,w]=0. Se wᵢ>w, copia-se D[i−1,w]; senão, usa-se max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). O tempo O(NW) é pseudopolinomial.

Algoritmos, grafos, programação dinâmica e bases de dados relacionais

32 cartões de revisão universitária sobre ordenação, algoritmos de grafos, programação dinâmica, SQL, índices e transações. Requer programação básica, estruturas de dados e SQL.

Level: basic
Languages: pt → pt
Cards: 32
Markdown: Algoritmos, grafos, programação dinâmica e bases de dados relacionais (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Como diferem chaves primárias e estrangeiras no PostgreSQL?	A primária identifica linhas por valores únicos e não NULL. A estrangeira exige correspondência com valores da chave referenciada, segundo suas regras de NULL. Pode referenciar uma chave UNIQUE elegível ou uma primária da mesma tabela ou de outra.
2	Porque é que quicksort pode levar Θ(n²) e como a aleatoriedade ajuda?	Partições repetidamente desequilibradas, como escolher sempre a menor chave entre chaves distintas, causam trabalho quadrático. Com chaves distintas ou tratamento adequado de duplicados, pivôs aleatórios dão tempo esperado O(n log n). A mediana de três é uma heurística útil, não uma garantia para o pior caso.
3	Porque é que a programação dinâmica é útil em muitos problemas de otimização?	A subestrutura ótima permite expressar um ótimo por meio de ótimos dos subproblemas. Quando eles se sobrepõem, guardar as respostas evita trabalho repetido. Os estados e a recorrência precisam representar corretamente o problema original.
4	Quando counting sort ou radix sort podem levar tempo linear?	Counting sort custa O(n+k) para n chaves num intervalo de k valores. Radix sort com d passadas estáveis por dígitos e base b custa O(d(n+b)). Só são lineares quando esses parâmetros permitem; exploram a estrutura das chaves além das comparações.
5	O que é uma leitura fantasma e como evitá-la?	Repetir uma consulta com predicado encontra outro conjunto de linhas correspondentes após alterações confirmadas por outra transação. SERIALIZABLE a impede no modelo definido na norma; algumas implementações, como REPEATABLE READ do PostgreSQL, também a impedem num nível inferior.
6	Como INNER JOIN e LEFT JOIN diferem?	INNER JOIN devolve combinações de linhas que satisfazem a condição de junção. LEFT JOIN também mantém cada linha esquerda sem correspondência, com NULL nas colunas direitas. Várias correspondências podem produzir várias linhas por linha esquerda.
7	Como funciona a ordenação por inserção e de que depende seu custo em dados quase ordenados?	Ela insere cada item num prefixo ordenado. A versão usual com deslocamentos ou trocas adjacentes leva Θ(n+I), sendo I o número de inversões. É linear quando I=O(n); uma entrada pequena não muda o pior caso Θ(n²).
8	O que é uma leitura não repetível e qual é o nível da norma que a impede?	Ao reler uma linha, seus dados mudaram ou ela desapareceu após outra transação confirmar uma atualização ou eliminação. REPEATABLE READ e SERIALIZABLE impedem essa anomalia.
9	Como o WAL apoia a durabilidade do PostgreSQL com commit síncrono normal?	Os registos necessários chegam ao armazenamento durável antes da confirmação do commit e antes da gravação das páginas alteradas. Após uma falha, o WAL pode reproduzir alterações ausentes nas páginas. O commit assíncrono pode perder transações recentes já confirmadas.
10	Como se comparam matriz de adjacência e listas de adjacência comuns?	Com V vértices e E arestas, a matriz usa O(V²) espaço e verifica uma aresta em O(1). As listas usam O(V+E); procurar (u,v) numa lista não ordenada custa O(deg(u)), sendo deg(u) o comprimento dessa lista.
11	Como funciona o merge sort habitual para vetores e quais são os seus custos?	Ordena recursivamente duas metades e intercala-as em tempo linear. A versão habitual leva Θ(n log n) tempo e O(n) espaço auxiliar, supondo comparações de tempo constante.
12	Como Bellman–Ford trata arestas negativas e detecta um ciclo negativo alcançável?	Relaxa todas as arestas até V−1 vezes. Uma melhoria adicional a partir de um vértice alcançável revela um ciclo negativo alcançável da origem. O pior caso custa O(VE); vértices alcançáveis desse ciclo não têm custo mínimo finito.
13	O que a pesquisa binária exige e quando leva O(log n)?	Ela divide repetidamente o intervalo de pesquisa ao meio em dados ordenados segundo o critério de comparação. Num vetor com acesso por índice O(1) e comparações de tempo constante, pesquisar entre n elementos custa O(log n).
14	O que é uma leitura suja e qual é o primeiro nível de isolamento da norma que a impede?	Ler dados não confirmados de outra transação, independentemente de esta ser depois anulada. READ COMMITTED e os níveis superiores definidos na norma proíbem leituras sujas.
15	Quais são as duas fases do bloqueio em duas fases (2PL)?	Crescimento: adquirir bloqueios sem os libertar. Encolhimento: libertar bloqueios sem adquirir novos. Com bloqueios adequados para leituras e escritas conflitantes, 2PL garante escalonamentos serializáveis por conflito, mas bloqueios mútuos continuam possíveis.
16	O que torna estável um algoritmo de ordenação?	Itens com chaves iguais mantêm sua ordem relativa original. Merge sort pode ser estável se escolher primeiro o item da esquerda em empates; o quicksort usual no próprio vetor geralmente é instável. A estabilidade depende da implementação.
17	Como a pesquisa em largura encontra caminhos mínimos num grafo não ponderado?	BFS usa uma fila FIFO e explora por distância em número de arestas. Marcar um vértice ao inseri-lo na fila evita visitas repetidas. O primeiro caminho descoberto até um vértice alcançável tem o menor número de arestas.
18	Como WHERE e HAVING diferem numa consulta agrupada?	WHERE filtra linhas de entrada antes do agrupamento. HAVING filtra os grupos resultantes e pode usar condições com agregações, como COUNT(*)>1.
19	Como um algoritmo guloso difere da programação dinâmica?	O guloso assume uma escolha local e exige prova de que essas escolhas preservam um ótimo. A programação dinâmica compara alternativas por uma recorrência e reutiliza resultados. O ótimo global exige modelo e recorrência corretos, não apenas o nome “DP”.
20	Qual é a recorrência para o comprimento da maior subsequência comum (LCS)?	L[i,j] é o comprimento da LCS de prefixos de comprimentos i,j. L[0,j]=L[i,0]=0. Se os últimos caracteres coincidem, L[i,j]=1+L[i−1,j−1]; senão, L[i,j]=max(L[i−1,j],L[i,j−1]). A tabela completa usa O(mn) tempo e espaço.
21	Qual é uma ordem lógica simplificada de processamento de uma consulta SQL SELECT?	Sem CTEs, funções de janela nem operações de conjuntos: FROM/JOIN → WHERE → GROUP BY e agregações → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. É um modelo lógico, não necessariamente a ordem física escolhida pelo otimizador.
22	O que exigem a primeira, segunda e terceira formas normais?	1FN: valores atómicos. 2FN: 1FN e nenhum atributo não primo depende de uma parte própria de qualquer chave candidata. 3FN: 1FN e, em toda dependência não trivial X→A, X é superchave ou A é primo. Um atributo primo pertence a alguma chave candidata.
23	O que é uma ordem topológica e como o algoritmo de Kahn a encontra?	Num DAG, cada aresta u→v coloca u antes de v. Retira-se repetidamente um vértice de grau de entrada zero, removendo suas arestas de saída e colocando na fila os novos vértices de grau zero. Se saírem menos de V vértices, há um ciclo dirigido.
24	Como diferem índices clustered e nonclustered de armazenamento por linhas no SQL Server?	O clustered armazena as linhas em ordem de chave, então há no máximo um por tabela. O nonclustered possui suas próprias chaves e localizadores de linhas e pode incluir outras colunas. Termos e detalhes de armazenamento variam entre sistemas.
25	Quando Dijkstra é válido e qual é um custo usual com heap?	Com pesos não negativos, ele fixa repetidamente o vértice com menor distância provisória. Uma implementação com listas de adjacência e heap binário mínimo leva O((V+E) log V). Arestas negativas podem invalidar o argumento de distância definitiva.
26	O que significam as propriedades ACID de uma transação?	Atomicidade: todos os efeitos ou nenhum. Consistência: transações corretas preservam restrições e invariantes da aplicação. Isolamento: a concorrência respeita o nível escolhido. Durabilidade: efeitos confirmados sobrevivem às falhas cobertas pelas garantias configuradas.
27	Como é que Kruskal e Prim constroem uma árvore geradora mínima?	Num grafo conexo, não dirigido e ponderado, Kruskal considera arestas por peso crescente e usa Union–Find para rejeitar ciclos. Prim expande uma árvore escolhendo uma aresta de peso mínimo que conecta a árvore a um vértice externo.
28	Como diferem memoização e programação dinâmica de baixo para cima?	A memoização avalia subproblemas a pedido, geralmente por recursão, e guarda os resultados. A abordagem de baixo para cima avalia estados quando suas dependências já estão disponíveis, normalmente preenchendo uma tabela.
29	Quais são o tempo no pior caso e o espaço extra do heapsort no próprio vetor?	Construir o heap custa O(n); as extrações somam O(n log n). Com descida iterativa no vetor de entrada, heapsort leva O(n log n) no pior caso e usa O(1) espaço extra.
30	Como a pesquisa em profundidade detecta um ciclo num grafo dirigido?	DFS aprofunda a exploração usando recursão ou uma pilha explícita. Uma aresta para um vértice ainda ativo no caminho DFS atual é de retorno e comprova um ciclo dirigido; apontar para qualquer vértice já visitado não basta.
31	Porque é que árvores B+ são úteis para índices e consultas por intervalo?	A alta ramificação mantém a árvore baixa e reduz acessos a páginas. Chaves ordenadas e folhas encadeadas permitem percorrer intervalos. Índices hash visam pesquisas por igualdade e não oferecem por si só o mesmo acesso ordenado por intervalo.
32	Qual é a recorrência habitual da mochila 0/1 com capacidade inteira W?	D[i,w] é o melhor valor usando os primeiros i itens, capacidade w e pesos inteiros positivos wᵢ. D[0,w]=0. Se wᵢ>w, copia-se D[i−1,w]; senão, usa-se max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). O tempo O(NW) é pseudopolinomial.