Bijective Partial Map

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa

Abstract:

Many applications require "lookup tables" that map objects in one domain to objects in another domain using unique "key" values. For example, a simple database may map employee names (social security numbers) to their salaries. In this example, unique employee names can be used as lookup keys for salaries. It may be the case, however, that the same salary is earned by several employees; so salaries cannot be used as lookup keys for unique employees. An appropriate data type for this scenario would be a Partial Map, which is modeled by a partial function.

Other applications require the objects in both domains to be unique, so that values in either domain can be used as lookup keys for values in the other. For example, a graph algorithm that computes least-cost tours may be easier to implement using integers instead of city names. In this case, it is useful to map unique cities to unique integer ids, compute the least-cost tour as a string of integers, and then recover the original city names using the inverse mapping from integers back to cities. To compute the inverse, however, the mapping function must be one-to-one so that the mapping is bijective on the partial domains.

This project explores design trade-offs and alternatives germaine to implementing the abstract data type Bijective Partial Map, which is modeled by a bijective partial function.

Calendar:

• The project was completed for Autumn Quarter 1997. The resulting Bijective_Partial_Map component was used that quarter in CIS 221 (an introductory course on software-component engineering) in the context of a least-cost path laboratory.

Project Development:

This documentation will take some time to reconstruct. In the mean time, I encourage the interested reader to follow the links below to the concrete specifications of both implementations. The first implementation is straightforawd and uncomplicated. The second may take some work to understand, but it is a good exercise in reading specifications.

Findings and Contributions:

An open question I had about the resulting component was that although it optimized space complexity, its time complexity still suffered from what appeared to be a substantial constant-factor overhead. I've sketched out yet another implementation of the component that uses a doubly-linked pointer structure to traverse separate binary trees. The drawback is the complexity involved with reasoning about the correctness of such an implementation, but it seems clear to me that it would outperform our currently optimal implementation.

Links and References:

• Abstract specification of the Bijective_Partial_Map type.
• Abstract specification of the Bijective_Partial_Map kernel operations.
• Concrete specification of the Bijective_Parital_Map_Kernel_1 design.
• Concrete specification of the Bijective_Parital_Map_Kernel_2 design.
• Concrete specification of the Bijective_Partial_Map_Kernel_1 implementation.
• Concrete specification of the Bijective_Partial_Map_Kernel_2 implementation.

  Return to Europa