Talk:Global serializability

From Wikipedia, the free encyclopedia

[edit] Are the experts experts?

Strangely, since its introduction publicly in formal publications, Commitment ordering has been misunderstood (including in papers mentioning strong recoverability), misrepresented, and totally ignored in many papers on database global concurrency control. The single existing description of CO in a textbook, by Weikum and Vossen, 2001, is indeed poor (as somebody already mentioned in the article Serializability’s discussion part) and a misunderstanding of the CO solution. A three years review process by IPL of a CO paper (see dates in the reference), a journal that typically accepts and publishes papers in few weeks, means a problematic review process with reviewers’ opposition very likely, but with acceptance at the end (persistent editor!). Acceptance to top journal and conferences means that at least some experts understood CO. CO is the most spectacular result in concurrency control theory since 2PL and multi-version CC, to my opinion, and apparently the only existing effective general solution to the global serializability problem. All the above is not a compliment to the researchers involved, whatever the reasons are.

Some more information connected to CO that I have found:

Closely related to CO is Dynamic atomicity that has been introduced at the MIT in the mid eighties by William E. Weihl (using a unique OO formalism), but without a general algorithm beyond mentioning known algorithms with locking. Under a specific transaction model translation it can be interpreted as CO (no commit order is mentioned there explicitly). In 1993 it was reformulated as CO (using commit) without reference to the CO papers. Atomic commitment and voting, which eliminate global cycles in the precedence graph, and are the basis for CO’s distribution, are not mentioned there.

In 1990 Analogous execution and serialization order, which unnecessarily has serializability as a premise (it implies serializability also without the premise), but otherwise similar to CO, was introduced in technical reports by Marek Rusinkievicz et al without a general algorithm. Its definition was enhanced in 1991 with a new name: Strong recoverability (wrong name), which is identical to CO. A paper about SS2PL (Rigorousness), already accepted for publication (“To appear in TSE, September 1991” is displayed at the top) that mentions analogous execution but does not mention strong recoverability, has been circulated in 1991. The definition of strong recoverability appears only in the September 1991 published version of the paper, and is used to assist a global serializability proof of a SS2PL based federated database. No related general algorithm is mentioned. A 1992 paper on strong recoverability cites a CO paper, but again, does not give any general properly defined CO algorithm. Atomic commitment and voting are not mentioned there, and neither I saw them mentioned in later papers that mention strong recoverability, sometimes together with CO. All papers that mention both state that they are "the same," which is true for the definitions, but not for the solutions: Only the CO papers describe valid CO algorithms and related effective system solutions.

In the mid nineties Transactional processes have been introduced, citing a CO paper. In later papers on transactional processes CO is not referenced, and distributed CO based algorithms are given (CO is assumed without mentioning the name CO). These algorithms are unlikely to be correct since they do not use the cycle elimination voting mechanism in atomic commitment, or any such alternative mechanism. 71.250.4.220 (talk) 17:04, 18 May 2008 (UTC)

  • I find this article essentially incomprehensible and unfortunately, your statement does little to clarify it. I would welcome some effort to make this entire discussion and the related pages about commitment ordering more accessible to a wider audience. If it's so spectacular, surely a more convincing case can be made. - JCLately (talk) 18:31, 18 May 2008 (UTC)
  • Some of the facts brought above, with proper references, can be a basis to an article about the evolution of CO.
Some more:
In 89 Weihl also showed that Dynamic atomicity is a maximal property that ensures global serializability when operations are scheduled dynamically during transaction's life. This is similar to CO being a necessary condition to guarantee global serializability for autonomous database systems.
Though the papers about Strong recoverability do not provide general algorithms, they state the importance of the property to achieve global serializability, and the fact that it is achieved when the property is present, like in SS2PL.


