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