From: frebe73 on 29 Jan 2007 02:46 > > 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? The relational model makes a distinction between logical an physical data structures. Relations are a logical data structure. B-trees or kd- trees are physical data structures. The logical and physical data structures are independent of each other. A database which provides relations, may still use any kind of physical structures. > You are talking about some magical "index type" which should save you. May > I have a relational description of? See above. > > 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? The logical data structure are relational. > Let me ask for clarity: > > 1. is "index" a data structure? A physical data structure. > 2. is it a relational structure? A logical data structure. > 3. how SQL describes the "index" required to the problem at hand? Some SQL dialects allow you to give hints to the query optimizer, but normally it is up to the optimizer to choose which indexes to use. Fredrik Bertilsson http://mybase.sf.net
From: Dmitry A. Kazakov on 29 Jan 2007 06:27 On 28 Jan 2007 16:04:30 -0800, Daniel Parker wrote: > 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??? Then the tuple (T, r) is a relation object. Here T is the type of the relation r and r is the value of, i.e. the relation itself. >> RA is about specialized containers and thus deserves no any special >> treatment. >> > > RA is about a formal logical system about relations, OK, if you take a mathematical definition of algebra. But in the context of this thread, RA refers to its application for software developing and design. > and a small > number of operations that map relations into relations. What is the > special treatment? It is an attempt to encapsulate it into a physically separate component interfaced though its own language. That thing is called RDBMS, which is responsible for implementation of RA. Because this design is obviously flawed, proponents of RDBMS try to argue that RA is capable to describe everything in the best possible way. That's rubbish. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Dmitry A. Kazakov on 29 Jan 2007 06:40 On 28 Jan 2007 23:46:53 -0800, frebe73(a)gmail.com wrote: >>> 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? > > The relational model makes a distinction between logical an physical > data structures. Relations are a logical data structure. B-trees or kd- > trees are physical data structures. The logical and physical data > structures are independent of each other. A database which provides > relations, may still use any kind of physical structures. I see. A poster with a car is logical structure of that car. The car in the garage is the physical structure of. Are are selling me posters? >>> 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? > > The logical data structure are relational. Yes, the car on that poster looks great. >> Let me ask for clarity: >> >> 1. is "index" a data structure? > > A physical data structure. > >> 2. is it a relational structure? > > A logical data structure. > >> 3. how SQL describes the "index" required to the problem at hand? > > Some SQL dialects allow you to give hints to the query optimizer, but > normally it is up to the optimizer to choose which indexes to use. I see, you are selling posters, cars are built by other guys... -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Patrick May on 29 Jan 2007 07:17 frebe73(a)gmail.com writes: >> Why don't you defend your claim that relations are the only data >> structure that should ever be used? > > The most common data structures used in current programming > languages are lists and maps, so I think we can limit ourself to > these structures. I think we can use that statement as evidence that you don't know what you're talking about. Lists and maps may be the most commonly used, but they by no means define the full set of data structures used in production software. > But I can recommend you to google for "relational algrebra" and you > might get better understanding. I've been in the industry for close to twenty years and started out working on a CASE tool that supported all the common relational modeling techniques at the time. Nice try with the condescension, though. It's easier than actually defending your ridiculously broad claims, isn't it? > Because lists and map are more low-level they do also have > performance benefits. In some scenarios (but not often in business > applications), performance might force you to use them. Because most > of the current mechanisms providing some sort of relational algrebra > are running in a separate process from the rest of the application, > there might be perfomance problems when making heavy use of > relational algebra. The best solution for this problem is to use > stored procedures to avoid the inter-process communication. Using > low-level data structures on the application side is a bad idea for > solving this problem. More pronouncements from on high. You admit that there are performance benefits to non-relational data structures, but assert without basis that they should nonetheless never be used. (Hint: inter-process communication is not the only source of performance problems.) >> Your claim is equivalent to asserting that all of the experienced >> software developers using other data structures to deliver real >> business value every day are ignorant or foolish. > > It was possible to make working applications in the pre-relational > era too. We're doing it in the post-relational era, too. >> Do you really think that only you have seen the light? > > No, have a look at comp.databases.theory or look at the LAMP- > architecture. I'm beginning to think I'm being trolled. No one can really be this cluelessly arrogant. >> Isn't it just possible that other data structures exist for very >> good reasons? > > They are needed to implement relational databases, and they are > needed in other low-level software. So you are contradicting your original claim that relations are the only data structure that should ever be used. If relations aren't good enough for implementing an RDBMS, there is no reason to think that they are sufficient for all application needs. >> The only people here who limit themselves to a single approach are >> the relational one trick ponies. The rest of us want as many tools >> in our toolbox as possible. > > OO people claim that OO can be used for everything. "Can" is not the same as "should." You relational one trick ponies should learn that. Sincerely, Patrick ------------------------------------------------------------------------ S P Engineering, Inc. | Large scale, mission-critical, distributed OO | systems design and implementation. pjm(a)spe.com | (C++, Java, Common Lisp, Jini, middleware, SOA)
From: frebe73 on 29 Jan 2007 07:31
> > The relational model makes a distinction between logical an physical > > data structures. Relations are a logical data structure. B-trees or kd- > > trees are physical data structures. The logical and physical data > > structures are independent of each other. A database which provides > > relations, may still use any kind of physical structures. > I see. A poster with a car is logical structure of that car. The car in the > garage is the physical structure of. Are are selling me posters? Please read http://www.inconcept.com/JCM/May2002/pascal.html and you have a deeper explaination about the difference between logical and physical levels. At http://www.acm.org/classics/nov95/s1p2p2.html, you can read what Dr Codd have to say about separating the choice of index from the application (separation of concerns). > >> 3. how SQL describes the "index" required to the problem at hand? > > > Some SQL dialects allow you to give hints to the query optimizer, but > > normally it is up to the optimizer to choose which indexes to use. > > I see, you are selling posters, cars are built by other guys... I have seen too many times OO guys trying to reinvent databases. The problem is that they always do it worse than existing products. Fredrik Bertilsson http://mybase.sf.net |