On Conceptual Modelling

This is a brief overview of terminology and issues related to Knowledge Representation (hereafter KR) research, intended primarily for researchers from the Database or Programming Language area.

This chapter presents a view of data models and their development. It outlines the basic problem of data modelling in the database context, data model concepts and terminology, a taxonomy of data models, research issues central to data models, and those issues of particular interest in current research.

The major issues of modern software are its size and complexity, and its major problems involve finding effective techniques and tools for organization and maintenance. This chapter traces the important ideas of modern programming languages to their roots in the problems and languages of the past decade and shows how these modern languages respond to contemporary problems in software development. Modern programming’s key concept for controlling complexity is abstraction — that is, selective emphasis on detail. New developments in programming languages provide ways to support and exploit abstraction techniques.

This paper describes a software specification methodology based on the notion of concept specialization. The methodology, which is particularly useful for Information Systems, applies uniformly to the various components of such systems, such as data classes, transactions, exceptions, and user interfaces (scripts), and its goal is the systematic and structured description of highly detailed world models, where concepts occur in many variations. An example from the domain of university information systems is used to illustrate and motivate the approach.

It has been said many times that semantic nets are mere notational variants of predicate calculus. But before we lay down our nets, we ought at least to be clear about what predicate calculus is. We will attempt to make some clarifications in this regard. We also devote some attention to the notions of semantic nets. In the end, we simply plead, for an open mind.

This chapter describes some problems and opportunities associated with conceptual modelling for the kind of “open systems” we foresee developing in the future. Computer applications will be based on communication between subsystems that will have been developed separately and independently. Some of the reasons for independent development are: competition, economics, geographical distribution, and diverse goals and responsibilities. We must deal with all the problems that arise, from conceptual disparities. Subsystems will be open-ended and incremental — undergoing continual evolution. There are no global objects. The only thing that all the various subsystems hold in common is the ability to communicate with each other. Message Passing Semantics is a methodology that we are developing to deal with highly parallel, distributed, open systems. Various aspects of this methodology deal with communication, description, transaction management, problem solving, change, completeness, and self-knowledge.

Some formal representation issues underlying the use of incomplete knowledge bases are discussed. An incomplete knowledge base is one that has only partial knowledge of the application domain. It is argued that a language that can refer to both the application domain and to the state of the knowledge base is required to specify and to question an incomplete knowledge base. A formal logical language with this expressive ability is presented and its semantics and proof theory are defined. It is also shown how different the use of the language must be, depending on whether the interaction involves querying or defining the knowledge base.

Insofar as database theory can be said to owe a debt to logic, the currency on loan is model theoretic in the sense that a database can be viewed as a particular kind of first order interpretation, and query evaluation is a process of truth functional evaluation of first order formulae with respect, to this interpretation. It is this model theoretic paradigm which leads, for example, to many valued propositional logics for databases with null values.

In this chapter I argue that a proof theoretic view of databases is possible, and indeed much morefiruitful. Specifically, I show how relational databases can be seen as special theories of gist order logic, namely theories incorporating the fiollowing assumptions:

It will follow that a proof theoretic paradigm for relational databases provides a correct treatment of:

A plan calculus is presented that is used to represent programs as well as a library of standard data and control abstractions in the Programmer’s Apprentice. Important features of this formalism include programming language independence, additivity, verifiability, and multiple points of view. The logical foundations of the representation are specified formally by using a situational calculus in which side effects and overlapping mutable data structures are accounted for. The plan calculus is compared with other formalisms such as program schemas, and its advantages are pointed out.

A complete design and specification of database transactions must include both structural and behavioural properties. Structure deals with states and static properties while behaviour concerns state transitions and dynamic properties. Database design techniques emphasize the importance of behaviour but seldom provide for modelling and integrating behaviour and structure.

