Finding Compact Scheme Forests in Nested Normal Form is NP-Hard
Peter ThanischGeorge LoizouJyrki NummenmaaPublished in: Inf. Comput. (1994)
Keyphrases
- normal form
- nested relations
- np hard
- database design
- polynomial time approximation
- functional dependencies
- relational databases
- complex objects
- relational algebra
- special case
- np complete
- information content
- relational database theory
- prime implicates
- relational model
- approximation algorithms
- integrity constraints
- disjunctive normal form
- relational database systems
- knowledge compilation
- boolean expressions
- lower bound
- optimal solution
- databases