 |
| Slides : Recording |
This afternoon the final lecture on Structure Data covered a range of database topics: ACID properties for transactions; the NoSQL movement; nested SQL queries, set operations, and aggregate queries; ultimate physical limits to computation; the wonders of the heavens captured in SkyServer; and the idea of doing scientific research and experiments from inside the database.
Links: Slides for Lecture 8; Recording of Lecture 8
Homework
Explore SkyServer, its different types of search, and try some SQL yourself. Work through at least the first three pages of the SQL Tutorial there.
Links: SkyServer; Famous places; SQL tutorial
SkyServer accepts queries from anyone and everyone: you don’t need an account or identity on it unless you want to run queries that return more than 100,000 rows or take over 10 minutes. If you manage to hit that limit, let me know — I’m interested to find out how.
Extra
-
Work out how https://is.gd/locatepluto persuades SkyServer to serve a non-dwarf-planet version of Pluto.
There’s a real SQL query there, and the page is genuinely from SkyServer. Some browsers may complain about subversive activity here, and they are right to do so.
References
 |
Which Database Systems are Most Popular? Despite what you may have heard, relational databases still rule This 2014 article from ZDNet looks at a ranking of database popularity. Since then things have shifted a little, but RDBMS remain well ahead. |
 |
DB-Engines Knowledge Base of Relational and NoSQL Database Management Systems Each month DB-Engines ranks database management systems by “popularity”, looking at job offers, Google trends, tweets, … Links: DB-Engines; This month’s top 10 |
 |
Hoag’s Object Ring Galaxy Eight billion stars, 600 million light-years away, shaped like a doughnut and with a bright inner core. Links: Hubble Telescope image; Wikipedia |
If you are interested in databases, their implementation and application, I recommend the third-year course Database Systems. If you would like to know more about complexity and the limits of computation, then take Algorithms and Data Structures.
The material in this lecture on complexity, exponential growth, and physical limits to computation is not examinable in this course, but these are important concepts in computer science and very likely to turn up again in your studies here.
- Wikipedia has a decent, if lengthy, article on the Travelling Salesman Problem.
- Wikipedia’s article on NP-completeness is a suitable introduction to the tangled web that is complexity classes.
- In the event you prove P=NP or P≠NP, you’ll want to contact the Clay Mathematics Institute about that $1M prize.
- The laptop illustration was from a Nature article on the Ultimate Physical Limits to Computation (May require EASE login).
- Wikipedia describes Bremermann’s Limit in its article on transcomputational problems. You can read Bremermann himself on this here:
- Optimization Through Evolution and Recombination. In Self-Organizing Systems, Yovits, et al. (eds). Spartan Books, 1962.
- Complexity and Transcomputability. In The Encyclopedia of Ignorance, Duncan and Weston-Smith (eds). Pergamon Press, 1977.
- Computronium is again on Wikipedia, and if you like that you’ll want to go on and read about Matrioshka Brains and other theoretical megastructures.
Last of All
 |
Travelling Salesman: The Movie Four mathematicians are hired by the US government to solve the most powerful problem in computer science history. “The moral uncertainty of a P=NP world” — New Scientist |
Yes, really. You can watch the trailer. The casting, sadly, buys into the persistent nonsense that computer scientists are necessarily young, white, male and American. If you can face that, then the maths is said to be sound, and the desert/coin analogy in the trailer is a great image for the nature of P vs. NP. What’s less clear is whether showing P=NP would have quite the social and political impact suggested.
