Paper Info
Title
Constraint Satisfaction for Reconciling Heterogeneous Tree Databases
Abstract
In order to simplify the reconciliation of two heterogeneous tree databases, we must minimize the number of crossovers in a directed graph constructed using two subtrees selected from the databases. This paper proposes a method for minimizing the number of crossovers in the directed graph. To find the directed graph with the minimum number of crossovers, the method maintains zero-crossovers in each ordered subtree. The resulting directed graph is defined as a semi-optimal solution satisfying the zero-crossover constraint for edges connecting two leaf sequences. It is computed by changing the order of non-leaf nodes in each hierarchical level of the ordered tree and swapping leaf nodes in each of the two leaf layers. To maintain the zero-crossover constraint for each ordered tree in the matrix transformation, the method also finds the two leaf clusters that contain half of the leaf nodes and swaps the leaf clusters.
Year
DOI
Venue
2000
10.1007/3-540-44469-6_58
DEXA
Keywords
Field
DocType
leaf cluster,leaf sequence,leaf layer,reconciling heterogeneous tree databases,non-leaf node,heterogeneous tree databases,hierarchical level,minimum number,zero-crossover constraint,constraint satisfaction,matrix transformation,leaf node,satisfiability,directed graph
Constraint satisfaction,Information integration,Cluster (physics),Computer science,Ordered graph,Tree (data structure),Directed graph,Transformation matrix,Database,Feedback arc set
Conference
ISBN
Citations 
PageRank 
3-540-67978-2
1
0.38
References 
Authors
7
2
Name
Order
Citations
PageRank
H. Kitakami19449.68
Mitsuko Nishimoto210.38