Transcript Anticipation in constructing and interrogating Natural

Anticipation in constructing
and interrogating Natural
Information Systems:
From Classical through Nano to
Quantum Computing
Authors
• B. Nick Rossiter, Informatics, Northumbria
University, Newcastle upon Tyne, UK, NE1
8ST, [email protected]
• M. A. Heather, Sutherland Building,
Northumbria University, NE1 8ST,
[email protected]
Weak Anticipation in Classical
Databases
• Today’s classical information systems anticipate the real
world.
• Databases store, organise and search collections of realworld data.
• In terms of anticipatory systems,
– Reductionism and normalisation are needed with von
Neumann architectures consisting of fixed instructions
between bit cells.
– Hence weak anticipatory as information systems
(databases) are constructed using classical methods
Developing non-classical Areas
• The new developing areas are:
– quantum computation, exploiting quantum mechanics
principles in physics,
– nanoscale chemistry,
– bio- and molecular-computing processing as in genetics
• Natural computing is:
– Real-world processing
• does not rely on any model.
– Data can be input neat
• without any reductionist pre-processing.
• The corresponding information system or database using
natural computing should therefore be strong
Classical Database Techniques
• The multilevel ANSI/SPARC architecture.
• Three layers and the mappings between them:
External Schema
Conceptual Schema
Internal Schema
views derived for end-users
from the conceptual schema
describing the data in terms
of types
addressing the layout
of data on disk
The mappings between schemas are algebraic or calculus expressions.
Non-classical Architecture
• Not layered (Theory of Categories)
• Use Dolittle approach (push me-pull you creature of High Lofting):
• Actually matches SQL standard approach where layering is not
enforced
C
CI E
I
E
C conceptual schema
I Internal schema
E external schema
Classical Relationships
• Relationships are often performed in a separate process:
– Entity-Relationship Modelling
– Unified Modelling (UML)
• Normalisation is needed to verify schema design:
– particularly to relate key and non-key attributes.
• The levels, mappings and relationships all have to be
integrated in a consistent database design.
Non-classical Database Design
• Formally a database design is a topos and
representable as a Dolittle diagram
subsuming the pullback/pushout
relationships as:
Cartesian Closed
Category
X
+
f*
What is f*?
• f* is an examination and re-indexing functor
– organises the data into a key for storage and applies a
query for interrogation of the database.
– puts together a key by concatenation as in the relational
model.
– looks up information for retrieval by inspecting the key.
• In quantum theory:
– the key (X) is entanglement,
– the colimit (+) is superposition,
• In genetics it is a DNA strand.
Enriched Pullback
• In terms of the Dolittle diagram:
– f* is the same operation in classical and natural
computation.
• What then corresponds to the database schema in
natural computing?
• The pullback diagram contains many more arrows
than in the Dolittle diagram.
• This enriched diagram satisfies our needs.
Pullback of S and M in Context of IMG
ls x m
S
s
ls x m

S XIMG M

