in [OOP]

From: frebe73 on 28 Jan 2007 15:12 > >>> Why don't you show the limitations with relations as data structures? > >> Come on! It was shown on numerous occasions. I can repeat just one example: > > >> Nearest neighbour search > >> ----------------------------------- > > >> Given: S, a metric space of dimension k>1; V={vi} a finite set of vectors > >> from S. > > >> Objective: represent V in a way that it were possible to design the > >> function f:S->V, such that forall i |x-f(x)|<=|x-vi|. > > >> Requirement: complexity of f must be better than O(n). > > > What data do you want me to model as relations? A point in space, a > > vector?(they are same) > > > Points in space may easily be modelled by a relation with k > > attributes. > > point(x, y, z)Yes, this is what I want. Now show me f. You can take Euclidean distance > d(r,t) = sqrt ((rx-tx)^2 + (ry-ty)^2 + (rz-tz)^2) > > Consider the following data set: > > x y z > ------------- > 1 2 10 > 10 3 20 > 3 3 5 > 0 0 0 > 9 2 99 > > For this set, f(0,0,90) shall yield (9,2,99). > > Remember the requirement - the complexity of f must be better than O(n), > where n is the cardinality of the data set. In the example provided, n=5. I assume that you agree it is possible to write statement in SQL solving the problem. As I understand it, the problem would be for the query engine to execute the query better than O(n), if B-trees are used. In your given example a k-d tree is the index type that should be used if the query should execute betten than O(n). Some databases allow you to use domain specific index types. Have a look at http:// download-west.oracle.com/docs/cd/B10501_01/appdev.920/a96595/ dci07idx.htm. You also have to realize that relational algebra is not an imperative language. It tells you WHAT data you want. HOW the algebra is executed is up to the database implementation, and the implementation might very well be specialized for different domains. Fredrik Bertilsson http://mybase.sf.net
From: Dmitry A. Kazakov on 28 Jan 2007 16:50 On 28 Jan 2007 12:12:29 -0800, frebe73 (a)gmail.com wrote:>>>>> Why don't you show the limitations with relations as data structures? >>>> Come on! It was shown on numerous occasions. I can repeat just one example: >> >>>> Nearest neighbour search >>>> ----------------------------------- >> >>>> Given: S, a metric space of dimension k>1; V={vi} a finite set of vectors >>>> from S. >> >>>> Objective: represent V in a way that it were possible to design the >>>> function f:S->V, such that forall i |x-f(x)|<=|x-vi|. >> >>>> Requirement: complexity of f must be better than O(n). >> >>> What data do you want me to model as relations? A point in space, a >>> vector?(they are same) >> >>> Points in space may easily be modelled by a relation with k >>> attributes. >>> point(x, y, z)Yes, this is what I want. Now show me f. You can take Euclidean distance >> d(r,t) = sqrt ((rx-tx)^2 + (ry-ty)^2 + (rz-tz)^2) >> >> Consider the following data set: >> >> x y z >> ------------- >> 1 2 10 >> 10 3 20 >> 3 3 5 >> 0 0 0 >> 9 2 99 >> >> For this set, f(0,0,90) shall yield (9,2,99). >> >> Remember the requirement - the complexity of f must be better than O(n), >> where n is the cardinality of the data set. In the example provided, n=5. > > I assume that you agree it is possible to write statement in SQL > solving the problem. I don't know. Show us. But no stored procedures please. > As I understand it, the problem would be for the > query engine to execute the query better than O(n), if B-trees are > used. In your given example a k-d tree is the index type that should > be used if the query should execute betten than O(n). Why didn't you propose kd-tree as the data structure? You are talking about some magical "index type" which should save you. May I have a relational description of? > Some databases > allow you to use domain specific index types. Have a look at http:// > download-west.oracle.com/docs/cd/B10501_01/appdev.920/a96595/ > dci07idx.htm. Great, wouldn't it be simpler to say that some databases aren't relational? Let me ask for clarity: 1. is "index" a data structure? 2. is it a relational structure? 3. how SQL describes the "index" required to the problem at hand? > You also have to realize that relational algebra is not an imperative > language. It tells you WHAT data you want. HOW the algebra is executed > is up to the database implementation, and the implementation might > very well be specialized for different domains. Where in my challenge I required you to make it imperatively? Do it as you wish. The only requirement is - be better than O(n). All this chatting about declarative vs. imperative is hand-waving. If you are using some declarative framework, you are free to do it. But, you have to put open all its costs. That is - parsing and inference. Complexities of both summed have to be under O(n). If they are you are through. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Dmitry A. Kazakov on 28 Jan 2007 16:50 On 28 Jan 2007 12:12:17 -0800, topmind wrote: > Dmitry A. Kazakov wrote: >> On 28 Jan 2007 06:04:24 -0800, frebe73 (a)gmail.com wrote:>> >>> Why don't you show the limitations with relations as data structures? >> >> Come on! It was shown on numerous occasions. I can repeat just one example: >> >> Nearest neighbour search >> ----------------------------------- >> >> Given: S, a metric space of dimension k>1; V={vi} a finite set of vectors >> from S. >> >> Objective: represent V in a way that it were possible to design the >> function f:S->V, such that forall i |x-f(x)|<=|x-vi|. >> >> Requirement: complexity of f must be better than O(n). > > I debunked this already, at least from a theoretical point of view. > In short, relational does NOT prevent domain-specific operations from > being defined. Neither warp knitting does. Surely that makes it the best data structure all over the world... -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: topmind on 28 Jan 2007 17:21 Dmitry A. Kazakov wrote: > You are talking about some magical "index type" which should save you. May > I have a relational description of? Indexes are not usually described on the relational level. Indexes are an implementation aid. In theory, a query should return the *same answer* even if you remove all the indexes. (It just may take a long time to run). > > > Some databases > > allow you to use domain specific index types. Have a look at http:// > > download-west.oracle.com/docs/cd/B10501_01/appdev.920/a96595/ > > dci07idx.htm. > > Great, wouldn't it be simpler to say that some databases aren't relational? > Let me ask for clarity: > > 1. is "index" a data structure? Yes. > 2. is it a relational structure? Index is an implementation. Relational describes an interface, not an implementation. > Dmitry A. Kazakov Note that wether indexes are best described as relational structures, I don't know and don't care. I am not one to claim relational is good for every use under the sun. I just know they usually work pretty well for my domain. -T-
From: Daniel Parker on 28 Jan 2007 19:04
On Jan 28, 4:45 am, "Dmitry A. Kazakov" <mail... (a)dmitry-kazakov.de> wrote: > On 27 Jan 2007 19:20:41 -0800, Daniel Parker wrote: > > > On Jan 27, 4:20 pm, "Dmitry A. Kazakov" <mail... (a)dmitry-kazakov.de>> > wrote: > > >> ... relations can be values (and thus objects). > > > A relation is a value. But are you saying that an object _is_ a value? > Of course I don't. I meant that if something could be a value, then we > could make objects on that basis. Make objects on what basis? A relation is a value, a relation is a set of tuples, every value is a value of some type, the type of a relation is parametrized on the type of its member tuples. And??? > > > If a mutable object > > is mutated, is it the same value?In the first approximation it is not, but it depends on the type of. See > below. > > > Rather, it seems to make more sense > > to say that an object _has_ a value, and that if it is mutated, it has > > a different value.Yes. > > But, there can be different views of what is the value. We cannot talk > about values indiscriminately (without types). When object is as usual > identity + state and its state is the value, that is one view. > > But there could be other views. You can consider object with all its > possible states and behavior as a single value (of a different type). As > examples we could take pointers passed around, random generators, clocks, > files. > > Everything depends on types and identities. Of course, every value is a value of some type. > > RA is about specialized containers and thus deserves no any special > treatment. > RA is about a formal logical system about relations, and a small number of operations that map relations into relations. What is the special treatment? Logic? The concept of algebraic systems that are closed over a set of operations? Something else? Daniel |