Patent ID: 7496571
Filing Date: 2009-02-24
Classification: G06F,Y10S

Abstract:
1. 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: 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.