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:

• Schema transformations, like object-equivalent, weakly object-extending and object-extending transformations. The approach was to decompose a schema change into a sequence of those and more primitive transformations and then to execute the primitive sequence on the code associated with the original schema. The thesis of Paul Bergstein and Walter Huersch contributed to this area. The first work in this area was Paul Bergstein's OOPSLA 91 paper on decomposing the object-equivalent transformation into further primitives.
  Papers: Paul:oopsla-1, lhx93:ext, bh93:evolution, hk96:evolution, linda:thesis
• Using traversal strategies to embed one model into a larger model. We have a small schema s and a larger schema t. The embedding is of the form that a direct relationship in s is mapped into a composition of relationships in t; in other words, a path in s is mapped to an expansion of that path in t. The traversal strategies are used to merge the two schemas and the code that is associated with them.
• Using traversal strategies to write the programs affiliated with a schema. This is a preventive maintenance approach that makes programs more robust to schema changes.
  Papers: lieber-nacho-cun:pp-cacm, lzhl94:reuse
• Grammars. A schema augmented by concrete syntax turns into a context free grammar. This connection can be used to address schema evolution for many interesting cases. Paul Bergstein's PhD Thesis has successfully investigated this approach building on automata theoretic work by A. Salomaa.
  Papers: paul:thesis, paul:thesis-TAPOS-97

  A concrete project description about maintaining XML documents shows how the adaptive property of LL(1) grammars can be utilized to maintain XML documents.

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() {
  System.out.print(this.getPOBillTo().getCity());
  //  cg.traverse(this, "PO -> POBillTo -> City", printVisitor);
}
is automatically transformed to:
// class PurchaseOrder
void printBillingCity() {
  System.out.print(this.getInvoiceTo().getAddress().getCity());
  //  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.

ship city "x"  street "y" 
bill city "x1" street "y1"

ship 
bill 

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.

References

PhD Theses of Demeter Group

@INPROCEEDINGS{Paul:oopsla-1,
AUTHOR = "Paul Bergstein",
TITLE = "Object-Preserving Class Transformations",
BOOKTITLE = oopsla,
YEAR = "1991",
ADDRESS = "Phoenix, Arizona",
PAGES = "299-313",
PUBLISHER = "ACM Press",
NOTE = "SIGPLAN Notices, Vol. 26, No. 11, November"
}

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

@ARTICLE{paul:thesis-TAPOS-97,
AUTHOR = "Paul L. Bergstein",
TITLE = "Maintainance of Object-Oriented Systems During Structural Schema Evolut
ion",
JOURNAL = tapos,
YEAR = 1997,
PAGES = "185-212",
MONTH = "",
VOLUME = 3,
NUMBER = 3
}

@INPROCEEDINGS{bh93:evolution,
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",
ORGANIZATION = "JSSST",
ADDRESS =     "Kanazawa, Japan",
PAGES =       "176--193",
PUBLISHER =   lncs,
NOTE =        ""
}

@PHDTHESIS{linda:thesis,
AUTHOR = "Linda Seiter",
TITLE = "Design Patterns for Managing Evolution",
SCHOOL = "Northeastern University",
YEAR = 1996,
NOTE = "188 pages"
}

@INPROCEEDINGS{hk96:evolution,
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        = "",
ORGANIZATION  = "",
PUBLISHER     = spcs,
ADDRESS       = "Kanazawa, Japan",
PAGES         = "2-21"
}

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

@ARTICLE{lhx93:ext,
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"
}

@INPROCEEDINGS{lzhl94:reuse,
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 =      "",
ORGANIZATION = "IEEE",
PUBLISHER =   "",
ADDRESS =     "Houston",
PAGES =       "180-189"
}

@ARTICLE{lieber-nacho-cun:pp-cacm,
AUTHOR  = "Karl J. Lieberherr and Ignacio {Silva-Lepe} and Cun Xiao",
TITLE   = "Adaptive Object-Oriented Programming using Graph-Based Customization"
,
JOURNAL = commACM,
YEAR    =  "1994",
MONTH   = "May",
VOLUME  = 37,
NUMBER  = 5,
PAGES   = "94-101"
}