Re: A Topological Relational Algebra in Lisp
Date: Sat, 17 Jan 2015 13:20:06 +0100
Message-ID: <m9dk0p$330$1_at_dont-email.me>
compdb_at_hotmail.com wrote:
> On Sunday, January 11, 2015 at 5:25:31 AM UTC-8, Norbert_Paul wrote:
>
>> I am interested in a discussion here, because it seemed that reviewers
>> tended to frown on my (any my co-workers) work because, for example:
>
> What database-oriented field(s) do you consider this work to be contributing
> to? (Eg the reviewers' and audiences'.)
Thank you for your remarks.
My specific interest are CAD databases and, maybe, geo-information. Hovever, I suppose, however, topological data has a wider field of application.
> Just because you are using relational operators and persisting doesn't mean
> you are involving "relational databases". Moreover just because you are using
> a relation(al) algebra doesn't mean you are being "relational" in the
> database sense.
Actually, your statement is a bit ambiguous. Doy you mean that my approach is "non-relational" in some sense or do you say that its being "relational" is still an open issue?
> Besides that, you are mostly using relation operators among others to
> implement non-relation operators on non-relation structures that are merely
> represented by relations among other structures.
How can structures that are represented by relations be "non-relational"? Could you please identify the non-relation operators you are talking about?
> Moreover some of your
> relations are specifically limited to binary relations and some are
> specifically representing matrices.
The concept is the following:
Relational Model: Take relations (database tables) R1, R2, ... and operate
on them using a relational operator op to produce a
result relation
R = op(R1,R2,...).
My extension: Attach a topology T1, T2, ... to each relation to get
topological spaces (R1,T1), (R2,T2), ....
Take the same operator op to produce the same result
relation R = op(R1,R2,...).
Then there exists a unique result topology T, such that
(R,T) is the result /space/ of op.
The result topology can be computed by a relational query
on all relations involved. If there is no dimension upper
bound on the topolgoies the query languange /must/ support
recursive join on binary relations to produce the correct
result topology.
The topologies, can always be represented by a binary relation (They are "Alexandroff topologies"). This is, where binary relations enter the scene, but the original relational model is still present. Note that no apprach to store a topology can have a better worst-case storage space-complexity than O(n^2) when arbitrary topologies of dimension more than 0 are to be stored for a given point-set of sitze n. So binary relations are asymptotically optimal with respect to storage space. (This is even true for one-dimensional spaces only).
> So really at best you could say you have
> a partly relation(al) algebra implementation of a topological space algebra,
> some of the parts and operators of which are actually relation-based in the
> relation(al) algebra sense.
I have topologized /all/ relational operators that are necessary to get a relationally complete query language. So I have a relationally complete query language for topological spaces.
> But almost none of this involves relations in the "relational database"
> sense. You're just using relations as an appropriate abstract and
> implementation sturcture; you're not using them "relationally". Because the
> significance of the "relational" in "relational database" is that there is a
> certain correspondence between relation(al) algebra operators and logic
> non-terminals, in such a way that there is a certain correspondence between
> equivalent relation expressions and predicate expressions, in such a way that
> not only can one query (in the sense of logical deduction, not the trivial
> sense of evaluating a relation expression) using either notation but the
> result can be automatically evaluated with certain complexity and
> optimization opportunities.
I am aware of complexity issues and still want to focus on effectiveness and not so much on efficiency.
Could you please provide the definition of "relational" your judgement is based on? THis would be helpful in the discussion.
> Here is part of what I wrote a while ago here when someone asked about a
> similar situation where a paper discussed analogues of relational database
> theory and probablitiy distributions, after I read its abstract. You can just
> read "topological space" for "probability distribution".
>
> On Wednesday, April 11, 2012 at 3:02:41 PM UTC-7, com..._at_hotmail.com wrote:
>>
>> A (named attribute) relation can be seen as a set of or mapping on
>> multi(-named-)dimensional points. Functional dependencies are properties of
>> relation values and expressions.
>>
>> Database relational operators are designed so that there is a
>> correspondence between relation expressions and predicates (and predicate
>> expressions aka wffs). The value of a relation expression is the extension
>> of a corresponding predicate (and wff) where the relation value's
>> attributes are the predicate's parameters (and the wff's free variables). A
>> relation expression has an associated predicate (and wff) built from it in
>> a certain way according to its operators and its variables' given
>> predicates (and wffs). The fundamental theorem of the relational model is
>> that IF the body of each relation variable's value is the set of tuples
>> that make a given predicate (or wff) true THEN the body of each relation
>> expression's value is the set of tuples that make that expression's
>> predicate (or wff) true. Eg if the predicate of relation R is R(X,Y)
>> "person X loves person Y" and the predicate of relation variable S is
>> S(Y,Z) "person Y loves food Z" then the expression for (R JOIN S)
>> PROJECT_AWAY Z is EXISTS Z [S(X,Y) AND R(Y,Z)] "there exists a Z such that
>> person X loves person Y and person Y loves food Z" ie "person X loves
>> person Y who loves some food".
>>
>> Probability operators for treating relations as probability distributions
>> will do different things (in general) than database operators. They will
>> satisfy different theorems.
>>
>> A relation with a functional dependency can represent a function.
>> Composition and images are relevant in databases when a relation expression
>> corresponds to a function's (or wff term's) value. To the extent that
>> distributions are used as (relational or functional) mappings such
>> representation-independent mapping-oriented operators will appear in that
>> system.
>>
>> So what we can expect is that what the two systems have in common is...
>> they both somehow involve a relation as a set of or mapping on
>> multi(-named-)dimensional points. Correspondences between operators other
>> than ones that are oriented to mappings would be coincidental. I don't call
>> that much of an analogy/parallel.
>
>
> It turned out like I predicted. (Although the paper's relation-based
> representation of probability distributions was simpler than I expected.)
Actually the sitaution is different: I do not have an "analogy". I realized that topological constructions (product space, subspace, glueing, wedge sum, ,...) constitute a relationally complete "query languge" for topological spaces and that each database relation can be turned into such a topological space by attaching a binary relation to it. So this is an extension.
> So from reading your page http://pavel.gik.kit.edu/doc/howto.html
> (particularly sections Topological Data Model and Example Session) my not
> very topologically informed impression is that your work uses relation
> operators but isn't "relational" in the database sense. (Even when you select
> from relations, it's by wffs and oblivious to the relation(al) algebra making
> that both possible and unnecessary.) Of course, I could be missing
> "relational" analogues. I hope you will try to justify any you have found or
> will find in light of this message.
I can only justify, if you give me an accepted definition of "relational".
This is, accoring to Codd RMV2:
(http://books.google.de/books/about/The_Relational_Model_for_Database_Manage.html?id=ZZckAQAAIAAJ)
1,2 The Relational Model
1.2.1 Relation is the only comound data type:
Every relation X of a relational database is a candidates as point set of a
topological space (X,T).
Every topology T is represented by a binary relation R on X.
So there only exist relations.
1.2.2 Inter-relating the Information Contained in Distinct Relations: "All inter-relating is achieved by means of comparison of values" (Codd).
So everything of the above is satisfied, and I guess Codd's definition of "relational" is authoritative.
You may want to compare what I did to Codd's Chapter
28.1 Requested Exensions
(3) computer-aided engineering design.
My spatial variants of queries are (formally) composed of relational
query operators.
Hence I followed Codd's general rule for making extensions:
"I strongly recommend that the problem be examined first at the level of
abstraction of the relational model. This means treating the relational
model, together with any necessary and relevant extensions, as a tool
for solving the problem."
> Perhaps I can distill it down to your system's notion of "query" merely being
> an expression of mostly non-relation operators calculating mostly
> non-relation results that are also somewhat implemented by relation
> operators, rather than an enquiry, even most of the time they involve
> relations.
I merely replaced each database query that takes a number of relations to produce a result by a modified query that takes pairs of relations and produces result pairs of relations. So i still don't get why this is "non-relational".
Thank you for your remarks
Norbert Received on Sat Jan 17 2015 - 13:20:06 CET