Today’s lecture was the final one on Structure Data and 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 nature captured in SkyServer; and the idea of doing scientific research and experiments from inside the database.
Link: Slides for Lecture 8
Explore SkyServer, its different types of search, and try some SQL yourself. Work through the first two pages of the SQL Tutorial there.
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.
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 (EASE login required).
- Wikipedia describes Bremermann’s Limit in its article on transcomputational problems. You can read Bremermann himself on this here:
- 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, peddles the 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.