The design and implementation of hierarchical software systems with reusable components

ABSTRACT

We present a domain-independent model of hierarchical software system design and construction that is based on interchangeable software components and large-scale reuse. The model unifies the conceptualizations of two independent projects, Genesis and Avoca, that are successful examples of software component/building-block technologies and domain modeling. Building-block technologies exploit large-scale reuse, rely on open architecture software, and elevate the granularity of programming to the subsystem level. Domain modeling formalizes the similarities and differences among systems of a domain. We believe our model is a blueprint for achieving software component technologies in many domains.

REFERENCES

• 1: Maurice J. Bach, The design of the UNIX operating system, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 2: D. S. Batory, Modeling the storage architectures of commercial database systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.463-528, Dec. 1985 [doi>10.1145/4879.5392]
• 3: ~BATORY, D.S. Extensible cost models and query optimization m GENESIS. IEEE Database ~Eng. (1987).
• 4: D. S. Batory, Concepts for a database system compiler, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.184-192, March 1988, Austin, Texas, United States [doi>10.1145/308386.308435]
• 5: D. S. Batory , J. R. Barnett , J. F. Garza , K. P. Smith , K. Tsukuda , C. Twichell , T. E. Wise, GENESIS: An Extensible Database Management System, IEEE Transactions on Software Engineering, v.14 n.11, p.1711-1730, November 1988 [doi>10.1109/32.9057]
• 6: ~BATORY, D. S., BARNETT, J. R., ROY, J., TWICHRLL, B. C., AND GARZA, J. Construction of file ~management systems from software components. COMPSAC, 1989
• 7: D. S. Batory, On the reusability of query optimization algorithms, Information Sciences: an International Journal, v.49 n.1-3, p.177-202, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90027-3]
• 8: Don S. Batory, The Genesis Database System Compiler: User Manual, University of Texas at Austin, Austin, TX, 1990
• 9: ~BATORY, D. S., AND BARNETt, J. R. DATE. The genes~s DBMS software layout editor. In ~Conceptual Modelling, Databases, and CASE, R. Zicari, Ed., McGraw-Hfil, 1991.
• 10: ~BATORY, D.S. A domain modeling methodology. In preparation.
• 11: ~BATORY, D. S., ET AL. The implementation of genesis. In preparation
• 12: ~BAXTER, I. Personal communication.
• 13: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 14: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 15: B. Bershad , T. Anderson , E. Lazowska , H. Levy, Lightweight remote procedure call, Proceedings of the twelfth ACM symposium on Operating systems principles, p.102-113, November 1989
• 16: Ted J. Biggerstaff , Alan J. Perlis, Software reusability: vol. 1, concepts and models, ACM Press, New York, NY, 1989
• 17: ~BIGGERS?AFF, T. J., AND PERLIS, A.J. Software Reusability II Apphcat~ons and Experience. ~ACM Press, 1989.
• 18: Grady Booch, Software Component with ADA, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1987
• 19: Grady Booch, Object oriented design with applications, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1990
• 20: Kathryn Heninger Britton , R. Alan Parker , David L. Parnas, A procedure for designing abstract interfaces for device interface modules, Proceedings of the 5th international conference on Software engineering, p.195-204, March 09-12, 1981, San Diego, California, United States
• 21: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 22: ~CHAMBERLIN, D. D., ET AL. SEQUEL 2: A unified approach to data definition, manipulation, ~and control. IBM J. Res. Dev. 20, 6 (Nov. 1976).
• 23: D Cheriton, VMTP: a transport protocol for the next generation of communication systems, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, p.406-415, August 05-07, 1986, Stowe, Vermont, United States
• 24: David D. Clark, The structuring of systems using upcalls, ACM SIGOPS Operating Systems Review, v.19 n.5, p.171-180, Dec. 1-4, 1985
• 25: L. P. Deutsch, Design reuse and frameworks in the smalltalk-80 system, Software reusability: vol. 2, applications and experience, ACM Press, New York, NY, 1989 [doi>10.1145/75722.75725]
• 26: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 27: ~GOGUEN, J. Parameterized programming. IEEE Trans. Softw. Eng. SE-IO, 5 (Sept. 1984).
• 28: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 29: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, ACM SIGMOD Record, v.16 n.3, p.160-172, Dec. 1987
• 30: ~GRAVES, H., AND POLAK, W. Common intermediate design language overview. Lockheed Palo ~Alto Res. Lab., Spring 1991.
• 31: John Guttag, Abstract data types and the development of data structures, Communications of the ACM, v.20 n.6, p.396-404, June 1977 [doi>10.1145/359605.359618]
• 32: John V. Guttag , Ellis Horowitz , David R. Musser, Abstract data types and software validation, Communications of the ACM, v.21 n.12, p.1048-1064, Dec. 1978 [doi>10.1145/359657.359666]
• 33: A. N. Habermann , Lawrence Flon , Lee Cooprider, Modularization and hierarchy in a family of operating systems, Communications of the ACM, v.19 n.5, p.266-272, May 1976 [doi>10.1145/360051.360076]
• 34: A. N. Habermann , Lawrence Flon , Lee Cooprider, Modularization and hierarchy in a family of operating systems, Communications of the ACM, v.19 n.5, p.266-272, May 1976 [doi>10.1145/360051.360076]
• 35: Roger Hayes , Steve W. Manweiler , Richard D. Schlichting, A simple system for constructing distributed, mixed-language programs, Software—Practice & Experience, v.18 n.7, p.641-660, July 1988 [doi>10.1002/spe.4380180705]
• 36: Norman C. Hutchinson , Larry L. Peterson, The X-Kernel: An Architecture for Implementing Network Protocols, IEEE Transactions on Software Engineering, v.17 n.1, p.64-76, January 1991 [doi>10.1109/32.67579]
• 37: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 38: ~JOHNSON, R. E., AND FOOTE, B. Designing reusable classes. J. Object-Ortented Program. ~(June/July 1988).
• 39: Henry F. Korth , Abraham Silberschatz, Database system concepts, McGraw-Hill, Inc., New York, NY, 1986
• 40: ~LINDSAY, B. Private communication, 1989.
• 41: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 42: Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
• 43: Tony Mason , Doug Brown, Lex & yacc, O'Reilly & Associates, Inc., Sebastopol, CA, 1990
• 44: Jeffrey C. Mogul , Anita Borg, The effect of context switches on cache performance, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.75-84, April 08-11, 1991, Santa Clara, California, United States
• 45: ~O'MALLEY, S.W. Ph.D. dissertation, Univ. of Arizona, 1990.
• 46: Sean William O'Malley , Larry L. Peterson, Avoca: an environment for programming with protocols, 1990
• 47: ~O'MALLEY, S. W., AND PETERSON, L.L. A new methodology for designing network software. ~Submitted for publication.
• 48: ~O'iVIALLEY, S. W., ABBOTT, M. B., HUTCHINSON, N. C., AND PETERSON, L.L. A transparent ~blast facility. J. Internetworking, 1, 2 (Dec. 1990).
• 49: John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
• 50: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 51: ~PARNAS, D.L. Designing software for ease of extension and contraction. IEEE Trans. Softw. ~Eng. (Mar. 1979).
• 52: Ruben Prieto-Diaz , G. Arango, Domain Analysis and Software Systems Modeling, IEEE Computer Society Press, Los Alamitos, CA, 1991
• 53: James Purtilo, Polylith: An environment to support management of tool interfaces, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.12-18, June 25-28, 1985, Seattle, Washington, United States
• 54: ~RoY, J. Design and use of the Jupiter file management system. M.Sc. thesis, Dept. of ~Computer Science, Univ. of Texas, 1991.
• 55: James Rumbaugh , Michael Blaha , William Premerlani , Frederick Eddy , William Lorensen, Object-oriented modeling and design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 56: ~SOFTWARE ENGINEERING INSTITUTE. Proceedings of the Workshop on Domain-Specific Soft- ~ware Architectures (July 9-12, 1990).
• 57: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 58: Richard Snodgrass, The interface description language: definition and use, Computer Science Press, Inc., New York, NY, 1989
• 59: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 60: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 61: ~TENNENHOUSE, D.L. Layered multiplexing considered harmful. In 1st International Work- ~shop on H,gh-Speed Networks (Nov 1989).
• 62: Toby J. Teorey , Dongqing Yang , James P. Fry, A logical design methodology for relational databases using the extended entity-relationship model, ACM Computing Surveys (CSUR), v.18 n.2, p.197-222, June 1986 [doi>10.1145/7474.7475]
• 63: Toby J. Teorey, Database modeling and design: the entity-relationship approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 64: ~TSICHmTZIS, D., AND KLUG, A., EDS. The ANSI/X3/SPARC DBMS Framework. AFIPS ~Press, 1978.
• 65: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 66: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 67: Clement T. Yu , Z. Meral Ozsoyoglu , K. Lam, Optimization of distributed tree queries, Journal of Computer and System Sciences, v.29 n.3, p.409-445, Dec. 1984 [doi>10.1016/0022-0000(84)90007-2]
• 68: Carlo Zaniolo, The database language GEM, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 69: ~ZIMMERMANN, H. OSI Reference Model--The ISO model of architecture for open systems ~interconnection. IEEE Trans. Commun. 28, 4 (April 1980).

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Methodologies**

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Representation**
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces; Software libraries
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Extensibility**
      D.2.m Miscellaneous
          Subjects: Rapid prototyping**; Reusable software**

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Design, Standardization

Keywords:
domain modeling, open system architectures, reuse, software building-blocks, software design