Fermat's last theorem and the simpsons

Jack Dikian

November 2011

The theorem states that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two. Fermat's last theorem has been one of the most difficult problems to solve. It took over 350 years to solve and has precipitated more incorrect proofs than any other math problem.

Fermat claimed to have proved this statement but that the margin was too narrow to contain it. It is the seeming simplicity of the problem, coupled with Fermat's claim to have proved it, which has captured the hearts of so many mathematicians.

In 1995 Andrew Wiles released his 108-page proof after spending almost 7 years developing it. The proof is regarded to be one of the most complicated in mathematics and involved (chapters in Wiles’ paper) Galois representations, cohomology groups, Gorenstein property, congruences between Hecke rings, Selmer group, elliptic curves, Gorenstein rings and local complete intersections.

Fermat's last theorem even entered the fictional world of The Simpsons. In the episode “Treehouse of Horror VI” a sum, proved impossible by the theorem, the equation ‪1782¹² + 1841¹² = 1922¹² is visible. The joke being that the twelfth root of the sum does evaluate to 1922 due to rounding errors. Note that the left hand side is odd, while ‪1922¹² is even, so the equality cannot hold. Instead of 1922, it actually is 1921.999999995.

Jack Dikian

The MINI-SCAMP MICROCOMPUTER

Jack Dikian

October 2011

Today, like many others, I couldn’t but resist having a look at the new iPhone 4S with all the expected hype and media frenzy. I was particularly interested in its specifications, and more specifically the new processor chipset it is using.

According to reports the new iPhone is using the A5 chip, which is also used by the iPad 2. This is a dual-core Cortex A9 processor which is said to be up to twice the speed of its predecessor. Also, the PowerVR SGX543MP GPU embedded graphics accelerator is up to seven times faster than the GPU found inside the previous chipset. The A5 contains a rendition of chip based upon the dual-core ARM Cortex-A9 MPCore CPU manufactured by Samsung.

Now the chips’ manufacture claim that the performance optimized dual-core Cortex A9 can do 10,000 DMIPS (Dhrystone MIPS) at clock speeds of 2000 MHz. Remember that CPU performance is generally about the number of instructions it can execute in a time period (say a second) and the amount of actual work it can do in that period.

The first is controlled by CPU architecture, memory speed, etc while the second has those as variables, as well as the effectiveness of its instruction set at doing the sort of typical application it is used in. The Cortex A9 processor runs the Dhrystone benchmark at about 2.50 DMIPS/MHz per core – an extremely efficient architecture at the sort of application the Dhrystone measures.

The reason I’m taking an interested in this architecture isn’t so much about how Apple is using these processors as enablers in there consumer products, not that I’m complaining as I am and have been an Apple fan from the day I first used the Apple Lisa at university. More so, because I was recently reminded of the very first computer I built when I was a teenager. At the time, anyone that was half-interested in electronics either built a micro-computer or an Amplifier of sort. My friends and I were more interested in wire-wraps, logic gates, LEDs, and nasty RF-modulators. The very slow and erratic cassette tape interface came much later thanks to Radio Shack and the TRS-80.

So as high school kids, my friends and I would catch the train from North Sydney to an electronics hobby store in Hornsby where we got to see an “expert” demonstrate his Mini-Scamp microcomputer and us using what little money we had to buy the components so that we can each build our own.

The Mini-Scamp micro-computer was, I think, a Dick Smith Electronics kit the design of which was published in "Electronics Australia". The Mini-Scamp was based on the SC/MP CPU from National Semiconductors and boasted a [massive] 256 bytes of RAM. Yes, that’s all the memory it had. Just as a simple comparison my current iPhone 4 has 3,435,9738,368 bytes of memory.

This nifty computer didn’t come with ROM so the idea of accessing an interpreter or a compiler was still, for us, years away. So we would load binary into RAM by requesting the data byte and address in binary using toggle switches. Pressing the deposit button stored the byte in memory. The LEDs showed the current contents of the memory location. After the program was entered this way a switch was flipped from DMA to Run mode and the micro did the rest.

These days I sometimes have a little chuckle to myself when an IT helpdesk puts me on hold while trying to rectify a trivial password glitch – and wonder how they would cope if all they have to work with is a soldering iron, a bit of copper printed circuit board, and if really lucky a second hand CRO.

