Structure of the Problemgraph

Graph structure

What can we say about the structure of the problem graph?

Note: Many propositions of this page have to be proved, yet.

Assumption:

The graph is induced from a redundancy free table

Nodes:

The nodes (n) of a graph are labeled by value(n) and the column(n).

Number of Paths:

The number of paths is stable for valid merging operations (See merging)

Paths:

Paths(g) are cliques in the graph with the following constraints: (a) The clique has size |column|. (b) Every element in the clique belongs to a different variable.

Properties:

The graph is chordal. Thus finding the maximal cliques can be achieved in polynomial time. (To proof: Before the first merging the graph is chordal. Every merging does not change this property) Maybe the graph is even a k-tree where k = |column| - 1 (?)

Merging:

A valid merging of two nodes merge(g, n1, n2) on a graph g has the precondition of column(n1) = column(n2) and value(n1) = value(n2). A new graph g' is created, replacing both nodes n1 and n2 by a new node n3. All edges either connected to n1 or n2 are modified to point to n3 instead. Postcondition: It should not change the set of paths and thus Path(g) = Path(g')

To Proof:

1. Is the graph chordal?
2. Is every maximal clique in the graph a path?
3. Are valid merging operations compositional? (The opposite can be shown by a counter example with two symmetric mergable nodes that exclude each other)
4. Is the resulting graph minimal? Has the shape of the graph influence on the final result?