This paper presents a methodology for logical design of relational schemas and integrity constraints
using semantic binary schemas. This is a top-down methodology. In this methodology,
a conceptual description of an enterprise is designed using a semantic binary model.
Then, this description is converted into the relational database design.
Sunday, November 18, 2007
A Methodology and Tool for Top-down Relational Database Design
THE HISTORICAL RELATIONAL DATA MODEL (HRDM) AND ALGEBRA BASED ON LIFESPANS
Critical to the design of an historical database model is the representation of the existence of objects across the temporal dimension — for example, the "birth," "death," or "rebirth" of an individual, or the establishment or dis-establishment of a relationship. The notion of the "lifespan" of a database object is proposed as a simple framework for epressing these concepts. An object's lifespan is simply those periods of time during which the database models the properties of that object. In this paper we propose the historical relational data model (HRDM) and algebra that is based upon lifespans and that views the values of all attributes as functions from time points to simple domains. The model that we obtain is a consistent extension of the relational data model, and provides a simple mechanism for providing both time-varying data and time-varying schemes.
Monday, September 03, 2007
Reducibility Between Classes of Port Graph Grammar
... by Charles Stewart (a.k.a. cas).
It is interesting to compare reducability results for PGGs with those for JCs (especially general SPGG in basic SPGG to general JC in core JC).
As a side note, I start to become uneasy with too complicated encodings... There should be some more fine-grained equivalence than an ability to encode one transformation system in another (something along the lines of expressivity).
For example, the standard encoding of general JC in core JC is not homomorphic in constructs of core JC - implying it is not identity on core JC terms - so this encoding does not prove expressibility of general JC in core JC Felleisen-wise.
PS: linearity.org seems to be down for some reason.
It is interesting to compare reducability results for PGGs with those for JCs (especially general SPGG in basic SPGG to general JC in core JC).
As a side note, I start to become uneasy with too complicated encodings... There should be some more fine-grained equivalence than an ability to encode one transformation system in another (something along the lines of expressivity).
For example, the standard encoding of general JC in core JC is not homomorphic in constructs of core JC - implying it is not identity on core JC terms - so this encoding does not prove expressibility of general JC in core JC Felleisen-wise.
PS: linearity.org seems to be down for some reason.
Saturday, September 01, 2007
Core Join Calculus - too hardcore?
After looking closely at core JC, and the proposed encoding of full JC in it, I found it unsatisfactory for my taste.
One problem is that the encoding results in "busy-wait" (stuttering non-termination), even if the original term was "normalizing", which makes the chosen notion of equivalence suspicious. Also, the encoding is sufficiently complicated to ask whether analysis of the resulting terms will be not harder than that of original ones (I recognize that analysis of core JC as a language is easier than of full JC, though - that's the usual trade-off between complexity of a language and its terms, sometimes exemplified by English vs. Chinese, or binary vs. hex).
So maybe I want to take a step back, and pick some variant of JC that is not as spartan as core JC. At the moment I see 3 differences between full and core JCs:
1. Polyadic vs. monadic messages (tuples of channels vs. single channels as payload).
2. N joins per definition vs. 1 join per definition.
3. M patterns per join vs. 2 pattern per join.
I am considering to look closer at the "monadic N M" variant, though in theory one could analyse all combinations, and how they can be encoded in each other (could make a PhD thesis :) ). If one adds to these 3 dimensions another one for allowing or disallowing free names in definitions, this yields 24 = 16 variants. I suspect, though, that one does not need to define encoding for each pair of combinations separately - they all could be factored via few "encoding patterns" (e.g., encoding of N-M JC in 1-2 JC, polyadic JC in monadic JC, and "higher order/closured" JC in "first order/closureless" JC).
One problem is that the encoding results in "busy-wait" (stuttering non-termination), even if the original term was "normalizing", which makes the chosen notion of equivalence suspicious. Also, the encoding is sufficiently complicated to ask whether analysis of the resulting terms will be not harder than that of original ones (I recognize that analysis of core JC as a language is easier than of full JC, though - that's the usual trade-off between complexity of a language and its terms, sometimes exemplified by English vs. Chinese, or binary vs. hex).
So maybe I want to take a step back, and pick some variant of JC that is not as spartan as core JC. At the moment I see 3 differences between full and core JCs:
1. Polyadic vs. monadic messages (tuples of channels vs. single channels as payload).
2. N joins per definition vs. 1 join per definition.
3. M patterns per join vs. 2 pattern per join.
I am considering to look closer at the "monadic N M" variant, though in theory one could analyse all combinations, and how they can be encoded in each other (could make a PhD thesis :) ). If one adds to these 3 dimensions another one for allowing or disallowing free names in definitions, this yields 24 = 16 variants. I suspect, though, that one does not need to define encoding for each pair of combinations separately - they all could be factored via few "encoding patterns" (e.g., encoding of N-M JC in 1-2 JC, polyadic JC in monadic JC, and "higher order/closured" JC in "first order/closureless" JC).
Thursday, August 30, 2007
Defunc'ed Join Calculus, now in Haskell
>module J where
This module defines alternative semantics for join calculus (JC) by means of providing an interpreter.
Major differences from standard semantics are:
1. "Kinda closure-converted/defunctionalized" form of object program
- we do not have nested definitions defining scope of names, all pieces of code are "kinda combinators".
2. Making code closed required introducing notion of object instances (data Obj).
- these objects are just identities (plus "vtable"), and could have been defined as just (Int, Code).
- however, this module models identity of the object as history of reactions (joins) that lead to its creation.
3. As all state is carried by messages, the history must be carried by them, as well.
- as a side-effect, we get unlimited stack-, err, graph-trace of the executed program!
- not that this is practical :)
>import Data.List as List
>import Data.Maybe (listToMaybe)
Let us model monadic JC, i.e., messages carrying just one channel as their body.
(see http://citeseer.ist.psu.edu/fournet95reflexive.html, Chapter 5).
Messages are the main part of the system, carrying all its mutable state.
"cause" is Nothing for primordial messages.
>data Msg = Msg {to::Channel, body::Channel, cause::Maybe Join} -- ("from" is redundant, as both causes have it as their "to")
> deriving (Eq, Ord)
>instance Show(Msg) where
> show (Msg t b Nothing) = (show t)++"("++(show b)++")"
> show (Msg t b (Just j)) = (show j)++" -> "++(show t)++"("++(show b)++")"
Join is just a couple of messages that reacted.
Forward reference: Messages of Join have equal "to", left one has L port id, right one has R.
>data Join = Join Msg Msg
> deriving (Eq, Ord)
>instance Show(Join) where
> show (Join m1 m2) = "<"++(show m1)++", "++(show m2)++">"
Channels are destinations of messages (and in standard monadic JC the only payload of messages).
Channels are identified by a pair of object identity and a port.
>data Channel = Ch {obj::Obj, port::PortId}
> deriving (Eq, Ord)
>instance Show(Channel) where
> show (Ch o p) = (show o)++""++(show p)
As this is core JC, each definition/code/object has just two channels, identified by their port ids - Left or Right.
>data PortId = L | R
> deriving (Show, Eq, Ord)
Obj is in fact a pair of object identity and procedure for handling messages ("kinda vtable").
Identity is formed by NewId qualified by birthjoin (think birthday).
"birthjoin" is Nothing for primordial objects.
TODO: "code" should not be a part of Eq's "key"
>data Obj = Obj {id::NewId, code::Code, birthjoin::Maybe Join}
> deriving (Eq, Ord)
>instance Show(Obj) where
> show (Obj i _ (Just j)) = (show j)++"->"++i
> show (Obj i _ Nothing) = i
NewId differentiates multiple objects created during reaction to the same join.
In more bytecode-like implementation this would be integer.
>type NewId = String
Code is the procedure to react to a join by creating new objects and sending new messages.
Code is closed, and the only input (capabilities!) it has are:
1. Its left and right channels - via ThisChannel
2. Messages in them (parts of the join causing the reaction) - via ThisMsg
3. Channels in newly created objects - via NewChannel
The reaction is a list of codes for new objects, keyed by their NewIds,
and a list of to/body references for new messages.
TODO: introduce datatypes for these pairs.
>data Code = Code [(NewId, Code)] [(Ref, Ref)]
> deriving (Show, Eq, Ord)
Reference - means for constructing capabilities.
>data Ref = ThisChannel PortId
> | ThisMsg PortId
> | NewChannel NewId PortId
> deriving (Show, Eq, Ord)
Config of the system is currently just a list of messages (order is important to define deterministic scheduling).
>type Config = [Msg]
Context is "a config with a hole". It is assumed that in this implementation hole is at the end of list.
>type Context = [Msg]
We follow the usual practice:
1. Find in the config a redex and its surrounding context.
2. Reduce redex.
3. Plug the result back.
One might use Danvy's refocusing here (link?),
but I am reluctant to optimize for speed just right now.
Just find the first(!) pair of messages having the same object and having left and right channels as destinations:
>findRedex :: Config -> Maybe (Join, Context)
>findRedex ms = listToMaybe $ [(Join m1 m2, ms \\ [m1, m2])| m1 <- ms, m2 <- ms, (obj $ to m1) == (obj $ to m2), (port $ to m1) == L, (port $ to m2) == R]
Basically translate capabilities to channels:
>reduce :: Join -> [Msg]
>reduce j@(Join l r) = (List.map s2m) sends where
> Code news sends = code this
> this = obj $ to l
> s2m (to, body) = Msg (r2c to) (r2c body) $ Just j
> r2c (ThisChannel p) = Ch this p
> r2c (ThisMsg L) = body l
> r2c (ThisMsg R) = body r
> r2c (NewChannel i p) = Ch (i2o i) p
> i2o i = case lookup i news of
> Just c -> Obj i c $ Just j
> Nothing -> error ("broken ref "++(show i))
Put result back into the hole:
>plugBack :: Context -> [Msg] -> Config
>plugBack c ms = c ++ ms
TODO: externalise scheduling out of findRedex/plugBack (probably use lazy evaluation - link?).
Now combine all three functions to make a single step:
>step :: Config -> Maybe Config
>step c = case findRedex c of
> Nothing -> Nothing
> Just (j@(Join l r), c2) -> Just $ plugBack c2 $ reduce j
And now the most dangerous part, as it is potentially non-terminating (unlike step):
>run :: Config -> Config
>run c = case step c of
> Nothing -> c
> Just c2 -> run c2
A few examples:
>c1 = Code [] [(ThisMsg L, ThisMsg R)]
>c2 = Code [] [(ThisMsg L, ThisChannel R), (ThisChannel L, ThisMsg R)]
>--c3 = Code [("x", c2)] [(ThisMsg L, NewChannel "x" L), (ThisMsg R, NewChannel "x" R)]
>ms1 = [Msg (Ch o1 L) (Ch o2 R) Nothing, Msg (Ch o1 R) (Ch o2 R) Nothing, Msg (Ch o2 L) (Ch o1 L) Nothing]
> where o1 = Obj "a" c1 Nothing ; o2 = Obj "b" c2 Nothing
Try "step ms1" and "run ms1" to get an idea.
The next installment should probably include a little compiler from LC terms to Config.
Monday, August 27, 2007
Programming Languages: Application and Interpretation
I have to find time to read this textbook - if only to verify my background.
Friday, August 24, 2007
"Defunctionalization" of Join Calculus
(See Defunctionalization at Work for a background on the defunctionalization technique, The reflexive CHAM and the join-calculus for a background on join calculus.) What I do is not really defunctionalization, but I miss the right term for that.
Lambda calculus can be encoded in join calculus (JC). Algebraic datatypes can be encoded in either. A decent functional PL (think ML) can be encoded in JC. Yesterday I had an idea of looking at the reversal of this encoding - take a JC term, and tell if it is an image of ML term under this encoding (similar in spirit to recovering user-lambdas from brutally CPSed terms). Better yet, take a JC term and split it into functional and (emmm...) superfunctional pieces.
Then I wandered into implementation ideas, and suddenly decided I need to explore some kind of first order JC. I mean, definitions in JC nest and form structures very similar in spirit to closures. What if I closure-convert JC semantics, tinker it a bit, and them put closures back?
I analyzed pages 5-6 of the JC paper, and started scribbling. Spoiled by UML, I didn't use sets or functions, only informal diagrams. "I'll validate it later", thought I.
Everything went fine, until I stumbled upon necessity to construct new instances. Need for elegant generation of fresh names and manifestedly safe references to them was what stopped me... Will have to check literature for inspiration.
Lambda calculus can be encoded in join calculus (JC). Algebraic datatypes can be encoded in either. A decent functional PL (think ML) can be encoded in JC. Yesterday I had an idea of looking at the reversal of this encoding - take a JC term, and tell if it is an image of ML term under this encoding (similar in spirit to recovering user-lambdas from brutally CPSed terms). Better yet, take a JC term and split it into functional and (emmm...) superfunctional pieces.
Then I wandered into implementation ideas, and suddenly decided I need to explore some kind of first order JC. I mean, definitions in JC nest and form structures very similar in spirit to closures. What if I closure-convert JC semantics, tinker it a bit, and them put closures back?
I analyzed pages 5-6 of the JC paper, and started scribbling. Spoiled by UML, I didn't use sets or functions, only informal diagrams. "I'll validate it later", thought I.
Everything went fine, until I stumbled upon necessity to construct new instances. Need for elegant generation of fresh names and manifestedly safe references to them was what stopped me... Will have to check literature for inspiration.
An Accidental Simula User: Luca Cardelli
A personal view of the history behind the calculus of objects!
Accidentally, just last night I considered playing with defunctionalized Join Calculus (a good topic for the next post).
Accidentally, just last night I considered playing with defunctionalized Join Calculus (a good topic for the next post).
Saturday, August 18, 2007
Analyzing the Environment Structure of Higher-Order Languages using Frame Strings
Besides tackling a really fundamental issue, the paper has an interesting preface.
Friday, July 13, 2007
Abstract And-Parallel Machines
I will have to persuade myself I never read this paper before, as reading it induces a deja vu in me.
Excellent stuff!
Excellent stuff!
Monday, July 09, 2007
Multiscale Scheduling: Integrating Competitive and Cooperative Scheduling in Theory and in Practice
They touch a lot of ideas I was vaguely exploring on this blog (hierarchical scheduling, scheduling as game, utility-driven scheduling).
E.g., DAG models are superficially similar to cobs (though cobs are not sequential tasks, they are atomic units of rewriting).
Hope this program will succeed!
E.g., DAG models are superficially similar to cobs (though cobs are not sequential tasks, they are atomic units of rewriting).
Hope this program will succeed!
Tuesday, July 03, 2007
Graph Rewriting Semantics for Functional Programming Languages
Something I should have read before pontificating on cobs :)
Sunday, June 24, 2007
Preventing Internet Denial-of-Service with Capabilities
A topic of DoS attacks has surfaced recently on LtU, so this paper may be relevant to PLs design enough.
Imagine combining Trickles with this scheme...
Imagine combining Trickles with this scheme...
Trickles - Stateless High Performance Networking
The Trickles network stack is a stateless replacement for TCP and the Berkeley sockets interface. It removes all per-connection state from one endpoint, typically the server, while providing important features such as congestion control, security of server-side state, and support for dynamic content.
In addition to markedly reduced memory overhead, our server-side stateless stack allows increased flexibility in redirecting network traffic at packet-level granularity, since any server can service any request regardless of past communications history. This enables new functionality in the network layer, such as transparent failover, load balancing, anycast services, and striped download.
I wonder, how well this can be bent to work with multicast.
Thursday, April 05, 2007
Work, work
This message is just to make sure Blogger does not write me off as MIA :)
My family and job responsibilities withdrew my attention from research and blogging, hope I will find some time soon to post some findings/ideas I had since January.
My family and job responsibilities withdrew my attention from research and blogging, hope I will find some time soon to post some findings/ideas I had since January.
Thursday, January 25, 2007
Punctuated Data Streams
We explore a kind of stream semantics called punctuated
streams. Punctuations in a stream mark the end of substreams, allowing us to view a
non-terminating stream as a mixture of terminating streams. We introduce three kinds of
invariants to specify the proper behavior of query operators in the presence of punctuation.
Pass invariants unblock blocking operators by defining when such an operator can pass
results on. Keep invariants define what must be kept in local state to continue successful
operation. Propagation invariants define when an operator can pass punctuation on. We
then present a strategy for proving that implementations of these invariants are faithful
to their finite table counterparts.
Some definitions could be streamlined, and typos corrected, but otherwise looks interesting.
I also suspect reformulating the definitions in terms of domain theory might have benefited both reader and writer (less implementation-specific details).
On the other hand, category theory might be an overkill for this...
Also, can this be seen as a good application for concurrent constraint programming?
On the first glance punctuations look just like constraints.
Wednesday, January 24, 2007
Comonadic functional attribute evaluation
They relate zippers to comonads. Wow!
No wonder processes looked like zippers to me - they are about contextually situated values (err, actually computations :( ).
CoKleisli categories make comonads relevant for analyzing notions of context-dependent
function. If the object D A is viewed as the type of contextually situated
values of A, a context-dependent function from A to B is a map D A -> B in the base
category, i.e., a map from A to B in the coKleisli category. The counit eA : D A -> A
discards the context of its input whereas the coextension k† : D A -> D B of a function k : D A -> B essentially duplicates it (to feed it to k and still have a copy left).
No wonder processes looked like zippers to me - they are about contextually situated values (err, actually computations :( ).
Monads, Kleisli Arrows, Comonads and other Rambling Thoughts
Simple, and to the point.
Now I wonder how to generalize this result to stream processors that do not preserve rate (i.e., produce a list to an output stream for each history of the input stream). Generalization to multiple inputs is next.
Now I wonder how to generalize this result to stream processors that do not preserve rate (i.e., produce a list to an output stream for each history of the input stream). Generalization to multiple inputs is next.
Tuesday, January 23, 2007
What kind of logic is “Independence Friendly” logic?
In a series of singular, thought-provoking publications in recent years, Jaakko
Hintikka has vigorously promoted consideration of an extension of first-order logic called
IF logic, along with claims that its adoption promises to have revolutionary
consequences. My main purpose here is to examine in what sense it deserves to be called
a logic.
Uh-oh.
Subscribe to:
Posts (Atom)