Fermat's Last Theorem

Jack Dikian

April 2011

Fermat's last theorem is a theorem first proposed by Fermat in the form of a note scribbled in the margin of his copy of the ancient Greek text Arithmetica. In 1637 he famously wrote in the margin of Arithmetica that he had discovered the proof however it was too large to fit in the margin.

“I have discovered a truly remarkable proof which this margin is too small to contain”.

Fermat's Last Theorem states that xn + yn = zn has no non-zero integer solutions for x, y and z when n >2.

Despite the efforts of many mathematicians, it took another 350 years for a proof to be developed. The British mathematician Andrew Wiles spent almost 6 years developing a proof that he published in 1993. However, by mid 1993, a bombshell was dropped. Several mathematicians began finding faults in the proof when refereeing Wiles' manuscript. The faults were finally repaired by Wiles and his former student Richard Taylor in late 1994.

The question remains today, had Fermat discovered a proof in the seventieth century. The proof by Wiles and Taylor utilized mathematics not available to Fermat. Ribet's proof of the epsilon conjecture in 1986 accomplished the first half of Frey's strategy for proving Fermat's Last Theorem. Wiles set off to prove the other half.

For example,

• Taniyama-Shimura conjecture for semistable elliptic curves.
  


• Horizontal Iwasawa theory


• Euler system


• Selmer groups


• Modular elliptic curves

Computing the “Theory of everything” (Strings)

Jack Dikian

String theory was originally developed to describe the fundamental particles and forces that make up our universe. New research, led by a team from Imperial College London, describes the unexpected discovery that string theory also seems to predict the behavior of entangled quantum particles. As this prediction can be tested in the laboratory, researchers can now test string theory.

Before strings

String theory is the most recent attempt to reconcile quantum mechanics and general relativity. It's the first candidate for the theory of everything, a manner of describing the known fundamental forces and matter in a mathematically complete system.

We learned in school that matter is made of atoms, which are in turn made of just three basic components: electrons [spinning] around a nucleus composed of neutrons and protons. In chemistry, some of us also learned that generally, there are as many neutrons as are protons in any nucleus of an atom. There are however isotopes where their nucleus contains an uneven mix of protons and neutrons.

It was quite comfortable for us to think of the atom in this way – somewhat reminiscent of planets revolving around the sun. The students that had a special interest in physics went on to discover that the electron is a truly a fundamental particle (it is one of a family of particles known as leptons), but neutrons and protons are made of smaller particles, known as quarks. Quarks are, as far as we now know, also elementary particles.

The universe is made up of atoms and forces through which atoms interact.

Our current knowledge about the subatomic composition of the universe is summarized in what is known as the Standard Model of particle physics. It describes both the fundamental building blocks out of which the universe is made, and the forces through which these blocks interact. There are twelve basic building blocks:-

Six of these are quarks which go by the interesting names of up, down, charm, strange, bottom and top. A proton incidentally, is made of two up quarks and one down.

The other six are Leptons and include the electron and its two heavier siblings, the Muon and the Tauon, as well as three neutrinos.

There are four fundamental forces in the universe:

§ Gravity,
§ Electromagnetism,
§ the Weak and
§ Strong nuclear forces also known as the colour force.

Each of these is produced by fundamental particles that act as carriers of the force. The most familiar of these is the photon, a particle of light, which is the mediator of electromagnetic forces. (This means that, for instance, a magnet attracts a nail because both objects exchange photons.) The graviton is the particle associated with gravity. The strong force is carried by eight particles known as gluons. Finally, the weak force is transmitted by three particles, the W+, the W-, and the Z.

We all recognize 2 forces very well – gravity and electromagnetism. We feel the pull of gravity and we use the force of gravity in our day to day lives. Some of us have also played with magnets and appreciate their pull force. The behaviour of the week and strong nuclear forces isn’t one that we observe in every day life. These operate at the subatomic level and bind sub particles with varying degree of strength. The strength of the strong nuclear force, for example, is many magnitudes greater than that of gravity on Earth. If the pull of gravity on was that of the strong nuclear force – we would weigh many trillions more than our current weight.

