electronically available articles

Updated 2011-09-03

**
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.

**
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.

**
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
.

**
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
.

**
M. Johnson and R. Rosebrugh
**

LNCS, 5140, 232-237, 2008.

Available in
pdf
.

**
M. Johnson and R. Rosebrugh
**

LNCS, 5140, 238-252, 2008.

Available in
pdf
.

**
Michael Johnson and Robert Rosebrugh.
**

Invited book chapter.

Available in
pdf
.

**
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), 109–129.

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 .

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 .

**
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 .

**
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 *null*s). Instead,
we usually analyse a clean data model based on assumptions about
complete information, and later retrofit support for *null*s.
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 .

**
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 .

**
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 *Journal of Pure and Applied Algebra* 175(2002), 327--353 (Kelly
Volume).

**
M. Johnson and R. Rosebrugh.
**

ENTCS,
Volume 61, 6, 1-13, 2002.

[ ps.gz (~50k) | ps (~130k) ]
© Elsevier Science

**
M. Johnson and R. Rosebrugh.
**

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

**
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

**
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 .

**
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 .

**
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 .

**
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.

**
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).

**
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 .

**
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 .

**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 .

**
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.

**
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

**
M. Fleming, R. Gunther and R. Rosebrugh
**

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

**
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.
*

**
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.

**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.

**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.

**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.

**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.