I know that DDL is most often used when talking about databases, but I see no reason why XML, PDF or even to some extent Prolog shouldn't belong to this category. It looks like branches of CS traditionally associated with studying languages wouldn't do very good job at analyzing DDLs.

Whichever approach to semantics you take, it doesn't seem to be meaningful, when applied to structured representation of data.

The notion of complexity is only so much relevant to data structures - it tries to answer the question of what would it mean to use a data structure for a particular task, but not the questions about the data structure itself.

Another reason for me to ponder this question is that based on my intuition, I can say things like "this data definition language seems to be better suited for the task", or "this data definition language seems to do a bad job when modelling the real-world situation", but I don't know where to look for the formalism which may support or debunk this intuition.

The comments suggested that I rephrase the question. Of course quality is a very broad concept, but I'm not only interested in efficiency. Or, more precisely, I don't really know what does it mean for a DDL to be efficient.

I will make it furthermore concrete. I was tasked with improving a file format of an application for editing presentations. The current version of this format is an XML, which basically dumps the application state at the time the user requested to save the file, and that's it. There are multiple downsides of this approach, beside the entire format was created ad hoc, unsystematically etc.

I red the Grammar of Graphics by Wilkinson, and thought that it had many great ideas about how to generalize and conceptualize in conceptually similar field. I also red about Allen's interval calculus and some other literature on how to formalize time in language. But more then just a set of ideas, I need some sort of quality assurance. Something that would give me some sense of guarantee, that the tools available to the language do indeed meet the needs, and that they do it in an optimal way (or not, and if not, then how far off am I). Of course it might be too naive to expect to have a metric that would just produce a numerical answer, but anything that I could use in the same way one could use asymptotic analysis would be great.

I did try to find an answer to the question myself. Here is the closest I think I found so far:

Orthogonality principle, as stated by Wilkinson in Grammar of Graphics:

As much as possible everything should work everywhere and in every combination.

Hierarchy principle

Complicated tasks should be done by enlisting support of simpler helpers.

While this sounds reasonable to me, I don't know how to approach the task of calculating these.

I also took courage to add one more principle:

Comprehensiveness. The notation should observe the bounds imposed by physical abilities of the reader.

Beside these, I tried to approach the problem from linguistic perspective. There is, for example, a notion of a measure of entropy of a grammar (for example, if talking about Hausdorff dimensions and topological entropy). But this is both too advanced for me, and I don't think this is "a thing" about data definition languages.

I also tried to approach the problem from the perspective of expressiveness, for which purpose I've been reading Matthias Felleisen On The Expressive Power of Programming Languages, but I find the analogy too removed / difficult to apply, because this book models its notion of expressiveness on lambda calculus, which doesn't fit well with what I'm trying to understand.

  • $\begingroup$ What are you asking, precisely? The question in the title is too unspecified, and in any case is not research-level. $\endgroup$ – Andrej Bauer Sep 6 '14 at 17:41
  • $\begingroup$ @AndrejBauer what part of the question was difficult? How do you know it's not a research level question if you just said you don't understand it? You also managed to put your question in a way I don't know how to respond to it, because it both contains a question and an automatic answer you gave to it yourself. $\endgroup$ – wvxvw Sep 6 '14 at 18:41
  • 2
    $\begingroup$ Ok, to be more constructive: I think it would be better to rephrase the question as a reference request. State a specific problem (such as "how to analyze the efficiency of various data definition languages in practice") and see what references you get. The way the question is stated now just asks for people's opinions. $\endgroup$ – Andrej Bauer Sep 6 '14 at 20:13
  • 1
    $\begingroup$ Because you missed the point of my question in the previous comment, let me more explicit. I would suggest you modify the question to make it clear instead of adding some text while keeping the unclear question as is. You had posted an unclear question, and a commenter had asked what you were asking. You then added some text which explained something, keeping the original unclear question intact. That is not a good use of people's advice, and may drive some readers like me away. $\endgroup$ – Tsuyoshi Ito Sep 7 '14 at 9:56
  • 2
    $\begingroup$ I am not interested in discussion. I am hoping that you will improve the question for the benefit of yourself, not because I think that the question is unclear. $\endgroup$ – Tsuyoshi Ito Sep 7 '14 at 11:53