The scheme consists of three tables, street, city and zipcode that all have a many-to-many relationship to each other.
What I want to do is a prediction that queries the database for possible matches as well as predicting missing data. To put it more into an example: Let's say the user starts typing in a city, perhaps "Wash". He already had a street typed in, for sake of me not knowing any streets, let's call it "New Street Avenue". This is a constraint, meaning it must be fulfilled in our prediction. Now I want the city to query for possible finishers of "Wash" as well as supplying missing data, in this case, zipcodes, that have a street called "New Street Avenue"
Here's how the naive approach would be:
- Filter street for all keys whose name match "New Street Avenue"
- Filter street_city for all the street keys and return the city keys
- Inner join the city keys on city_zipcode, and then Inner join those onto zipcode
The issue with this approach: The knowledge between street and zipcode is completely ignored. That means we could end up with zipcodes and city pairs, where we know the city contains the street we seek for, but the zipcode doesn't necessarily. This would be an invalid prediction to return, because the address doesn't exist!
That means I need to "persist" the information about street further down the line.
My approach would be this:
- Filter down street for the keys that fulfil our condition.
- Inner Join street onto city for the keys from #1. Keep both key columns.
- Inner join onto city_zipcode keeping the zipcode keys as well
- Filter out all the street and zipcode pairs that are not present in street_zipcode
(On a sidenote: to "hopefully" improve performance, after each "prediction" I would put a LIMIT 10 (or similar) command since we only need a sensible amount of predictions).
This approach should work. It might not be the best optimized, but it would return the correct results. However this not only feels very dirty to me, but also opens up another problem:
I'm pretty sure it scales horribly, in table size as well as in additional tables
There is a good likelyhood there will be another table that has Many-to-Many relationships towards, for the sake of argument, street and zipcode. Now if I wanted to search for a city with a street constraint, I need to do what I did above, and add even more to also filter out any relationships between street and the new table.
I feel like I'm going into a dead end with this approach. I'd love someone to help me out here on how to approach this problem better.