Microsoft Technology Licensing, LLC

Alan P Nash

Philip Alan Bernstein

Sergey Melnik

Todd J Green

A system that facilitates composition of schema mappings. A general algorithm is provided for composing a broad class of mappings, where one or both mappings are not functions, such as constraints between two schemas and the inverse of functions. A composition component performs composition on schema mappings of disparate data sources, which schema mappings can be expressed by at least one of full, embedded, and second-order dependencies, wherein the second-order dependencies need not be in source-to-target form. The algorithm for composition further includes a procedure that tests whether the composition algorithm will terminate.

System and method for composition of mappings given by dependencies

A general-purpose reusable algebraic-based composition algorithm for composing mappings between data schemas. The algorithm handles more expressive mappings, makes a best-effort to eliminate symbols when a perfect answer cannot be obtained, includes new heuristics, and is extensible. A relational algebraic language is provided wherein each mapping is expressed as a set of constraints, and each constraint is either a containment or equality of two or more relational algebraic expressions. The composition mechanism exploits monotonicity properties of algebraic operators in operator arguments, handles NULLs and bag semantics, operates to allow composition to produce a partial result when a complete result is not possible, facilitates symbols elimination one symbol at a time using left composition, for example, as a way of isolating the symbols, supports making a best-effort to eliminate as many symbols as possible from an intermediate schema, and handles unknown or partially known operators via delayed handling.

Growing community of inventors

La Jolla, CA, United States of America

Alan P Nash