Algoritmo GYO

El algoritmo GYO ^{[ 1 ]} es un algoritmo que se aplica a hipergrafos . El algoritmo toma como entrada un hipergrafo y determina si este es α-acíclico . De ser así, calcula una descomposición del hipergrafo.

El algoritmo fue propuesto en 1979 por Graham e independientemente por Yu y Özsoyoğlu , de ahí su nombre.

Un hipergrafo es una generalización de un grafo . Formalmente, un hipergrafo${\displaystyle H=(V,E)}$Consta de un conjunto de vértices V y de un conjunto E de hiperaristas , cada una de las cuales es un subconjunto de los vértices V. Dado un hipergrafo, podemos definir su grafo primal como el grafo no dirigido definido sobre el mismo conjunto de vértices, en el que colocamos una arista entre cualesquiera dos vértices que aparecen juntos en alguna hiperarista.

Un hipergrafo H es α-acíclico si satisface dos condiciones: ser cordal y ser conforme. Más precisamente, decimos que H es cordal si su grafo primal es un grafo cordal . Decimos que H es conforme si, para cada camarilla del grafo primal, existe una hiperarista de H que contiene todos los vértices de la camarilla.

El algoritmo GYO toma como entrada un hipergrafo y determina si es α-acíclico en este sentido.

El algoritmo elimina iterativamente las llamadas " orejas " del hipergrafo, hasta que este queda completamente descompuesto.

Formalmente, decimos que una hiperarista e de un hipergrafo${\displaystyle H}$Se considera una oreja si se cumple alguna de las dos condiciones siguientes:

• ${\displaystyle e}$está aislado , es decir, para cada otro hiperborde${\displaystyle e'}$, tenemos${\displaystyle e\cap e'=\emptyset }$;
• ${\displaystyle e}$está casi cubierto por otro hiperborde, es decir, existe otro hiperborde${\displaystyle f}$de tal manera que todos los vértices en${\displaystyle e\setminus f}$ocurren solo en${\displaystyle e}$.

En particular, cada arista que es un subconjunto de otra arista es una oreja.

El algoritmo GYO procede entonces de la siguiente manera:

• Encuentra una oreja e en H.
• Elimina e y elimina todos los vértices de H que estén solo en e .

Si el algoritmo elimina con éxito todos los vértices, entonces el hipergrafo es α-acíclico. De lo contrario, si el algoritmo llega a un hipergrafo no vacío que no tiene orejas, entonces el hipergrafo original no era α-acíclico.

El algoritmo GYO termina en el hipergrafo vacío si y solo si H es${\displaystyle \alpha }$-acíclico

Supongamos primero que el algoritmo GYO termina en el hipergrafo vacío, sea${\displaystyle e_{1},\ldots ,e_{m}}$sea ​​la secuencia de orejas que ha encontrado, y deje que${\displaystyle H_{0},\ldots ,H_{m}}$la secuencia de hipergrafos obtenidos (en particular${\displaystyle H_{0}=H}$y${\displaystyle H_{m}}$es el hipergrafo vacío). Está claro que${\displaystyle H_{m}}$, el hipergrafo vacío, es${\displaystyle \alpha }$-acíclico. Entonces se puede comprobar que, si${\displaystyle H_{n}}$es${\displaystyle \alpha }$-acíclico entonces${\displaystyle H_{n-1}}$también lo es${\displaystyle \alpha }$-acíclico. Esto implica que${\displaystyle H_{0}}$De hecho, es así.${\displaystyle \alpha }$-acíclico.

Para la otra dirección, suponiendo que${\displaystyle H}$es${\displaystyle \alpha }$-acíclico, se puede demostrar que${\displaystyle H}$tiene una oreja${\displaystyle e}$. ^{[ 2 ]} Dado que al eliminar esta oreja se obtiene un hipergrafo que sigue siendo acíclico, podemos continuar este proceso hasta que el hipergrafo quede vacío.

• Abiteboul, Serge; Hull, Richard; Vianu, Victor (2 de diciembre de 1994). Fundamentos de las bases de datos: El nivel lógico (PDF) . Reading, Mass.: Pearson. ISBN 978-0-201-53771-0.Véase el algoritmo 6.4.4.
• Koutris, París. "Lección 4: Consultas conjuntivas acíclicas" (PDF) .
• Arenas, Marcelo; Barceló, Pablo; Libkin, Leonidas; Martens, Wim; Pieris, Andreas (19 de agosto de 2022). "Capítulo 18". Teoría de Bases de Datos (Versión Preliminar) .
• Tziavelis, Giorgos; Gatterbauer, Wolfgang; Riedewald, Mirek (2022). "Hacia sistemas de gestión de bases de datos responsivos: algoritmos de unión óptimos, enumeración, factorización, clasificación y programación dinámica" . Tutorial ICDE 2022 .Parte 3: Consultas acíclicas y enumeración. Diapositivas , vídeo de 20 minutos , página del tutorial .

• Algoritmo de Yannakakis