Extracting a Largest Redundancy-Free XML Storage Structure From an Acyclic Hypergraph in Polynomial Time

Date Added: Dec 2009
Format: PDF

Given a hypergraph and a set of embedded functional dependencies, the authors investigates the problem of determining the conditions under which the authors can efficiently generate redundancy-free XML storage structures with as few scheme trees as possible. Redundancy-free XML structures guarantee both economy in storage space and the absence of update anomalies, and having the least number of scheme trees requires the fewest number of joins to navigate among the data elements. The authors know that the general problem is intractable. The problem may still be intractable even when the hypergraph is acyclic and each hyperedge is in Boyce-Codd Normal Form (BCNF).