Data dependencies and algorithms to mine them provide significant insight into unfamiliar datasets with limited metadata. They can be used to help identify constraints such as primary and foreign keys. Existing algorithms have focused primarily on mining dependencies from relational databases. Little attention has been paid to the explosion of semi-structured data from web services and NoSQL databases. This talk highlights some of the problems with existing approaches and presents new dependency structures and mining algorithms to handle this data.