Patent ID: 7496571

Claim:
A method for performing information-preserving DTD (Document Type Definition) schema embeddings between a source schema and a target schema, comprising: finding each DTD-legal string of the target, schema, wherein each of the source schema and the target schema comprise a Directed Acyelie Graph (DAG) DTD, wherein a DTD-legal string is a string, where after deleting all marked string nodes in the string at levels>_i, a node at level i-1 satisfies at least conditions of: (a) determining that a production of the node does not contain both conjunctive and disjunctive edge, (b) determining that where the node was originally a conjunctive node before the deletions, the deletions do not cause two or more disjunctive nodes to be merged into the node, and (c) determining that where the node was originally a disjunctive node before the deletions, the deletions do not cause two or more conjunctive nodes to be merged into the node; determining, for each DTD-legal string, a bottom-up estimate of DAG substructure root nodes in reduced DTD graphs to provide thereby initial estimates of the best cumulative edit distances of the relevant DAG substructures; determining a top down adjustment of the initial estimates to provide thereby a one to one matching value and corresponding match costs; and estimating a minimal match cost in memory, wherein the minimal match cost is the smallest among the match costs.