Abstracts -
electronically available articles

Updated 2011-09-03


Lenses, fibrations and universal translations.

Michael Johnson, Robert Rosebrugh and R.J. Wood

This article is extends the ``lens'' concept for view updating in Computer Science beyond the categories of sets and ordered sets. It is first shown that a constant complement view updating strategy also corresponds to a lens for a categorical database model. A variation on the lens concept called c-lens is introduced, and shown to correspond to the categorical notion of Grothendieck opfibration. This variant guarantees a universal solution to the view update problem for functorial update processes.
Mathematical Structures in Computer Science, Vol. 22, 2012, 25-42. Available in pdf.


Completely and Totally Distributive Categories I

F. Marmolejo, R. Rosebrugh and R. J. Wood

In 1978, Street and Walters defined a locally small category K to be totally cocomplete if its Yoneda functor Y has a left adjoint X. Such a K is totally distributive if X has a left adjoint W. Small powers of the category of small sets are totally distributive, as are certain sheaf categories. A locally small category K is small cocomplete if it is a P-algebra, where P is the small-colimit completion monad on Cat. In 2007, Day and Lack showed that P lifts to R-algebras, where R is the small-limit completion monad on Cat. It follows that there is a distributive law RP to PR and we say that K is completely distributive if K is a PR-algebra, meaning that K is small cocomplete, small complete, and the P structure preserves small limits. Totally distributive implies completely distributive. We show that there is a further supply of totally distributive categories provided by categories of interpolative bimodules between small taxons as introduced by Koslowski in 1997.
Available in pdf.


Algebras and update strategies.

Michael Johnson, Robert Rosebrugh and R.J. Wood

The correspondence between view update translations and views with a constant complement reappears more generally as the correspondence between update strategies and meet complements in the order based setting of S. Hegner. We show that these two theories of database view updatability are linked by the notion of lens which is an algebra for a monad. We generalize lenses from the category of sets to consider them in categories with finite products, in particular the category of ordered sets.
Journal of Universal Computer Science, Vol. 16, 2010, 729 - 748.
Available in pdf .


Duality for CCD lattices

F. Marmolejo, R. Rosebrugh and R. J. Wood

The 2-category of constructively completely distributive lattices is shown to be bidual to a 2-category of generalized orders that admits a monadic schizophrenic object biadjunction over the 2-category of ordered sets.
Theory and Applications of Categories, Vol. 22, 2009, pp 1-23
Available in dvi and ps and pdf .


Implementing a categorical information system.

M. Johnson and R. Rosebrugh

LNCS, 5140, 232-237, 2008.
Available in pdf .


Constant complements, reversibility and universal view updates.

M. Johnson and R. Rosebrugh

LNCS, 5140, 238-252, 2008.
Available in pdf .


Ontology engineering, universal algebra and category theory.

Michael Johnson and Robert Rosebrugh.

Invited book chapter.
Available in pdf .


Fibrations and universal view updatability

M. Johnson and R. Rosebrugh

Maintainability and modifiability of information system software can be enhanced by the provision of comprehensive support for views, since view support allows application programs to continue to operate unchanged when the underlying information system is modified. Supporting views depends upon a solution to the view update problem. This paper presents a new treatment of view updates for formally specified semantic data models based on the category theoretic sketch data model. The sketch data model has been the basis of a number of successful major information system consultancies. We define view updates by a universal property in models of the formal specification, and explain why this indeed gives a complete and correct treatment of view updatability, including a solution to the view update problem. However, a definition of updatability which is based on models causes some inconvenience in applications, so we prove that in a variety of circumstances updatability is guaranteed independently of the current model. This is done first with a very general criterion, and then for some specific cases relevant to applications. We include some detail about the sketch data model, noting that it involves extensions of algebraic data specification techniques. This has appeared as:
Theoretical Computer Science 388 (2007), 109129.

Available in dvi and pdf .


Generic commutative separable algebras and cospans of graphs

R. Rosebrugh, N. Sabadini and R. F. C. Walters

We show that the generic symmetric monoidal category with a commutative separable algebra which has a $\Sigma$-family of actions is the category of cospans of finite $\Sigma$-labelled graphs restricted to finite sets as objects, thus providing a syntax for automata on the alphabet $\Sigma$. We use this result to produce semantic functors for $\Sigma$-automata. This has appeared as:
Theory and Applications of Categories, Vol. 15, 2005, pp 164-177

Available in dvi and ps and pdf .


Split structures

R. Rosebrugh and R.J. Wood

In the early 1990's the authors proved that the full subcategory of `sup-lattices' determined by the constructively completely distributive (CCD) lattices is equivalent to the idempotent splitting completion of the bicategory of sets and relations. Having many corollaries, this was an extremely useful result. Moreover, as the authors soon suspected, it specializes a much more general result.