We use what we call the Standard Model to describe the interaction of sub-particles and forces with great success. This is, however, with one notable exception - gravity. The gravitational force has proven very difficult to describe microscopically. This has been for many years one of the most important problems in theoretical physics. That is to formulate a single model that describes both the micro and macro elements of the universe. Einstein attempted to unify the general theory of relativity (macro) with electromagnetism using a single field, hoping to recover an approximation for quantum theory. A "theory of everything" is closely related to unified field theory, and also attempts to explain all physical constants of nature.

Strings

In the last 20 or so years string theory has emerged as a promising model in attempts to provide a complete, unified, and consistent description of the fundamental structure of our universe, another “Theory of Everything”.

The basic idea is that all of the components of the Standard Model are just different manifestations of one basic element - a string. One way to think about this is by imagining an electron to be a tiny loop of string rather than a single zero-dimensional point. The loop (string) can as well as moving, oscillate in different ways. It is the way strings oscillate that determine the type of subatomic building blocks we recognize. So one kind of oscillation may be an electron whilst another oscillation may be regarded as a photon. This means, if true

The entire universe is made of strings

In recent years many developments have taken place, radically improving our understanding of what the theory is. String theories also require the existence of several extra, unobservable, dimensions to the universe, in addition to the usual four space-time dimensions.

Five major string theories have been formulated with the main differences between them, being the number of dimensions in which the strings are developed within and their characteristics. In the mid 1990s a unification of all previous superstring theories, called M-theory, has been proposed, which asserted that strings are really 1-dimensional slices of a 2-dimensional membrane vibrating in 11-dimensional space.

Quantum-connected computers overturn the uncertainty principle

Introduction