To JCLately: Being this article's author I answer you since you made some comments about the article itself, and not just about the text above.
"your statement does little to clarify it" - I do not think the writer above tries to clarify the article, but I leave it to him/her to answer you.
To be honest, my comments were as much directed at you, but I didn't want to put you on the spot. - JCLately (talk) 17:44, 19 May 2008 (UTC)
"I find this article essentially incomprehensible" - I'm sorry about this, but since this is a general claim, I do not know how and where to start help. Please be more specific. At least show to me the first sentence in the article that you think is not understood, and I'll try to elaborate or change if needed. A list of places will help even more. I would like to note that this article, like most in any specific category, assume some knowledge within the category.
Sorry if I put that too strongly or perhaps chose the wrong word. The introduction has a quality of wordiness and circularity without clearly expressing the basic concept. Each of the first two paragraphs concludes with a strong statement that doesn't clearly follow, or which is not strongly supported. - JCLately (talk) 17:54, 19 May 2008 (UTC)
Which article? Commitment ordering has only one paragraph in the intro. The last statement is elaborated in a whole section. Comps (talk) 23:00, 19 May 2008 (UTC)
In the preceding remark, I was referring to this article on Global serializability. The sentence "This makes global serializability a major goal for global concurrency control in multidatabase systems." doesn't quite logically follow. Also, the portion that precedes it seems to use too many words to say too little. As for the second paragraph, the final sentence is worded too strongly, I think. Instead of saying "would lead to...", I'd substitute "may lead to...". - JCLately (talk) 04:05, 20 May 2008 (UTC)
No and No. I suggest you study concurrency control and get better understanding before commenting on the subject. Comps (talk) 14:31, 20 May 2008 (UTC)
"I would welcome some effort to make this entire discussion and the related pages about commitment ordering more accessible to a wider audience." - Again, knowledge in transaction processing is needed. For Serializability and Commitment ordering you need also some mathematical background (pointed to with links in the articles). "Wider audience" is quite unclear. I think that the paper gives an idea about the subject to non-experts (however general knowledge in the category is still needed), but goes deep enough also for the experts. Look for example at a randomly picked Math article: Calculus of variation. It goes deep enough also for a person who knows a great deal about Mathematics, with material and notation that a non-expert cannot understand.
Having created Category:Transaction processing and recently rewritten the introduction to e (mathematical constant), it would be fair to conclude that I have some knowledge of those subjects - more than should be required of the intended audience for these articles. The applicable guideline I have in mind is WP:LEAD, the section under "Provide an accessible overview" in particular. Taking your randomly selected example, Calculus of variations, I think it does a better job of introducing the subject than this article, because the essential concepts are sufficiently expanded to convey the gist of the idea, concrete examples are provided, and links to a well-chosen selection of additional topics have enough context to guide the reader appropriately. - JCLately (talk) 18:44, 19 May 2008 (UTC)
I do not agree. I think my intro of CO includes all necessary info for an intro. Comps (talk) 23:00, 19 May 2008 (UTC)
"If it's so spectacular, surely a more convincing case can be made." - "Spectacular" is the writer's above opinion. However, if "convincing case" relates to the article, I believe that the article makes a convincing case about the importance of the CO solution: It describes quite in detail why CO provides an effective solution to the global serializability problem. It also describes that quite many people for long time have tried to find an effective solution, which makes Global serializability an interesting enough article subject. How this solution works is shown in quite a detail in the article Commitment ordering.
Comps (talk) 14:09, 19 May 2008 (UTC)
It seems as though all roads lead to Commitment ordering, the article I find most objectionable, if that isn't putting it too strongly. It would be helpful if the CO concept were further clarified from the outset, in the article lead section. In its present form, the lead doen't exactly "invite a reading of the full article". Claims about the wonderfulness of CO may need to be toned down, unless they can be better justified in plain English. - JCLately (talk) 19:16, 19 May 2008 (UTC)
"Claims about the wonderfulness of CO" - I see no sentence in the articles saying anything about "The wonderfulness of CO." So, it should be your own deduction from the articles. Please show me any claim that you think is false, or inaccurate, and if you are right, I promise you to correct it. The article is supposed to include only correct facts. Also, I do not care about "invite a reading of the full article." The introduction plainly and shortly describes the main characteristics of CO, following mainly the original CO paper's abstract (paper in the references). Thank you, but it looks sufficiently inclusive to me as an intro. I am not in the business of luring people to read articles. I am in the business of providing information and teaching in my area of expertise, the best way I can. In this case, as I already wrote, targeting from the non-expert to the expert. The rest of the article is a quite detailed description of various aspects of CO, which requires more expertise, where you can also find the mathematical definition with no mathematical notation. If you are interested, you may read any other part of the article. If not, nobody holds you. PS You have started this discussion under the wrong section title. Comps (talk) 22:30, 19 May 2008 (UTC)
Sorry, my response was only to your last section. Only now I see that you have responded in several sections. I'll read and respond later. Comps (talk) 22:39, 19 May 2008 (UTC)
Please see above, immediately after your comments. Comps (talk) 23:00, 19 May 2008 (UTC)
I have a problem with the tenor of arguments to the effect that CO is the long-sought "solution" to the distributed concurrency control problem. I'm not convinced that this is a widely held view, and it may not even represent the original author's claim. Perhaps CO would be more correctly described as an optimization technique, and it should be noted that CO can only go so far toward making distributed transactions practical. To describe it as a "solution", or to assert that it is in some sense guaranteed to be "effective", I think may be overstating its significance. In any case, a clearer explanation would help the reader decide whether to bother investing more time on this subject.
I didn't pull the phrase "invite a reading of the full article" out of the air - it's an excerpt from the Wikipedia:Lead section style guideline, to which I call your attention again. It is not easy to write a good introduction to a complex technical subject, and I appreciate that you are highly knowledgeable and have contributed a great deal to this and related topics. Nevertheless, I encourage you to consider the possibility that there might be room for some further improvement along the lines I've suggested. - JCLately (talk) 05:24, 20 May 2008 (UTC)
Look, It is obvious from your comments that you are not an expert in the area of database concurrency control, and probably have not published any research paper. You are welcome to find experts and consult with them on the subject, on the importance of CO, etc. While every article can be improved, I feel very comfortable with the current versions, after more than two years of refinement and presentation enhancements. I have not seen from you a single fact that contradicts anything I wrote. My articles deal with proven facts. If you have specific suggestions re text, please make them and I'll consider. Otherwise I see no point in continuing this discussion with you, since we get nowhere. Comps (talk) 14:31, 20 May 2008 (UTC)
Also it is obvious that you have not understood this "essentially incomprehensible" article (I asked for a single incomprehensible sentence and have not received...), which discusses what the problem is, and shows in great detail why CO is a good general solution to the problem, and why it is the only possible general solution for autonomous databases. Facts and only facts. Neither what I or this or that think about it, nor "Claims about the wonderfulness of CO," to use your expression. Comps (talk) 20:22, 20 May 2008 (UTC)
I have enhanced the Commitment ordering intro anyhow. Hope it helps a little Comps (talk) 18:17, 5 June 2008 (UTC)