Let D be a monad on a category C in which idempotents split. Write kar(C_D) for the idempotent splitting completion of the Kleisli category. Write spl(C^D) for the category whose objects are pairs ((L,s),t), where (L,s) is an object of the Eilenberg-Moore category for D, and t is a homomorphism that splits s, with spl(C^D)(((L,s),t),((L',s'),t'))=C^D((L,s)(L',s')).

The main result is that kar(C_D) is isomorphic to spl(C^D). We also show how this implies the CCD lattice characterization theorem and consider a more general context. This has appeared as:
Theory and Applications of Categories, Vol. 13, 2004, pp 172-183

Available in dvi and ps and pdf .


Minimization and Minimal Realization in Span(Graph)

R. Rosebrugh, N. Sabadini and R.F.C. Walters

The context of this article is the program to study the bicategory of spans of graphs as an algebra of processes, with applications to concurrency theory. The objective here is to study functorial aspects of reachability, minimization and minimal realization. The compositionality of minimization has application to model-checking. Mathematical Structures in Computer Science, 14(2004), 685-714.

Available in dvi , ps and pdf .


Three approaches to partiality in the sketch data model

M. Johnson and R. Rosebrugh

Partial information is common in real-world databases. Yet the theoretical foundations of data models are not designed to support references to missing data (often termed nulls). Instead, we usually analyse a clean data model based on assumptions about complete information, and later retrofit support for nulls. The sketch data model is a recently developed approach to database specification based on category theory. The sketch data model is general enough to support references to missing information within itself (rather than by retrofitting). In this paper we explore three approaches to incorporating partial information in the sketch data model. The approaches, while fundamentally different, are closely related, and we show that under certain fairly strong hypotheses they are Morita equivalent (that is they have the same categories of models, up to equivalence). Despite this equivalence, the query languages arising from the three approaches are subtly different, and we explore some of these differences. Has appeared as ENTCS, Volume 78, 1-18, 2003.

Available in pdf .


Coherence for Factorization Algebras

R. Rosebrugh and R. J. Wood

For the 2-monad $((-)^2,I,C)$ on CAT, with unit $I$ described by identities and multiplication $C$ described by composition, we show that a functor $F : {\cal K}^2 \rightarrow \cal K$ satisfying $FI_{\cal K} = 1_{\cal K}$ admits a unique, normal, pseudo-algebra structure for $(-)^2$ if and only if there is a mere natural isomorphism $F F^2 \rightarrow F C_{\cal K}$. We show that when this is the case the set of all natural transformations $F F^2 \rightarrow F C_{\cal K}$ forms a commutative monoid isomorphic to the centre of $\cal K$. This has appeared as:
Theory and Applications of Categories, Vol. 10, 2002, pp 134-147

Available in dvi and ps and pdf .


Distributive Laws and Factorization

R. Rosebrugh and R. J. Wood

This article shows that the distributive laws of Beck in the bicategory of sets and matrices, wherein monads are categories, determine strict factorization systems on their composite monads. Conversely, it is shown that strict factorization systems on categories give rise to distributive laws. Moreover, these processes are shown to be mutually inverse in a precise sense. Strict factorization systems are shown to be the strict algebras for the 2-monad (-)^2 on the 2-category of categories. Further, an extension of the distributive law concept provides a correspondence with the classical orthogonal factorization systems. Has appeared in Journal of Pure and Applied Algebra 175(2002), 327--353 (Kelly Volume).

Available in dvi and pdf .


Sketch Data Models, Relational Schema and Data Specifications.

M. Johnson and R. Rosebrugh.

ENTCS, Volume 61, 6, 1-13, 2002.
[ ps.gz (~50k) | ps (~130k) ] © Elsevier Science

Available in ps and pdf .


Semantics: Initial, Absolute, and Relative

M. Johnson and R. Rosebrugh.

Proceedings of the Tenth OOPSLA Workshop on Behavioral Semantics, Tampa, Florida, October 2001, 121-132.


Reverse Engineering Legacy Information Systems for Internet Based Interoperation.

M. Johnson and R. Rosebrugh.

Has appeared as Proceedings of the IEEE Conference on Software Maintenance, 32--39, 2001.
[ ps.gz (~73k) | ps (~165k) ] © IEEE

Available in ps and pdf .


Update Algorithms for the Sketch Data Model

M. Johnson and R. Rosebrugh.

The authors have developed a new approach to database interoperability using the sketch data model. An important question is: What are the algorithms that support updates in the sketch data model? The question arises since the sketch data model uses EA-sketches to specify data structures, and these include constraint and other information not normally supported by relational database systems. In this paper we answer the question by providing a formal definition of insert update together with an algorithm which provably achieves updates. The algorithm treats data and constraints on an equal categorical footing. Further exactness properties (limits and colimits) can aid specification, and we provide algorithms for updates of EA sketched databases with finite limits. The sketch data model is being used in industry for designing interoperations for computer supported cooperative work and CASE tools are under development. In press for CSCWD2001, the Fifth International Conference on Computer Supported Cooperative Work in Design, London, Ontario, 2001.

Available in pdf .


View Updatability Based on the Models of a Formal Specification.

M. Johnson and R. Rosebrugh.

Information system software productivity can be increased by improving the maintainability and modifiability of the software produced. This can be achieved by the provision of support for views. Supporting views depends on a solution to the view update problem. This paper presents a new treatment of view updates. The formal specification technique we use is based on category theory and has been the basis of a number of successful major information system consultancies. We define view updates by a universal property in a subcategory of models of the formal specification, and explain why this indeed gives a comprehensive treatment of view updatability, including a solution to the view update problem. A definition of updatability which is based on models causes inconvenience in applications, so we prove that in a variety of circumstances updatability is guaranteed independently of the current model. The solution to the view update problem can be seen as requiring the existence of an initial model for a specification. LNCS, 2021, 534-549, 2001.

Available in pdf .


View Updates in a Semantic Data Modelling Paradigm.

C.N.G. Dampney, M. Johnson and R. Rosebrugh.

This paper describes the sketch data model and investigates the view update problem (VUP) in the sketch data model paradigm. It proposes an approach to the VUP, and presents a range of examples to illustrate the scope of the proposed technique. We define under what circumstances a view update can be propagated to the underlying database. Unlike many previously proposed approaches the definition is succinct and consistent, without ad hoc exceptions, and the propagatable updates form a broad class. The examples demonstrate that under a range of circumstances a view schema can be shown to have propagatable views in all states, and thus state-independence can frequently be recovered. Proceedings of the twelfth Australasian Database Conference ADC2001, 29--36, IEEE Press, 2001.

Available in pdf .


Database Interoperability Through State Based Logical Data Independence.

M. Johnson and R. Rosebrugh.

Computer supported cooperative work (CSCW) depends more and more upon database interoperability. The design of interbusiness CSCW when the businesses are already operating independent systems depends either upon effective reverse engineering, or upon sufficiently rich semantic models and good database management system support for logical data independence. This paper takes the second approach presenting a rich semantic data model that the authors have been developing and have used successfully in a number of major consultancies, and a new approach to logical data independence and view updatability based on that model. We show how these approaches support database interoperability for business-to-business transactions, and, for CSCW within an organisation, how they support federated databases. Proceedings of CSCW2000, the Fourth International Conference on Computer Supported Collaborative Work, IEEE Hong Kong, 161-166, 2000.

Available in ps and pdf.


A basic distributive law

F. Marmolejo, R. Rosebrugh and R. J. Wood

We pursue distributive laws between monads, particularly in the context of KZ-doctrines, and show that a very basic distributive law has (constructively) completely distributive lattices for its algebras. Moreover, the resulting monad is shown to be also the double dualization monad (with respect to the subobject classifier) on ordered sets. Journal of Pure and Applied Algebra 168(2002), 209-226 (Coimbra Volume).

Available in dvi and pdf .


Boundedness and complete distributivity

R. Rosebrugh and R. J. Wood

We extend the concept of constructive complete distributivity so as to make it applicable to ordered sets admitting merely {\em bounded} suprema. The KZ-doctrine for bounded suprema is of some independent interest and a few results about it are given. The 2-category of ordered sets admitting bounded suprema over which non-empty infima distribute is shown to be bi-equivalent to a 2-category defined in terms of idempotent relations. As a corollary we obtain a simple construction of the non-negative reals. Appear in Applied Categorical Structures, 9(2001), pp 437-456.

Available in dvi and ps and pdf .


Entity-relationship-attribute designs and sketches

M. Johnson, R. Rosebrugh and R. J. Wood

Entity-Relationship-Attribute ideas are commonly used to specify and design information systems. They use a graphical technique for displaying the objects of the system and relationships among them. The design process can be enhanced by specifying constraints of the system and the natural environment for these is the categorical notion of sketch. Here we argue that the finite-limit, finite-sum sketches with a terminal node are the appropriate class and call them EA sketches. A model for an EA sketch in a lextensive category is a `snapshot' of a database with values in that category. The category of models of an EA sketch is an object of models of the sketch in a 2-category of lextensive categories. Moreover, modelling the {\em same} sketch in certain objects in other 2-categories defines both the query language for the database and the updates (the dynamics) for the database. This article has appeared in Theory and Applications of Categories 10(2002), 94-112.

Available in dvi and ps and pdf .


Minimal realization in bicategories of automata

R. Rosebrugh, N. Sabadini and R.F.C. Walters

The context of this article is the program to develop monoidal bicategories with a feedback operation as an algebra of processes, with applications to concurrency theory. The objective here is to study reachability, minimization and minimal realization in these bicategories. In this setting the automata are 1-cells in contrast with previous studies where they appeared as objects. As a consequence we are able to study the relation of minimization and minimal realization to serial composition of automata using (co)lax (co)monads. We are led to define suitable behaviour categories and prove minimal realization theorems which extend classical results. Mathematical Structures in Computer Science, 8(1998), 93-116.

Available in dvi and ps and pdf .


A database of categories

M. Fleming, R. Gunther and R. Rosebrugh

We describe a program which facilitates storage and manipulation of finitely-presented categories and finite-set valued functors. It allows storage, editing and recall of finitely-presented categories and functors. Several tools for testing properties of objects and arrows, and the computation of right and left kan extensions are included. The program is written in ANSI C and is menu-based. Use of the program requires a basic knowledge of category theory. Journal of Symbolic Computation 35(2003), 127-135.

Available in dvi and pdf .


User Guide for a database of categories

M. Fleming, R. Gunther and R. Rosebrugh

A guide to use of a C program which allows storage and manipulation of finitely presented categories and functors, including Kan extensions of finite-set valued functors.

Available in dvi and pdf files, and here is an abridged version


Guide to data structures and algorithms for a database of categories

M. Fleming, R. Gunther and R. Rosebrugh

A technical manual for users of the program described in the preceding abstract.

Available in dvi and pdf .


Distributive adjoint strings

R. Rosebrugh and R. J. Wood

For an adjoint string V -| W -| X -| Y : B --> C, with Y fully faithful, it is frequently, but not always, the case that the composite VY underlies an idempotent monad. When it does, we call the string distributive. We also study shorter and longer `distributive' adjoint strings and how to generate them. These provide a new construction of the simplicial 2-category, Delta. This article has appeared in Theory and Applications of Categories 1(1995), 119-145.

Available in dvi and pdf .


An adjoint characterization of the category of sets

R. Rosebrugh and R. J. Wood

If a category B with Yoneda embedding Y : B ---> CAT(B^op,set) has an adjoint string, U -| V -| W -| X -| Y, then B is equivalent to set. This paper has appeared in Proceedings of the American Mathematical Society 122(1994), 409-413.

Available in dvi and pdf .


Relational Databases and Indexed Categories

R. Rosebrugh and R.J. Wood

A description of relational databases in categorical terminology given here has as intended application the study of database dynamics, in particular we view (i) updates as database objects in a suitable category indexed by a topos; (ii) L-fuzzy databases as database objects in sheaves. Indexed categories are constructed to model the databases on a fixed family of domains and also all databases for a varying family of domains. Further, we show that the process of constructing the relational completion of a relational database is a monad in a 2-category of functors. This paper has appeared in the Proceedings of the 1991 Category Theory Meeting, published by the AMS.

Here are the dvi and pdf files.


Constructive complete distributivity IV

R. Rosebrugh and R. J. Wood

A complete lattice L is constructively completely distributive, ccd, when the sup arrow from down-closed subobjects of L to down-closed subobjects of L has a left adjoint. The Karoubian envelope of the (bi-)category of relations is equivalent to the (bi-)category of ccd lattices and sup-preserving arrows. The equivalence restricts to an equivalence between ideals and ``totally algebraic'' lattices. Both equivalences have left exact versions. As applications we characterize projective sup lattices and recover a known characterization of projective frames. Also, the known characterization of nuclear sup lattices in set as completely distributive lattices is extended to an equivalence with ccd lattices in a topos. This paper has appeared in Applied Categorical Structures 2(1994), 119-144.

Here are the dvi and pdf files.


Constructive Complete Distributivity III

R. Rosebrugh and R.J. Wood

A complete lattice L is constructively completely distributive, (CCD)(L), if the sup map defined on down closed subobjects has a left adjoint. We characterize preservation of this property by left exact functors between toposes using a ``logical comparison transformation''. The characterization is applied to (direct images of) geometric morphisms to show that local homeomorphisms (in particular, product functors) preserve (CCD) objects, while preserving (CCD) objects implies openness. This paper has appeared in the Canadian Mathematical Bulletin 35(1992), 537-547.

Here are the dvi and pdf files.


Constructive Complete Distributivity II

R. Rosebrugh and R.J. Wood

A complete lattice L is constructively completely distributive, (CCD)(L), if the sup map defined on down-closed subobjects has a left adjoint. It was known that in boolean toposes (CCD)(L) is equivalent to (CCD)(L\op). We show here that the latter property for all L (sufficiently, for Omega) characterizes boolean toposes. This paper has appeared in the Mathematical Proceedings of the Cambridge Philosophical Society, 110(1991) pp. 245-249.

Here are the dvi and pdf files.