#!/usr/bin/env python

# We represent a dependency as a pair of sets.
# If alpha and beta are sets in Python of attributes then
# alpha -> beta is (alpha,beta)

# These are an example set of dependencies
# From the book, page 338,
# Database System Concepts Silberschatz 6ed.

# A  -> B
# A  -> C
# CG -> H
# CG -> I
# B  -> H
F = [                               \
     (set(['a']),set(['b'])),       \
     (set(['a']),set(['c'])),       \
     (set(['c','g']),set(['h'])),   \
     (set(['c','g']),set(['i'])),   \
     (set(['b']),set(['h']))        \
    ]

result = set(['a','g'])
#result = set(['c','g'])
done = False

# This is the Python version of the Algorithm
# on page 341.
while not done:
    before = len(result)
    
    for (beta,gamma) in F:
        if beta.issubset(result):
            result = result.union(gamma)

    if len(result) == before:
        done = True
        
print result;