A Life in Research
APPENDIX C: THE NATURE OF COMPUTER-SCIENCE RESEARCH
There is a fundamental difference in Particle Physics (PP) research in which I was earlier engaged in, and Computer Science (CS) research in which I entered later. In PP the objective is to discover the natural properties, often expressed in complex and abstract mathematical models, which can take long computer time in evaluation. The length of computation time does not bother a physicist as long as the model is correct. In contrast, a quick execution is an essential requirement of a computational model, even if it means cutting some corners.
Computer Science is a technological science, which can be defined as:
A good (i.e. sound) computational model for the problem domain.
There may be many computational models (unlike the single reality of fundamental physics) to solve a problem, where the researcher is looking for the best one, but unlike physics, the best one will not be necessarily acceptable if it is too complicated and computationally too expensive. For example, it is possible to make a generalised CS model for a problem domain, but a generalised model could be computationally too expensive, and hence would not be used. In contrast, a generalised model is the one that a physicist will generally prefer, as it will be assumed to reveal the deeper truth – here the computational cost is irrelevant. Consider the experiments in CERN for finding Higgs bosons. The researchers there do not talk about the computation times of various modelling options, what they talk about is the result, i.e. if a signature for Higgs bosons has been found. I am not saying that researchers do not care about efficient computation, but it is far lower down in the food chain.
Here is a good experience that I had on this in 1982, when I produced a general architecture for distributed databases (DDBs), which was well-received by the CS researchers. The idea was that a diverse range of databases, of different data models (i.e. different data-structures and query languages), including pre-existing databases (each such database situated perhaps at a different network node), should be able to join a distributed database system, through which a user should be able (i) to treat the underlying databases as “a single database”, (ii) to query that “single database” by a global language and (iii) to receive integrated answers. Such a facility requires all these underlying databases to support inter-database conversions and interpretations (both semantic and syntactic) of data-structures and query languages, transparent to the global users. The necessary conversions, which are complex and time-consuming, have to be carried out dynamically as global queries are presented to the DDB system for execution. Contrast this position with Google search, which simply lists articles from different sources for the inquirer to view and read, nothing more. Its chief virtue is its execution speed. There is no attempt in Google to combine these answers (articles) into a single integrated answer (article), and hence Google is not a distributed database (DDB) facility. A DDB is far more ambitious, and its answers from different remote sources include both data and text, which involve as mentioned above, both semantic and syntactic interpretations for the production of a single integrated global answer, and hence its complexity.
The IBM ignored such a genuine distributed database facility, and instead extended the software of their existing SQL database system, allowing the data of a single database to be partitioned and held over multiple computers connected by a communications network. They called it a distributed database, which made us very cross – a betrayal of the concept of true distributed databases, we thought. We had then a DDB conference that year in Berlin, which I attended. I was riding high, because of my DDB architecture. An IBMer presented their DDB architecture, but he was attacked by everyone, so much so that he escaped from the rest of the conference. But today it is the IBM’s version of distributed database that is used, nobody would even implement our model, which they would consider impracticable. However, I still believe that sometime in the future, people might implement a distributed database facility of my kind for at least in-house management reports from diverse sources.
Given the definition of CS as a good (i.e. sound) computational model for the problem domain, how do we go about doing CS research? I present the following approach that guided us, but using example from the development of the Relational Database Model for clarity.
Observe that in Computer Science, invention is said to be harder than discovery, since invention has to be based on the solid foundation of experimentation. Invention, I presume, is our aim. Borrowing some ideas from Professor Milner of Edinburgh, and with some modifications, I produced my version of an approach to invention research:
- Examine a problem domain, and abstract the requirements. Sometimes several problem domains can lead to the same abstraction and also some aspects of the problem domain could be too different (or too complex) to be captured by a single elegant abstraction theme, that is, the abstracted domain may not model the whole of problem neatly, but only part of it. This is okay.
- Produce a good solution (a sound computational model) for the abstracted domain.
- Demonstrate that the model works not only for that problem domain but also for similar other problem domains.
- The wider the range of problem domains over which this model works, the better is the model.
Consider the Relational Model as an example. Dr E. F. Codd [Ted Codd] was trying to represent data in a simple way that could be queried also in a simple way. He thought of tabular structures, but he also understood that all data may not be amenable to a tabular form. For example, repeating groups (e.g. number of windows in a house, or the number of months in a year) and hierarchical structures (such as a name made up of surname and initials) require more complex data structures than simple tables. Maps and engineering drawings are further examples of complex structures that cannot be easily represented by simple tabular data.
He accepted these limitations and developed a query language with five basic operations for handling tabular data. (i) how to extract one or more columns from a table, (ii) how to extract one or more rows from a table, (iii) how to insert rows of one table into those of another, (iv) how to remove rows from a table, and (v) how to insert column(s) of one table as additional column(s) of another table.
He defined these operations mathematically (i.e. with precision) and proved mathematically that these five operations are necessary and sufficient for all operations over tabular data structures (i.e. in the relation model), except for some statistical operations, such as average, minimum and maximum values, etc. Observe that any single value can be thought of as the value of a table of one column and one row. This is the power of the model where all operations over one or more tables produce another table as the result, successively. Needless to say that the success of this model has been so staggering that people have now extended it even for some non-tabular data-structures.
The criteria we used to judge the success of a model is: does it make SENSE? The SENSE criteria are:
S Soundness: that is the model is sound.
E Employability: that is, the model can be employed directly on a problem, without any further and subjective assumptions. Many models fail on this, when the provisions of a model require further, often far-away, subjective interpretations before the model can be applied to solve a problem. Some PhD theses (models) fail utterly on this employability criteria.
N Necessity: that is, the assumptions made are as few as possible i.e. MINIMALLY necessary assumptions. It implies that all assumptions must be orthogonal with respect to one another, without any overlapping assumptions.
S Sufficiency: that is, the concepts used are sufficient – no further concepts are needed to solve the problems in that domain.
E Efficiency and effectiveness: that is, the solution is efficient and effective.
Everything should be made as simple as possible – but not simpler – A. Einstein.