Re: no names allowed, we serve types only
Date: Wed, 17 Feb 2010 16:21:20 -0800 (PST)
Message-ID: <4dbb8cf6-dcea-4453-b5f4-bfa019df7d6f_at_e19g2000prn.googlegroups.com>
On Feb 17, 3:46 pm, Tegiri Nenashi <tegirinena..._at_gmail.com> wrote:
> On Feb 17, 2:01 pm, Jan Hidders <hidd..._at_gmail.com> wrote:
>
>
>
>
>
>
>
> > On 17 feb, 21:00, Tegiri Nenashi <tegirinena..._at_gmail.com> wrote:
>
> > > On Feb 17, 11:36 am, Nilone <rea..._at_gmail.com> wrote:
>
> > > > On Feb 17, 8:51 pm, Tegiri Nenashi <tegirinena..._at_gmail.com> wrote:
>
> > > > > On Feb 17, 10:14 am, David BL <davi..._at_iinet.net.au> wrote:
>
> > > > > > On Feb 17, 9:15 pm, Nilone <rea..._at_gmail.com> wrote:
>
> > > > > > > On Feb 17, 1:29 pm, David BL <davi..._at_iinet.net.au> wrote:
>
> > > > > > > > Operators can be formalised without a type system too. Simply
> > > > > > > > formalise an operator as a function defined on some domain, where a
> > > > > > > > domain is merely a set (not a "type").
>
> > > > > > > Thanks for the introduction, I haven't seen the typeless model
> > > > > > > before. I don't see how such a system would handle arithmetic
> > > > > > > operators (e.g. + and <) and string operators like concatenation and
> > > > > > > search - could you perhaps give an example?
>
> > > > > > In a typeless system a unary function could for example be formalised
> > > > > > as a triple (D,C,G) where D is the domain, C is the co-domain and G is
> > > > > > the graph of the function (a subset of DxC). This is typeless in the
> > > > > > sense that a function value doesn't formally have any concept of a
> > > > > > defined type. Rather the domain and co-domain are formally part of
> > > > > > the function's value as a triple (D,C,G). For example two functions
> > > > > > can have the same domain and graph but different co-domains. That
> > > > > > makes them distinct. This is actually conventional, as when one
> > > > > > determines whether a given function is surjective (i.e. its range
> > > > > > equals its co-domain). It wouldn't make sense to ask whether a
> > > > > > function is surjective if its co-domain isn't part of its value.
>
> > > > > > Alternatively a typeless system could instead formalise a unary
> > > > > > function as a set of pairs (i.e. what we above called its graph). In
> > > > > > that case the domain and range is determined from the graph using
> > > > > > projection, but there is no concept of a co-domain.
>
> > > > > > Similarly a typeless system could formalise a relation in two
> > > > > > different ways. One allows for attributes to have domains specified
> > > > > > independently of the graph (or "body") of the relation, and these
> > > > > > domains represent part of the relation's value. That means that two
> > > > > > distinct relations can have exactly the same graph.
>
> > > > > > Alternatively a relation can be identified with its graph. In that
> > > > > > case the domains are determined as the projection of each attribute.
>
> > > > > > In a typeless formalism one is very clear about what it means for two
> > > > > > functions or two relations to be equal. It seems to require more
> > > > > > effort to understand what equality means in a typed formalism.
>
> > > > > > In a D&D type system, a value has a MST, but this actually depends on
> > > > > > the prevailing type system. E.g. two different databases could use
> > > > > > different type systems. Putting it another way, the MST of a value
> > > > > > depends on who you ask :-).
>
> > > > > > D&D want to ensure that equality of values is independent of declared
> > > > > > types. That's why they say that a selector for an ellipse value that
> > > > > > happens to specify equal width and height actually returns a value
> > > > > > which has an MST of circle. It's like a "magic downcast". They point
> > > > > > out that OO systems don't normally work that way. E.g. an OO
> > > > > > constructor for ellipse never returns a circle.
>
> > > > > > I think D&D end up treating relations with the same body and attribute
> > > > > > names as equal. i.e. in essence the declared attribute domains are
> > > > > > not part of the relation's value. I think they define subtyping of
> > > > > > relation types accordingly.
>
> > > > > > It seems to me that D&D spend a lot of effort discussing ideas that
> > > > > > are either eliminated or trivialised in a typeless formalism of the
> > > > > > RM.
>
> > > > > Formalization is less of an issue here. I interpret the question as
> > > > > how to make a working system operating predicates such as Plus(x,y,z)
> > > > > and Concat(x,y,z). Logical programming provides sort of an answer.
>
> > > > You're right. I'm a programmer rather than a mathematician. As such,
> > > > infinite sets can only be approximated and every value has a cost in
> > > > space and time. So I'm interested in how operators would be
> > > > effectively (and hopefully, efficiently) defined in a software version
> > > > of such a model.
>
> > > > The operators in a typed system are based on inspecting and
> > > > manipulation the representation of values. I don't see how anything
> > > > similar is possible in an untyped relational model. There's
> > > > exhaustively generating all operands and results, which is
> > > > impractical. With a successor operator defined (again,
> > > > exhaustively?), we can define plus inductively, which would be highly
> > > > inefficient. Is there a way to define these operators without
> > > > resorting to hidden types or an actor-like model of delegating the
> > > > work to the operand?
>
> > > I'm not sure what hidden types or actor-like model of delegating the
> > > work to the operand, and why it is undesirable. Predicates such as
> > > "Plus" do have a set of functional dependencies, so why not to allow
> > > these dependencies be implemented in procedural language? These could
> > > be considered implementation details, pretty much as indexes belonging
> > > to physical layer of relational model. This idea is explored in
>
> > >http://vadimtropashko.wordpress.com/relational-programming-with-qbql/...
>
> > You seem to be linking being untyped and representing functions/
> > operations with predicates. Can I ask why? Would you not agree that
> > one can have one without the other and vice versa?
>
> No rationale (other than sharing intuition with more elaborate David
> BL explanation). What are types? Is there a foundation that doesn't
> involve heavy machinery of category theory?
>
> The thread started as Keith's attempt to demote attribute names in
> favor of types, and was vehemently objected to. From my angle (that
> would be relational lattice:-) Relational Model is a theory of
> Relations with Named Attributes. It is difficult to see unnamed
> perspective (with positional attributes) as contender anymore. This is
> especially evident through the prism of set intersection join (aka
> composition) operation...
Let me clarify these ideas. In unnamed perspective attributes are numbers indicating _relative_ position of each attribute in each individual relation. One have to devise some drudgery conventions to be able to compare, say, attribute #5 in the relation Emp with attribute #2 in the relation Dept. In unnamed perspective Cartesian Product takes the prime stage with all those mathematical snags around it (non commutativity, non associativity).
With named attributes we operate relation attributes as ordinary sets. Unfortunately, classic Relational Algebra doesn't make this point obvious. Natural join unions the attributes, but about the other Relational Algebra operations? Compare it to relational lattice, where
- generalized union (denoted "v") intersects attribute sets
- ditto inner join (denoted "*")
- outer union ("+", aka D&D <OR>) unions attributes
- unary inversion operation ("`") builds a relation with
"complementary" set of attributes.
These are not some exotic operations, one can suggest a list of very practical queries involving them:
http://vadimtropashko.wordpress.com/relational-programming-with-qbql/qbql-for-sql-people/
What about other set operations? For example, symmetric difference is an operation with some notable algebraic properties; do we have an binary operation operation over relations that takes a symmetric difference of attributes? Yes, in fact there are several of them http://vadimtropashko.wordpress.com/relational-programming-with-qbql/aggregation-and-set-joins/ the most distinguished among these being set intersection join (aka composition). I wonder if the whole theory shouldn't be recast in semiring form of natural join and composition... Received on Thu Feb 18 2010 - 01:21:20 CET