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
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:
- Find the candidate keys.
- Calculate the canonical cover.
- left reduction
- right reduction
- remove dependencies with empty rhs
- combine dependencies with same lhs
- Create a new relation for every dependency in the canonical cover.
- Create the optional key scheme if no candidate key is included in the attribute set of one of the relations of step 2.
- 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
Built Distribution
File details
Details for the file dbis_functional_dependencies-1.0.0.tar.gz
.
File metadata
- Download URL: dbis_functional_dependencies-1.0.0.tar.gz
- Upload date:
- Size: 40.6 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/5.1.0 CPython/3.10.14
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | c4d7724e0b2a6171d712bb1a61a0d7b401ae5cbe17755068e0bd5349a2bfd8c8 |
|
MD5 | 55cb3bafdca51d43f59866d50b22f760 |
|
BLAKE2b-256 | 19f291bb2e13b2ad894c2dd22bfdd1ff1397b25ed08bb1fde20ed04849272429 |
Provenance
File details
Details for the file dbis_functional_dependencies-1.0.0-py3-none-any.whl
.
File metadata
- Download URL: dbis_functional_dependencies-1.0.0-py3-none-any.whl
- Upload date:
- Size: 30.7 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/5.1.0 CPython/3.10.14
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | b87793293e107158127aad3c0102aaf72dd5591ac23e2ec65693e7c580aedcfc |
|
MD5 | 82a0e0207d5b6212765069f54e884f64 |
|
BLAKE2b-256 | 1508bf54e6dacfa1bbe3b066453fc68c1d36849598b7c51ea77cecb00261ef64 |