Finding compact scheme forests in nested normal form is NP-hard
type: Item
instance of: scholarly article
title: Finding compact scheme forests in nested normal form is NP-hard
zbMATH Open document ID: 0804.68035
published in: Information and Computation
publication date: 1995-01-12T00:00:00Z
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 563070
zbMATH Keywords: query processing performance
zbMATH Keywords: relational databases
zbMATH Keywords: nested normal form
zbMATH Keywords: multivalued dependencies
author: Peter Thanisch
author: George Loizou
author: Jyrki Nummenmaa
MaRDI profile type: Publication
OpenAlex ID: W2091946057
DOI: 10.1006/INCO.1994.1022
Recommended article: Compact scheme forests in nested normal form
Recommended article: Finding a tree structure in a resolution proof is NP-complete
Recommended article: Complexity and approximation of the constrained forest problem
Recommended article: Embedding Trees in a Hypercube is NP-Complete
Recommended article: Nested semantics over finite trees are equationally hard
Recommended article: Recognizing union-find trees is NP-complete
Recommended article: Extended formulation for CSP that is compact for instances of bounded treewidth
Recommended article: Navigating Forest Straight-Line Programs in Constant Time
Recommended article: NP-completeness and degree restricted spanning trees
Recommended article: Generalized hypertree decompositions: NP-hardness and tractable variants
description: scientific article; zbMATH DE number 563070