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.
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.
Which Database Systems are Most Popular?
Despite what you may have heard, relational databases still rule
This article from ZDNet looks at a ranking of database popularity in August 2014.
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.
Finally, Travelling Salesman the movie. The trailer, sadly, peddles the nonsense that computer scientists are necessarily young, white, male and American. If you can face that, then the maths is — reportedly — 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.