В очень широком смысле БД можно считать массив данных, о структуре которого у вас достаточно информации для выполнения необходимых вам обработок, выборок и, вообще, операций. Например, если вы смотрите на бинарник в HEX-редакторе, и даже представления не имеете, что там - видео, картинка, или же записи о сотрудниках предприятия (ну или "догадываетесь" что там, но все же не имеете в распоряжении формальных и четких правил обработки этого набора байт), то это не база данных. Если же вы знаете, что в первых 4-х байтах у вас количество записей, а дальше - сами записи о сотрудниках, длиной 150 байт каждая, и вы знаете, где в этой записи нужные вам ФИО и зарплата - то это уже простейшая БД.
Важно также, чтобы эти данные в той или иной степени отражали реальный мир: это могут быть актуальные данные, архивные (исторические) данные, но так или иначе вам должно быть известно (!), как эти данные соотносятся с реальностью. Даже если это тестовые данные, сгенерированные случайным образом - вам это должно быть известно. Иначе невозможно понять, можете ли вы в реальной системе принимать решения на основе этих данных, или нет.
Конечно в современном мире файлик с записями "базой" обычно не называют, поэтому есть и другие критерии, например, упомянутая вами связность, и возможность ее реализации. Кроме того, если говорить о системе управления БД, то у нее должен быть формальный интерфейс для выполнения запросов по обработке данных - выборок, добавления и пр.
Кстати, на вопрос проще ответить, если вы укажете конкретную модель БД - реляционную, объектную, или, например, документную. При введении модели вводятся и правила, которым должны удовлетворять данные, чтобы называться Базой данных.
