Methods and apparatus for mapping source schemas to a target schema using schema embedding

• US 20060271506A1
• Filed: 05/31/2005
• Published: 11/30/2006
• Est. Priority Date: 05/31/2005
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Fan, Wenfei, Perinkulam, Suryanarayan, Flaster, Michael E., Bohannon, Philip L.
• Granted Patent: US 7,921,072 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/88 Mark-up to mark-up conversion conversion for visualization in web browsing G06F16/9577

Abstract

Methods and apparatus are provided for mapping XML source documents to target documents using schema embeddings. According to one aspect of the invention, one or more edges in the one or more source schemas are mapped to one or more paths in at least one target schema. The disclosed mapping techniques ensure that (i) one or more source documents that conform to one or more of the source schemas can be recovered from one or more target documents that conform to the at least one target schema, if a mapping exists between the one or more of the source schemas and the at least one target schema; (ii) queries on one or more source documents that conform to one or more of the source schemas in a given query language can be answered on one or more target documents that conform to the at least one target schema; and (iii) the one or more target documents conform to a target schema.

Claims

1. A method for mapping one or more source schemas to at least one target schema, comprising:

mapping one or more edges in said one or more source schemas to one or more paths in said at least one target schema.

2. The method of claim 1, wherein paths in said target schema mapped from sibling edges in said source schema are sufficiently distinct to allow information to be preserved.

3. The method of claim 1, further comprising the step of mapping at least one node in said one or more source schemas to at least one node in said at least one target schema.

4. The method of claim 1, wherein paths in said target schema mapped from sibling edges in said source schema are sufficiently distinct to allow information to be preserved.

5. The method of claim 1, wherein one or more source documents each conforming to one of said source schemas can be recovered from one or more target documents each conforming to said at least one target schema, if a mapping exists between said source schema and said target schema.

6. The method of claim 1, wherein queries on one or more source documents each conforming to one of said source schemas in a given query language can be answered on one or more target documents each conforming to said at least one target schema.

7. The method of claim 6, further comprising the step of translating a reference to an edge in said one or more source schemas to a reference to a path in at least one target schema.

8. The method of claim 1, further comprising the step of finding one or more local embeddings for individual productions in said one or more source schemas and combining them to form a consistent embedding.

9. The method of claim 8, wherein said local embeddings are assembled into a schema embedding using a random order of said local embeddings.

10. The method of claim 8, wherein said local embeddings are assembled into a schema embedding using a quality-specific order of said local embeddings.

11. The method of claim 8, further comprising the steps of generating a candidate pool of local embeddings and employing a heuristic solution to Maximum-Independent-Set to assemble a valid schema embedding.

12. The method of claim 8, wherein said local embeddings are assembled into a schema embedding and wherein said method further comprises the step of generating one or more non-conflicting local embeddings when a conflict is detected.

13. The method of claim 1, wherein said mapping step generates a schema embedding, σ

, that is a pair of functions (λ

,path) that maps each element type, A, in a collection of labels, E₁, from a source schema, S₁, to a corresponding λ

(A) type in a collection of labels, E₂, from a target schema, S₂, for said type mapping, λ

, and each edge (A, B) in S₁ to a unique path (A,B) from λ

(A) to λ

(B) in S₂.

14. The method of claim 1, wherein said mapping is based on a similarity metric, att (A,B), that indicates the suitability of mapping each element type A in a source schema to each element type B in a target schema.

15. A method for identifying one or more prefix-free paths in a directed acyclic graph (DAG) structure, comprising:

performing a depth-first-search on an input graph to identify one or more paths from a source node s to target nodes in a set of target vertices, L_tar; and

identifying prefix-free paths among said identified paths.

16. The method of claim 15, further comprising the step of maintaining an array to monitor whether a subgraph rooted at a node n has been searched and yielded no matches for nodes in L_tar.

17. An apparatus for mapping one or more source schemas to one or more target schemas, the apparatus comprising:

a memory; and

at least one processor, coupled to the memory, operative to;

map one or more edges in said one or more source schemas to one or more paths in said one or more target schemas.

18. The apparatus of claim 17, wherein paths in said target schema mapped from sibling edges in said source schema are sufficiently distinct to allow information to be preserved.

19. The apparatus of claim 17, wherein one or more source documents each conforming to one of said source schemas can be recovered from one or more target documents conforming to said at least one target schema, if a mapping exists between said source schema and said target schema.

20. The apparatus of claim 17, wherein queries on one or more source documents each conforming to one or more of said source schemas in a given query language can be answered on one or more target documents conforming to said at least one target schema.

21. The apparatus of claim 17, further comprising the step of finding one or more local embeddings for individual productions in said one or more source schemas and combining them to form a consistent embedding.

22. The apparatus of claim 21, wherein said local embeddings are assembled into a schema embedding using a random order of said local embeddings.

23. The apparatus of claim 21, wherein said local embeddings are assembled into a schema embedding using a quality-specific order of said local embeddings.

24. The apparatus of claim 21, further comprising the steps of generating a candidate pool of local embeddings and employing a heuristic solution to Maximum-Independent-Set to assemble a valid schema embedding.