views:

192

answers:

1

So I'm taking the Discrete Math course from MIT's OpenCourseWare and I'm wondering... I see the connection between relations and graphs but not enough to "own" it. I've implemented a simple state machine in SQL as well so I grok graphs pretty well, just not the more rigorous study of how relations and sets compeltely apply. Should I just be following the Yegge train of thought where I just glance over the stuff that I'm not grokking readily and come back when I've learned more? I'd like to be able to better analyze the graph structures I create on a day to day basis (sounds fun) and I want to make sure I'm not passing up valuable information right now.

(EDIT: I'd like to get a better idea of how the different set and relation properties relate to things like graph theory and how basic graph theory relates to sets/relations.)

Any good resources where I could learn more about this? I'm using the 5th edition of Discrete Mathematics and Its Applications by Rosen in case it matters.

Thanks!

+3  A: 

wow, 4 hours and no answer; i had a similar experience in school but just learned the stuff and figured out what it was good for later. it turns out to be very useful, so let's see if this helps -

a database is formally defined as a set of relations, but it is also a graph; each table is a node, each column is a node connected to the table, each row is a node connected to the table, each field is a node connected to the row, relationships between tables interconnect nodes, foreign-key relationships interconnect rows, query constraints (where clauses) and joins interconnect nodes and sets of nodes, and so on.

An SQL query may be visualized as traversing the graph formed by the database relations and values and performing operations on each node. Under the hood that is what the query execution planner does, it breaks down the query into a set of fundamental operations and arranges them in a graph that is most efficient.

Updates to your database may also be thought of as graph operations, e.g. updating the quantity in an order line item row propagates the change to the the total in the order row, which propagates the change to the TotalSales in the Customer row, and so on.

many common problems devolve into graph-traversal problems. Ever used Google Maps to get directions to some place?

Steven A. Lowe
Awesome thank you Steve!
Justin Bozonier