Timeline for Extension of SQL capturing $\mathsf{P}$
Current License: CC BY-SA 3.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2013 at 15:07 | answer | added | András Salamon | timeline score: 3 | |
| Mar 12, 2012 at 21:56 | history | edited | Kaveh | CC BY-SA 3.0 |
added some motivation part
|
| Mar 12, 2012 at 20:55 | history | reopened |
Stéphane Gimenez sepp2k Raphael Dave Clarke Gilles 'SO- stop being evil' |
||
| Mar 12, 2012 at 20:55 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
clarification following the comment thread
|
| Mar 12, 2012 at 18:09 | comment | added | Shog9 | That's fine. There is still some time left in the private beta. | |
| Mar 12, 2012 at 18:07 | comment | added | Kaveh | @Shog9, I am little bit busy today, will update it tomorrow. | |
| Mar 12, 2012 at 17:38 | history | edited | Raphael | CC BY-SA 3.0 |
adding a clarifying remark regarding the meaning of "captures"
|
| Mar 12, 2012 at 17:07 | comment | added | Shog9 | @AlextenBrink: I've responded there. Kaveh: rather than leaving the outcome of discussion in comments (on the question or answer), update your question to address them. This makes it more accessible to future readers. | |
| Mar 12, 2012 at 16:59 | comment | added | Alex ten Brink | As I noticed another question got closed as well (which also had close votes), I asked a question on meta about it: meta.cs.stackexchange.com/questions/97/… | |
| Mar 12, 2012 at 16:48 | comment | added | Alex ten Brink | @Shog9: I fail to see why this question needed moderator intervention and was closed. I'm comfortable enough with Descriptive Complexity to say that this is a real question (although possibly better suited for TCS - it's a bit of a hard question). | |
| Mar 12, 2012 at 15:54 | comment | added | Kaveh | @Shog9, Which part are you referring by "obviously not"? If someone is not familiar with descriptive complexity or even computability theory (e.g. J.D.) then their comments doesn't contradict what I said. | |
| Mar 12, 2012 at 15:52 | comment | added | Kaveh | ps: even without the motivation part the question is clear enough to get answered. Either state a language with these properties or if there is not one explain why such a language is not interesting from the point of practice. | |
| Mar 12, 2012 at 15:52 | comment | added | Shog9 | Obviously not, as you have several comments and an answer indicating otherwise. Please take what you've written here and update the question to clarify your intent. | |
| Mar 12, 2012 at 15:46 | comment | added | Kaveh | @Shog9, the motivation is coming from Descriptive Complexity. I am trying to see if there is a language extending SQL used in the industry that captures P. The original SQL language is rather weak as Immermann's result show, from theoretical point of view many efficient computations are impossible to state in it. On the other hand we would like to keep the language efficient (i.e. $\mathsf{P}$). Is there such a language? (I think these are probably clear for people familiar with descriptive complexity). | |
| Mar 12, 2012 at 15:35 | comment | added | Shog9 | Please read the rest of my first comment, @Kaveh. | |
| Mar 12, 2012 at 15:28 | comment | added | Kaveh | @Shog9, I have already replied to that. J.D. does not understand the question, he didn't even know what capture means and is not aware that a language capturing P cannot be Turing complete by definition. He expects it to be stated in the way he likes it, I have stated it in the usual descriptive complexity terminology and complexity of query languages, and have even explained these to him. What is not clear here? | |
| Mar 12, 2012 at 15:23 | comment | added | Shog9 | @Kaveh: it is very unclear what you are trying to accomplish with this question right now (see comments from J.D.). Please elaborate on what you are doing, and what your goal is here, so that others may provide concrete, specific answers rather than open-ended discussion. | |
| Mar 12, 2012 at 15:21 | comment | added | Kaveh | @Rebecca, why did you close the question? | |
| Mar 12, 2012 at 15:20 | history | closed |
user20 Rebecca Chernoff |
not a real question | |
| Mar 12, 2012 at 0:11 | comment | added | Kaveh | @J.D., sorry, but based on your comment I think you don't understand the question. The question is well-defined. Capturing a complexity class by a language is a standard terminology. (what is not well-defined is my preference that the language should be a query language, but that is only a preference and I have told you I would be fine with one which is not if there isn't one with that preference.) | |
| Mar 11, 2012 at 19:56 | comment | added | Kaveh | As I have already said, I would prefer a language which is not procedural, but if there isn't one I would be interested even in that (do you know one?). (I want the language to extend SQL and remain a query language, it is not a well-defined concept but the least requirement is that the instruction are processed by the database server and not on the client side.) The language should be in use by industry (i.e. I don't want made up answers, it is easy to define such languages). | |
| Mar 11, 2012 at 19:49 | comment | added | Kaveh | @J.D., obviously if it captures $\mathsf{P}$ it cannot be Turing-complete. | |
| Mar 9, 2012 at 0:12 | answer | added | Victor Stafusa | timeline score: -1 | |
| Mar 8, 2012 at 19:14 | answer | added | Janoma | timeline score: 5 | |
| Mar 8, 2012 at 17:11 | comment | added | Kaveh | @J.D., I am looking for something that captures $\mathsf{P}$, i.e. doesn't contain anything outside $\mathsf{P}$ (and preferably something that is similar to SQL, e.g. no procedural programming). | |
| Mar 8, 2012 at 16:31 | history | edited | Kaveh | CC BY-SA 3.0 |
added 208 characters in body
|
| Mar 8, 2012 at 16:08 | history | asked | Kaveh | CC BY-SA 3.0 |