rs x m 
s x m *m
M
s
(s)-1
m
(m)-1
W/IMG
Figure 2: Pullback showing fuller collection of arrows
S = source, M = medium, IMG = image, W = world
Contents of Enriched Dolittle
• The Dolittle diagram relates binary categorial limits (X)
and colimits (+) for types
• Includes Heyting implication in intuitionistic logic.
• The pullback functor (f*) looks for:
– a particular sub-limit to represent a relationship,
– emulating the join operation of databases (*).
• Other arrows represent:
– projection 
– existential  quantification
– universal  quantification
Higher-level Arrows
• Originality with the unit of adjunction 
– Example:  gives properties of relationship onto limit
–  = 0, no creativity, mapping S to S XIMG M is 1:1
–  = 1, maximum creativity, mapping S to S  IMG M is from S to
cartesian product of S  M.
• Style with the counit  of adjunction.
– Example:  gives properties of relationship onto colimit
–  = 1, preservation of style, each S is found exactly once in S XIMG
M
–  = 0, loss of style, each S occurs in S  IMG M maximum number
of times (S  M).
• The Dolittle diagram is the universal relation with all
possible relationships in parallel.
Work with Databases and
Categories
• Michael Johnson, Robert Rosebrugh and RJ
Wood, Entity-Relationship-Attribute
Designs and Sketches, TAC 10(3) 94-111.
– sketches for design (class structure)
– models for states (objects) where model is used
in categorical sense
– lextensive category (finite limits, stable disjoint
finite sums) for query language
More details for Sketches
• 12 different types:
– See Wells, C, (1993), Sketches: Outline with References at
http://www.cwru.edu/artsci/math/wells/pub/pdf/sketch.pdf
• Employed also in databases by:
– Zinovy Diskin, Boris Cadish: Algebraic Graph-Based Approach to
Management of Multidatabase Systems, NGITS’95 69-79 (1995).
• Sketch idea originally from Charles Ehresmann.
– Finite Discrete (FD) sketch D = (E, L, R, S)
• finite graph E (data structure)
• set of diagrams L in E (constraints)
• Finite set R of discrete cones in D (relationships)
• Finite set S of discrete cocones in D (attributes)
Models from Sketches
• Model (M) – sketch homomorphism
• maps any E to category V where V is a database state
• L  commutative diagrams, R  limit cones, S  colimit
cocones
• preserve products
• the more detailed the sketch, the less nice the model
• strength of anticipation depends on nature of model
• In FD sketches in Johnson et al:
• finite sums satisfy the lextensive axiom
• sums are well-behaved
View on Sketches
• Intuitively appealing as match categorial concepts with
those of information systems
• In sketches:
– The cones match X in Dolittle for design giving
relationships
– The cocones match + in Dolittle.for design giving
attributes
– The graph matches C in Dolittle for schema
– The set of diagrams that will commute is not in Dolittle
• all our diagrams commute.
• Good equivalence but our constructions are more
general in further mappings as in interoperability.
Other Recent Work
• Grover has developed the idea of using quantum algorithms for faster
searching of databases
• Selinger has produced a collection of operations at such a level that
they could form the basis of a quantum programming language.
• Both offer potential for the development of quantum databases.
• However, databases in general require a conceptual level for the
representation, querying and updating of data.
• The present approach is not yet at the f* conceptual level:
– relies on low-level operations analogous to classical methods
– like the CNOT gate (controlled NOT gate) where two input qubits,
control and target, are xor'd and stored in a target qubit B + A.
• As a kind of f*, Grover makes use of the 'oracle', treated as a black box
and used for collapsing the wave function, that is to determine when a
solution has been derived.
– However, this form of the oracle lacks non-locality
Discussion
• What is the status for natural computing as a
strong anticipatory system?
• Nano-computation may be a separate transitional
phase between and distinct from classical and
quantum processors.
• Issue remains whether natural, nano and quantum
computing are all facets of the same operation.
• Anticipatory systems theory latent in the Dolittle
diagram suggests they are all the same.
• If the Dolittle diagram is much closer to reality
than most models, it is a strong anticipatory
system.
References
[1] Adleman, L, On constructing a molecular computer, DNA based
computers, Lipton, R, and Baum, E, (edd), DIMACS, American
Mathematical Society 1-21 (1996).
[2] Grover L K, A fast quantum mechanical algorithm for database
search, Proc 28th Annual ACM Symposium Theory of Computing
212-219 (1996).
[3] Heather, M A, & Rossiter, B N, Locality, Weak or Strong Anticipation
and Quantum Computing I. Non-locality in Quantum Theory,
International Journal Computing Anticipatory Systems 13 307-326
(2002).
[4] Heather, M A, & Rossiter, B N, Locality, Weak or Strong Anticipation
and Quantum Computing. II. Constructivism with Category Theory,
International Journal Computing Anticipatory Systems 13 327-339
(2002).
[5] Selinger, P, Towards a Quantum Programming Language, 42pp,
http://quasar.mathstat.uottawa.ca/~selinger/papers.html#qpl (2002).