Вопрос философского толка, однако ;) Первое условие уже содержится в самом вопросе - данные в наборе должны быть связаны. Ну, а второе напрямую вытекает из первого и заключается в том, как же именно они связаны. Базой данных можно считать набор данных, связанных в контексте некоторой предметной области, причем связаных так, что это позволяет делать выборки данных, отвечающие на вопросы этой предметной области.
Например, в контексте поиска телефонных номеров...
Городской телефонный справочник - это база данных, т.к. данные в нем связаны таким образом, что позволяют находить номера. Если же мы перекроим его так, что каждому телефонному номеру будет поставлен в соответствие номер страницы, на которой этот номер напечатан, а каждой фамили - сумма отдельных цифр в телефонном номере, этот набор данных перестанет быть базой данных в контексте заявленной области (хотя в нем будут все данные из исходного набора, и даже больше)... зато легко может стать таковой для каких-нибудь гороскопно-нумерологических задач.