Skip to main content

RWTH Aachen Computer Science i5/dbis assets for Lecture Datenbanken und Informationssysteme

Project description

DBIS Functional Dependencies

Functional Dependencies and Normal Forms for Relational Databases

PyPI Status pypi License Pipeline Status

This library provides a Python implementation of the synthesis algorithm and decomposition algorithm according to the DBIS lecture. For more background and application of functional dependencies and the algorithms, see Doku-FunctionalDependencies.

Features

  • Create sets of Functional dependencies (FDSets).
  • Calculate candidate keys of an FDSet.
  • Calculate attribute closure of an attribute or set of attributes.
  • Test whether an FDSet is in 2NF, 3NF or BCNF.
  • Execute the synthesis algorithm to transform the FDSet into 3NF.
  • Execute the decomposition algorithm to transform the FDSet into BCNF.
  • Generate the closure $F^+$ of an FDSet $F$.
  • Generate true/false questions w.r.t. synthesis and decomposition algorithm.

Installation

Install via pip:

pip install dbis-functional-dependencies

Usage

Creating an FDSet

Create a new instance of FunctionalDependencySet. The set of attributes is passed as parameter.

fdset = FunctionalDependencySet('ABCDE')

You can add more attributes later by using the add_attribute function.

fdset.add_attribute('F')

Add dependencies with the add_dependency function ...

fdset.add_dependency("AC", "DE")
fdset.add_dependency("DEF", "B")
fdset.add_dependency("B", "D")

... or remove them with the remove_dependency function.

fdset.remove_dependency("B", "D")

Printing an FDSet shows the dependencies in a more readable form.

print(f"{fdset}")

Attribute closure and candidate keys

Calculate the attribute closure of one or multiple attributes.

closureA = fdset.get_attr_closure('A')
closureAC = fdset.get_attr_closure('AC')

Calculate all candidate keys.

ckeys = fdset.find_candidate_keys()

Check for normal forms

Since we only work with schemas (no actual values for the attributes), we assume that a corresponding database is in 1NF.

Check whether the FDSet is in 2NF, 3NF or BCNF.

is2NF = fdset.is2NF()
is3NF = fdset.is3NF()
isBCNF = fdset.isBCNF()

Execute the synthesis algorithm

Execute the synthesis algorithm on an FDSet to generate a corresponding list of FDSets in 3NF.

fdslist = fdset.synthesize()

The algorithm performs the following steps:

  1. Find the candidate keys.
  2. Calculate the canonical cover.
    • left reduction
    • right reduction
    • remove dependencies with empty rhs
    • combine dependencies with same lhs
  3. Create a new relation for every dependency in the canonical cover.
  4. Create the optional key scheme if no candidate key is included in the attribute set of one of the relations of step 2.
  5. Remove subset relations.

You receive additional information on the steps of the algorithm by toggling the parameter verbose.

fdslist = fdset.synthesize(vebose=True)

Alternatively, you can also execute the single steps with the following functions:

fdset_step.canonical_cover()
fdslist_step = fdset_step.create_new_fdsets()
fdslist_step_with_key = FunctionalDependencySet.create_optional_key_scheme(self, ckeys, fdslist_step)
reduced_fdslist_step = FunctionalDependencySet.remove_subset_relations(self, fdslist_step_with_key)

The verbose option exists for all steps.

Execute the decomposition algorithm

Execute the decomposition algorithm on an FDSet to generate a corresponding decomposition of FDSets in BCNF.

fdslist = fdset.decompose2()

Before performing the actual algorithm, the the closure of the FDSet is calculated.

Closure of an FDSet

Calculate the closure $F^+$ of an FDSet $F$.

fdset.completeFDsetToClosure()

This function just adds dependencies with all subset combinations of the attribute set with their corresponding closures on the rhs of the dependency, so that no implicit dependency is missed by the decomposition algorithm.

Exercise generator

Generate true/false statements based on the different steps of the algorithms.

fdslist = fdset.synthesize(genEx=True)

The genEx option is available for the following functions:

  • find_candidate_keys
  • synthesize
    • canonical_cover
      • left_reduction
      • right_reduction
      • remove_empty_fds
      • combine_fds
    • create_new_fdsets
    • create_optional_key_scheme
    • remove_subset_relations
  • decompose2

Checking results against expected

Checks a given calculated step of an FDSet during the synthesis algorithm (according to the DBIS lecture) for correctness.

original = fdset.copy()
fdset.left_reduction()
original.isCorrectLeftReduction(fdset)

For this purpose, the following functions exist:

  • isCorrectLeftReduction
  • isCorrectRightReduction
  • isCorrectRemovingEmptyFDs
  • isCorrectCombinationOfDependencies
  • isCorrectCanonicalCover
  • isCorrectCreationOfNewFDS

These functions are called on the FDSet with all steps before already calculated on it.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

dbis_functional_dependencies-1.0.0.tar.gz (40.6 kB view details)

Uploaded Source

Built Distribution

File details

Details for the file dbis_functional_dependencies-1.0.0.tar.gz.

File metadata

File hashes

Hashes for dbis_functional_dependencies-1.0.0.tar.gz
Algorithm Hash digest
SHA256 c4d7724e0b2a6171d712bb1a61a0d7b401ae5cbe17755068e0bd5349a2bfd8c8
MD5 55cb3bafdca51d43f59866d50b22f760
BLAKE2b-256 19f291bb2e13b2ad894c2dd22bfdd1ff1397b25ed08bb1fde20ed04849272429

See more details on using hashes here.

File details

Details for the file dbis_functional_dependencies-1.0.0-py3-none-any.whl.

File metadata

File hashes

Hashes for dbis_functional_dependencies-1.0.0-py3-none-any.whl
Algorithm Hash digest
SHA256 b87793293e107158127aad3c0102aaf72dd5591ac23e2ec65693e7c580aedcfc
MD5 82a0e0207d5b6212765069f54e884f64
BLAKE2b-256 1508bf54e6dacfa1bbe3b066453fc68c1d36849598b7c51ea77cecb00261ef64

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page