Back in the mid eighties when completing a pure mathematics degree and using the then state of the art mini-computers, the PDP11 family of processors (we couldn’t afford the services of the more, much more, brawny nitrogen-cooled Crays to solve sparse Hadamard matrices - I contributed an article in a UK computer journal discussing the future of computers, artificial intelligence, human interfaces and visualization – I guess you can call it a naive attempt to predict how systems will/MAY evolve. Of course this was through my own lens of experience. Watching processor speeds rapidly increasing and memory, disk and everything else growing almost exponentially.

Of course the implicit question was - If all that has happened in the first 50 years of computer history, what will happen in the next 50 or so years?

Moore's Law is an empirical formula describing the evolution of processors which is often cited to predict future progress in the field, as it's been proved quite accurate in the past: it states that the transistor count in an up-to-date processor will double each time every some period of time between 18 and 24 months, which roughly means that computational speed grows exponentially, doubling every 2 years. As processors become faster the science of computability, amongst other things describes a class called 'NP-hard problems' which are also sometimes referred to 'unacceptable', 'unsustainable' or 'binomially exploding' whose complexity and therefore computation grow exponentially with time.

An example of NP-hard algorithm is the one of finding the exit of a labyrinth: it doesn't require much effort if you only find one crossing, but it gets much more demanding in terms of resources when the crossings become so large that it becomes either impossible to compute because of limited resources, or computable, but requiring an unacceptable amount of time.

Many, if not all, of the Artificial Intelligence related algorithms are extremely demanding in terms of computational resources because they are either NP-hard or involve combinatorial calculus of growing complexity.

Not all developments in processing architecture stem from a single genesis. For example, recently, IBM researchers have made huge strides in mapping the architecture of the Macaque monkey brain. They have traced long-distance connections in the brain - the "interstate highways" which transmit information between distant areas of the brain. Their maps may help researchers grasp how and where the brain sends information better than ever before, and possibly develop processors that can keep up with our brain's immense computational power and navigate its complex architecture.

Artificial intelligence and cognitive modeling try to simulate some properties of neural networks. While similar in their techniques, the former has the aim of solving particular tasks, while the latter aims to build mathematical models of biological neural systems.

Another trajectory – that of Quantum Computers

The uncertainty principle is a key underpinning of quantum mechanics. A particle's position or its velocity can be measured but not both. Now, according to five physicists from Germany, Switzerland, and Canada, in a letter abstract published in Nature Physics(1) quantum computer memory could let us violate this principle

Paul Dirac who shared the 1933 Nobel Prize in physics with Erwin Schrödinger, "for the discovery of new productive forms of atomic theory” provided a concrete illustration of what the uncertainty principle means. He explained that one of the very, few ways to measure a particle's position is to hit it with a photon and then chart where the photon lands on a detector. That gives you the particle's position, yes, but it's also fundamentally changed its velocity, and the only way to learn that would consequently alter its position.

That's more or less been the status quo of quantum mechanics since Werner Heisenberg first published his theories in 1927, and no attempts to overturn it - including multiple by Albert Einstein himself - proved successful. But now the five physicists hope to succeed where Einstein failed. If they're successful, it will be because of something that wasn't even theorized until many years after Einstein's death: Quantum Computers.

Key to quantum computers are qubits, the individual units of quantum memory. A particle would need to be entangled with a quantum memory large enough to hold all its possible states and degrees of freedom. Then, the particle would be separated and one of its features measured. If, say, its position was measured, then the researcher would tell the keeper of the quantum memory to measure its velocity.

Because the uncertainty principle wouldn't extend from the particle to the memory, it wouldn't prevent the keeper from measuring this second figure, allowing for exact, or possibly, for obscure mathematical reasons, almost exact measurements of both figures.

It would take lots of qubits - far more than the dozen or so we've so far been able to generate at any one time - to entangle all that quantum information from a particle, and the task of entangling so many qubits together would be extremely fragile and tricky. Not impossibly tricky, but still way beyond what we can do now.


(1) Nature Physics
Published online: 25 July 2010 doi:10.1038/nphys1734
The uncertainty principle in the presence of quantum memory
Mario Berta, Matthias Christandl, Roger Colbeck, Joseph M. Renes & Renato Renner

A message into the future and even the past

Jack Dikian

ABSTRACT

Sending messages into the future and whatabout sending messages into the past

Bell’s theorem shows that there are limits that apply to local hidden-variable models of quantum systems, and that quantum mechanics predicts that these limits will be exceeded by measurements performed on entangled pairs of particles. This article discusses Bell’s theorem in the context of experiments that show that the predictions of quantum mechanics are consistent with the results of experiments, and inconsistent with local hidden variable models of quantum mechanics.

A series of experiments has demonstrated the quantum predictions that form the basis of Bell's Theorem and some would therefore claim that not only the predictions of quantum theory but also experimental results now prove, using Bell's theorem, that the universe must violate either locality or counterfactual definiteness.

So, basically, if entanglement through a spin placed on a particle results in another spinning in the opposite direction in exactly the same way and at exactly the same time no matter the distance between them – this may make for instantaneous communication, across in theory, any distance.

If we now consider learning’s from the twin paradox (see special relativity) in which a twin makes a journey into space in a high-speed rocket and returns home to find he has aged less than his identical twin who stayed on Earth. I.e. the twin, and everything else have aged at a much faster rate than him. He will essentially have traveled forward in time.

What if a particle is accelerated at a sufficient enough rate so that it travels forward in time, and at the same time second particle in the entanglement-pair is spun. Are we then essentially sending a message into the future.

Unsolvable Problem

Jack Dikian

October 1999

The Halting Problem is one of the simplest problems known to be unsolvable. Given a program and an input to the program (input-program pair), determine if the program will eventually stop when it is given that input.

Turing pondered if there was a way of telling in general once a computer has embarked on a calculation whether that calculation will terminate in an answer. This problem is known as the "Halting Problem for Turing Machines" and was first proved in the 1937 paper in which he described his machines.

My interest in this was caught when writing a Turing Machine simulator and was fascinated by the seemingly simple challenge – and Turing’s elegant solution.

Introduction

Briefly, a Turing machine can be thought of as a black box, which performs a calculation of some kind on an input number. If the calculation reaches a conclusion, or halts then an output number is returned. Otherwise, the machine theoretically just carries on forever. The problem is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

There are an infinite number of Turing machines, as there are an infinite number of calculations that can be done with a finite list of rules. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines.

Break here

Download author's Turing Machine simulator and article "Halting Problem Made Simple, October 1999"

Apparatus For Removing Hidden Lines from Bezier Surfaces

Jack Dikian

November 2000

This paper describes the work carried out by the author in implementing an apparatus for removing hidden lines from Bezier surfaces on the Tektronix storage tube technology of the early 80’s.

Bézier surface

A Bézier surface is formed as the cartesian product of the blending functions of two orthogonal Bézier curves. Bézier surfaces, first described in the early 60’s by the French engineer Pierre Bézier and used in automobile body design.

Hidden lines

When rendering a three dimensional surface on a two dimensional plane such as a computer screen, lines which should otherwise not seen by the viewer must be removed. The shape of the surface, if opaque, should not be cluttered by overlapping lines. Importantly, our real world experience does not allow for us to “see” through what is a solid surface or object.

In order to remove these lines, hidden line algorithms are applied in the surface rendering software to create a wire-frame which contains only visible lines and hides the lines covered by the surface.

There are a number of algorithms used to remove hidden lines. Arthur Appel’s work at IBM in the late 1960’s for example works by propagating the visibility from a segment with a known visibility to a segment whose visibility is yet to be determined. By a comparison of the two following images, the line removal algorithm can be seen at work as the wireframe representation of the surface shaded object removes the lines which are not in view.

Whilst much of the initial work in hidden line removal was done by Arthur Appel, the field is still growing as there are exceptions when his algorithm is not effective. There is a variety of other algorithms which are implemented in computer-assisted design such as the object-precision algorithms of Weiss and Galimberti/Montenari and the image-precision algorithms Encarnacao (priority-edge intersection test and scan grid – point/surface test), Warnock, and Watkins.

The Approach

Grammatical Extensions to the Structured Query Language SQL

Jack Dikian

ABSTRACT

The SQL+sh is an interactive front-end to Unify’s Structured Query Language (SQL). It’s main purpose is to add Csh/tenex like functionality to a vanilla query interpreter in the way of SQL.

A query history stack, ability to recall and edit previous queries as well as an interactive RECORD and FIELD name recognition and completion mechanism are a sample of the sort of enhancements SQL+sh supports. This paper presents a brief background to SQL before discussing some of the features we added to this package. Working in an environment where a significant portion of a programmer’s time is spent writing and maintaining applications software around the Unify Relational Database; any facility that simplifies database interactions must be an advantage. This database is quickly approaching the 2 G-byte mark with over 300 Mb of supporting software. Like other large database users, the overhead of database related maintenance is a significant consideration. Improvements in database related utilities greatly increases productivity as well as reliability.

One of the most powerful facilities available to the maintenance programmer in our environment is Unify’s Structured Query Language SQL. This utility is often used to interrogate as well as patch the underlying database. Adhoc SQL queries are often generated to confirm the correctness of application modules as well as serving the more simple day to day user information requirements.

A Quick Look At SQL

SQL is an english keyword orientated query language of great flexibility. It is a language that is easy enough for non-programmers to learn, yet has enough power for data processing professionals. This product was originally defined by Chamberlin and others at the IBM Research Laboratory in San Jose, California, under the brand name System R. A family of IBM products based on the System R technology was developed. These products are now generally available and are known as DB2, SQL/DS and QMF [1].

A number of other vendors have also produced systems that support SQL. SQL’s data manipulation statements typically operate on entire sets of records. For example, the select and update clauses can retrieve and modify a set of values and tables. SQL, like all relational data manipulation languages is a set-level language. For this reason, SQL is often described as a non-procedural language. The user specifies "what" data they want and not so much "how" to get it.

It is up to SQL to decide on how best to execute any particular query. It needs for example to consider which tables are being referenced in any request; the size of the tables; what indexes exits; how selective those indexes are and of course, the form of the where clause. SQL queries consist of clauses, each of which is preceded by a keyword. Examples of keywords include; select, update, delete and insert. In fact, the previous four keywords all belong to that part of SQL which is commonly referred to as the DML or Data Manipulation Language. Other optional keywords are used to control, format and operate on the various queries. Some simple examples of queries are given below:-

> select Name, Phone
> from PERSONS
> where Age > 30/

The above example illustrates the selecting or retrieving of the specified fields Name and Phone from a specified table PERSON where some specified condition is true. It is important to note that the result of the query is another table.

> select PERSON.*, COMPANY.*
> from PERSON, COMPANY
> where PERSON.PName = COMPANY.CName/

This example demonstrates the retrieving of data from two tables namely PERSON and COMPANY. We are interested in all instances of the field PName in PERSON matching the field CName in the table COMPANY. This is commonly referred to as "Joining" two or more tables. The availability of the join operation is, almost more than anything else that distinguishes relational from non-relational systems.

The SQL+sh

Our main database currently supports over a 100 tables and close to a 1000 fields. Using SQL to interrogate and manipulate data in this environment almost always requires the programmer to first browse through the Database schema listing. This is not only due to the large number of different tables and fields but is also due to UNIFY’s record and field naming conventions. The maximum length of a record name is eight characters. It is therefore impossible to create two records with the names "PROGRAMMER" and "PROGRAMME". A compromise may lead to the names "PROGMR" and "PROGME" etc. It is easy to see why the schema listing may be required in such cases. Creating tables in Unify requires the user to nominate both a short and a long field name. Short field names must begin with a letter and can be up to eight characters long. The long field names begin with a letter and can be up to sixteen characters long. It is the long name that SQL requires for carrying out queries.

The schema is used to determine or look up this long name. The schema is also used to determine relationships between tables and their corresponding fields. Editing large queries are handled by - SQL writing the last query in/tmp. The edit facility invokes a standard editor such as vi with the last query loaded in the editor buffer. The user modifies and saves the changes before using the restart clause to re-execute the query. Although this facility is useful, it is however often tedious. This is especially true when a simple typo needs to be repaired. Because only the last query is effectively saved, access to previous queries are lost unless the user explicitly saves the editor buffer to a nominated file. Interestingly, we required in SQL a similar transformation in functionality as that provided by say csh and tcsh over the bourne shell. Where tcsh provides file name recognition and completion, we required record and field name recognition and completion.

Where csh provides a history and edit facility for commands, we required, a history and edit mechanism for queries. In implementing some of the ideas found in csh and tcsh, we were able to address both the above mentioned short-commings as well as provide a much more effective user interface. Not having access to SQL source, the only other alternative in implementing the above changes was to write our own parser sitting on top of SQL. This would simply read the input stream, decide if it needs to act upon, and manipulate the history stack, carry through edit commands, expand alias’ etc and then write to SQL via a pipe. The output of SQL is not and should not be altered.

SQL+sh reads a schema description file on startup. This file is typically generated by the systems administrator by running a specially written shell script. The description file describes the database tables, there respective fields and other information such as field type and length. The shell script uses SQL to dump the relevant table, field types and names. On startup, SQL+sh looks at the environment variable DBPATH and displays the the name and address of the working database. After this point, SQL+sh enters a for-ever loop waiting for queries, internal commands and or the end clause. A new prompt including the event number is displayed. An environment variable defines the maximum history size. An internal command has been added called "Mod On/Off" which enables and disables the availability of non-passive SQL clauses. For example, after entering the command "Mod Off", such clauses as delete, update, insert are disabled or ignored. This is useful in cases where support staff use SQL to answer quick telephone queries and should not update the database inadvertently. Unlike Unix commands which are newline terminated, SQL queries often span over many lines. In fact, users of SQL are encouraged to use good formatting procedures when making SQL queries. This is in part due to the fact that quite complex SQL scripts can be written and saved for regular use. These scripts are also used to feed data to Unify’s report generator RPT. The "/" character is used to indicate the end of a query. For this reason, SQL+sh supports a modified history substitution command in the way of "!event+". This signals SQL+sh to re-execute the query beginning with the event number "event" and continue to re-execute events forward in the stack until a "/" character is encountered. All other normal history substitution commands such as "!!", "!- number", "!number" as well as "!pattern" etc have been implemented. Where a query spans many lines, SQL+sh collects together the individual clauses to echo a single event in its history stack.

Editing previous queries are handled two ways. The standard SQL procedure is to invoke the system editor with the last query loaded into the editor buffer. The edit clause facilitates this procedure. This method is still available and is usually used for editing large query texts. This method allows only the last query to be modified and executed. SQL+sh introduces the csh like "!event s/patternl/patternl" and ^patternl^pattern2^ mechanisms. These are extremely convenient for repairing typos and or for substituting record or field names while leaving the general structure of the query untouched.

One of the most useful additions to SQL was the introduction of record and field name recognition and completion. The idea here was to provide a convenient way to avoid having to look up the record and field names before generating queries. Automatically displaying field types and length was considered useful. Other considerations included providing a means by which key strokes could be reduced and accurately associating relevant field names to their correct parent tables. This mechanism is used in conjunction with the database schema description file. It is no longer necessary to type a complete record or field name. Only a unique abbreviation is necessary. Typing the ESCAPE key after the abbreviation will complete the record or field name, echoing the full name. Unlike tcsh, where there is really only one type of file name completion, SQL+sh needs to consider context and determine whether a record, or field name is being sought. This is achieved by adding some of the SQL syntax rules into SQL+sh.

For example the following grammar extracts the syntax for the insert and select clauses:-

insert into RECORD [(FIELD .... )]:
from filenamell select/ select ["unique"] I * I RECORD.* I RECORD.FIELD I FIELD ....I * I RECORD.* I RECORD.FIELD I FIELD ....
from I RECORD [label] I .... where ["not"] I FIELD I RECORD.FIELD I constant ETC.

SQL+sh tries to carry out a search of either the appropriate record or field based on the position the ESCAPE key was pressed in the input stream. It is obvious from the above two syntax examples that it is not often possible to determine whether a RECORD or a FIELD needs expanding. In the select clause for example, it is possible to say "select record.field from ..." or " select field from...". Hitting the ESCAPE key just after the select token leaves SQL+sh with a choice of searching for appropriate records or fields. In fact, in this particular example, the system will first search through the record list and then the field list. In general, as each word is read, SQL+sh updates a flag indicating whether it is in a "RECORD" or "FIELD" state. This flag is initially set to a "NULL" state thus causing an alert when the ESCAPE key is pressed. A "BOTH" state causes SQL+sh to search records and then fields. This state is established by tracking entered words against various syntax rules defined in SQL+sh. We have also provided a means of commenting query text. Text found enclosed within the "{" and "}" braces are ignored. This facility was implemented in order to allow a clean method of displaying field types and length in-line. On Hitting ESCAPE in a "FIELD" state, the system will not only display a candidate field name but also place the relevant field type and length already commented.

Besides providing a recognition and completion mechanism, SQL+sh also provides a facility where fields belonging to a particular record can be scanned. For example, after having typed in the sub-clause

select * from
PERSON where " it is possible to Hit Ctrl-f to echo the first field belonging to the PERSON record.

Hitting Ctrl-f again will replace the first displayed field name with the next field. When the list of fields are exhausted, the process is repeated. This allows the user to carry out a query on a record even when they had no idea of the field names associated with the given record. The field type and length is once again displayed in comments. Some examples follow:-

select * from PE"
select * from PERSON

results in the cursor sits at the next column position waiting for the rest of the query.

select * from PERSON where
results in
select * from PERSON where PName {STRING 12}
Hitting again results in
select * from PERSON where Paddress {STRING 45}

The user can now enter the rest of the query

select * from PERSON where Paddress {STRING 45} = ’Bag End*’
Hitting here results again
PAge {NUMERIC 3 }
PAge {NUMERIC 3} <= 111/

Now we can enter the rest of query Often there is the need to carry out repetitive queries involving tests against large text constants such as "0 081 12346789050" and "Speak Friend And Enter". An ability to implement a concept of macros was also considered a useful enhancement. The same query is often re-executed many times over in the event of a Database maintenance session. One or more parameters in the query may however vary. An ability to expand VMS like "Logical Variables" was added to SQL+sh. The same variable setting and expansion mechanism is used to set and unset simple and complex variables. There is no inherent differences between variable substitution and macro processing. The difference is operational. SQL+sh maintains a set of variables each of which has as a value a list of zero or more words. Each word in this list could be a simple constant or another variable. This value may be displayed and changed by using the internal commands show and clear. After the input line is parsed, and before each query is executed, variable substitution is performed. Variables are keyed by ’$’ character. The expansion can be prevented by preceding the ’$’ with a ’V except within ’"s. A Macro with a single argument can be seen as a variable containing another variable in its assignment string. The second variable has to be resolved before the macro can be executed. Newline characters found in the assignment list are ignored. Looping is prevented by checking that the same variable does not appear in the assignment list of that variable.

Examples of variables follow:-

[1] $new_name = "Bilbo Baggins"
[2] $my_update = " update PERSON
[3] set PName = Snew_name
[4] where PName = ’ *’/"
[5] Smy_update

We have been using this utility on a trial basis for the last few weeks. In general, the added convenience of query recall and edit far exceeds the cost of overhead. The ability to echo the field length and type results in much less references made to the schema listing. Record and field name completion means less typos in general.

References

[1] C.J. Date, "An Introduction To Database Systems", Addison-Wesley 1986.e, Australia; 13th- 15th September 1988.