This chapter presents concepts, tools, and techniques for the design and specification of behavioural and structural properties of database transactions. The concepts, tools, and techniques result from the integration of programming language (PL) and database (DB) technologies. Design principles from PLs (e.g., abstraction and refinement), are applied to DB design and a new DB design principle, called localization, is proposed. PL concepts such as procedural abstractions, abstract data types, control structures, and specification techniques are integrated with DB concepts such as data abstractions, integrity constraints, data structures, and data models to produce a semantic data model for the conceptual design of databases and their associated transactions. The integration is based on the correspondence between the structure of complex databases and the structure of the associated transactions. In the proposed methodology, hierarchies of transactions and their constituent actions are designed in correspondence with the hierarchies designed to relate objects. As proposed in both artificial intelligence and PLs, design and specification are leveled. Gross design is done using graphic notation while detailed design is done using a conventional predicate based specification language. Appropriate concepts, tools, and techniques are presented for each level. The methodology is adequate for most database applications. However, complex and critical database applications (e.g., critical patient care, nuclear power plants) require precise, structured specifications. An appropriate formal specification technique, based on functional programming, is introduced. Formal specifications support increased precision and permit automated analysis and verification. The motivation for this work is similar to that for precise specifications in PLs. However, the existence of a database changes the nature of the problem and the required solution.

The relationship between this chapter and other chapters is presented in a concluding Epilogue.

The event model integrates a set of data structuring and manipulation primitives with a database schema design and evolution methodology. A number of database research efforts have concentrated on expanding the expressiveness of database modelling mechanisms in order to increase the understandability and usability of database conceptual schemas. The event model includes a simple set of such high-level “semantic” modelling constructs; an associated methodology provides prescriptive assistance in the task of specifying and maintaining a conceptual schema. A primary goal of this approach is to reduce the expertise required to design, evolve, and access databases. An interactive database design and evolution system based upon the event model has been implemented and is in use on an experimental basis.

This chapter suggests two mechanisms for adding semantic knowledge to a data manager, namely inclusion of an AI oriented rules system and a particular use of abstract data types. Both topics are explored in the context of the INGRES relational database system.

During the last decade, much research has been done in the field of data abstraction techniques in programming languages (see the chapter by Shaw), and higher-level data models for databases [CODD70] [CHEN76] [SS77b]. It is thus not surprising that researchers have begun to attempt to integrate databases and programming languages (i.e., by providing definitional and manipulative primitives for databases in the programming language that is consistent in philosophy with its existing data and control structures). The work in PASCAL/R (see the chapter by Mall, Reimer, and Schmidt) and PS-ALGOL [ACC82] are examples of such attempts made in the context of compiled, imperative (ALGOL-like) languages. This chapter describes our ideas on integrating databases into an interactive, applicative (Lisp-like) programming system.

Data types have played a key role in the design of the programming language Ada. Issues concerning the separation of logical properties, implementation and physical representation, the isolation of static and dynamic properties of data, the abstraction from and hiding of implementation details, and the parameterization of type definitions had to be addressed. The design motivations and specific solutions of Ada are presented and illustrated by numerous examples. An extension of Ada by concepts of formal specification is briefly sketched.

Fully fledged database systems have operational characteristics not commonly provided by programming language systems. Examples of this would be access and integrity control, failure recovery, data sharing, and concurrency management.

This chapter discusses the way in which programming language constructs (such as data structures and their selection mechanisms, scope rules, procedures, modules, and variable import and passing mechanisms) can be utilized to support the above operational characteristics in the context of an integrated database programming environment.

Programming languages, database systems, and artificial intelligence systems all have the notion that entities can be classified into types. As might be expected, however, the usage of the notion of type is not the same among or even within these areas. This chapter presents a view of type that is based on work in programming languages. This view is then used to indicate how the programming languages and database systems can be integrated to produce a more powerful modelling environment.

I would like to address three issues: various aspects of generality, problem solving versus algorithmic systems, and communication.

PL researchers are like good craftsmen; they choose tools very carefully and are concerned with quality and esthetics. They are also some what parochial, refusing to deal with issues such as I/O and persistent objects that are of great real world concern. Although PL people claim to add new tools and features to their tool kit, it takes a long time for new ideas from other areas to be incorporated into their languages.

My view is not restricted to classical programming languages. I am interested in formal languages that are used for manipulating things in general. I would like to argue that a language is a structure used for describing combinations of actions and objects. This definition includes Pascal as well as menu systems. The important notion underlying the definition is that of combination. Good language design is the process of combining features into an itegrated whole. A good example is Pascal/R, which introduces the concept of relation into Pascal as a data type. Another example, ARGUS, adds the notion of a database transaction to CLU.