Generic Model Management

While attending the Microsoft Research Faculty Summit 2003 at Microsoft University in Bellevue, Washington, I had the opportunity to discover a second strong connection between my work and work done at Microsoft Research. For the first connection see P-optimal thresholds.

Philip Bernstein at Microsoft Research has for several years been investigating generic model management to provide an infrastructure for schema manipulation problems. They all involve schemas and software associated with the schemas and mappings between the schemas. Such problems are pervasive and include data translation (e.g., XML message translation for e-commerce), schema evolution (updating the software associated with a schema when the schema changes), integration of applications, data warehouse loading, etc. Phil Bernstein advocates a generic high-level approach to those meta data problems that avoid a lot of object-at-a-time programming.

The Demeter Research Group has been studying model management for over a decade. We focused on how to evolve object-oriented programs when the object-oriented schema changes. We investigated how to prepare for schema evolution by writing object-oriented programs in adaptive style. Adaptive programs are robust to object-oriented schema changes. Central to our investigation of generic model management are four areas:

Example of expressing schema mapping with traversal strategies. The schemas are from Generic Model Management by Phil Bernstein:

Example for using traversal strategies for model embedding:

Schema 1:
PO = POShipTo POBillTo.
POShipTo = City Street.
POBillTo = City Street.
City = String.
Street = String.

Schema 2:
PurchaseOrder = DeliverTo InvoiceTo.
DeliverTo = Address.
InvoiceTo = Address.
Address = [ZipCity] [Street]. // [] means optional (EBNF notation)
ZipCity = [ZipCode] City.
ZipCode = int.

Map expressed with traversal strategies:
PO -> POShipTo -> {City,Street}  ::: PurchaseOrder -> DeliverTo -> {City,Street}
PO -> POBillTo   -> {City,Street}  ::: PurchaseOrder -> InvoiceTo -> {City,Street}

// class PO
void printBillingCity() {
  //  cg.traverse(this, "PO -> POBillTo -> City", printVisitor);
is automatically transformed to:
// class PurchaseOrder
void printBillingCity() {
  //  cg.traverse(this, "PurchaseOrder -> InvoiceTo -> City", printVisitor);

Example for 4:  use a grammar-based approach based on language inclusion:

Schema 1 is transformed into the following grammar G1:
PO = "ship" POShipTo "bill" POBillTo.
POShipTo = City Street.
POBillTo = City Street.
City = "city" String.
Street = "street" String.

Schema 2 is transformed into the following grammar G2:
PurchaseOrder = "ship" DeliverTo "bill" InvoiceTo.
DeliverTo = Address.
InvoiceTo = Address.
Address = [ZipCity] [Street].
ZipCity = [ZipCode] City.
ZipCode = int.
City = "city" String. 
Street = "street" String.
Notice that the language of PO-sentences is a sublanguage of PurchaseOrder-language. For example the sentence
ship city "x"  street "y" 
bill city "x1" street "y1"
belongs to both languages. While
belongs only to the PurchaseOrder-language. The thesis result of Paul Bergstein can be used to automatically generate the program transformation and instance mapping.

In order to transform a schema 1 object s1 to a schema 2 object, we print s1 according to G1 and parse the output according to G2. All the information in the schema 1 objects is properly put into schema 2 objects. But note that although G1 defines a sublanguage of G2, schema 1 objects don't conform to schema 2. An interesting translation has to take place which is automated by the printing/parsing approach.


PhD Theses of Demeter Group

AUTHOR = "Paul Bergstein",
TITLE = "Object-Preserving Class Transformations",
BOOKTITLE = oopsla,
YEAR = "1991",
ADDRESS = "Phoenix, Arizona",
PAGES = "299-313",
NOTE = "SIGPLAN Notices, Vol. 26, No. 11, November"

AUTHOR = "Paul Bergstein",
TITLE = "{Managing the Evolution of Object-Oriented Systems}",
SCHOOL = "Northeastern University",
YEAR = 1994,
NOTE = "151 pages"

AUTHOR = "Paul L. Bergstein",
TITLE = "Maintainance of Object-Oriented Systems During Structural Schema Evolut
JOURNAL = tapos,
YEAR = 1997,
PAGES = "185-212",
MONTH = "",

AUTHOR =      "Paul L. Bergstein and Walter L. H{\"u}rsch",
TITLE =       "Maintaining Behavioral Consistency during Schema Evolution",
BOOKTITLE =   isotas,
YEAR =        1993,
MONTH =       "November",
EDITOR =      "S. Nishio and A. Yonezawa",
ADDRESS =     "Kanazawa, Japan",
PAGES =       "176--193",
PUBLISHER =   lncs,
NOTE =        ""

AUTHOR = "Linda Seiter",
TITLE = "Design Patterns for Managing Evolution",
SCHOOL = "Northeastern University",
YEAR = 1996,
NOTE = "188 pages"

AUTHOR        = "Walter L. H{\"u}rsch and Linda M. Seiter",
TITLE = "Automating the Evolution of Object-Oriented Systems",
BOOKTITLE     = isotas,
YEAR          = 1996,
MONTH         = "March",
EDITOR        = "",
PUBLISHER     = spcs,
ADDRESS       = "Kanazawa, Japan",
PAGES         = "2-21"

AUTHOR = "Walter H{\"u}rsch",
TITLE = "Maintaining Consistency and Behavior of
Object-Oriented Systems during Evolution",
SCHOOL = "Northeastern University",
YEAR = 1995,
NOTE = "331 pages"

AUTHOR =      "Karl J. Lieberherr and Walter L. H{\"u}rsch and Cun Xiao",
TITLE =       "Object-extending Class Transformations",
JOURNAL =     fac,
YEAR =        1994,
PAGES =       "391-416",
Number = 6,
NOTE =        "Also available as Technical
Report NU-CCS-91-8, Northeastern University"

AUTHOR =      "Ling Liu and Roberto Zicari and Walter H{\"u}rsch and
Karl Lieberherr",
TITLE =       "Polymorphic Reuse Mechanisms for Object-Oriented
Database Specifications",
BOOKTITLE =   icde,
YEAR =        1994,
MONTH =       "February",
EDITOR =      "",
ADDRESS =     "Houston",
PAGES =       "180-189"

AUTHOR  = "Karl J. Lieberherr and Ignacio {Silva-Lepe} and Cun Xiao",
TITLE   = "Adaptive Object-Oriented Programming using Graph-Based Customization"
YEAR    =  "1994",
MONTH   = "May",
VOLUME  = 37,
NUMBER  = 5,
PAGES   = "94-101"