Design

Hardware

Cisco
Mikrotik

Nets

Protocols

OS

FreeBSD
Linux
Other
Unix
Windows

Programming

Delphi
Java
Perl
Php
Shell
c_c++
git

Software

Backup
Mail
MySQL
Other
Postrgre
SQL
Secure
Security
apache
asterisk
cron
dhcp
ups

Web

Ajax
CGI
HTML
Javascript
XML

Software

Backup

Mail

»нтеграци€ Postfix, Maildrop и DSPAM - 11.07.2011

MySQL

InnoDB | ¬нешние ключи и транзакции - 18.05.2012
«ащита —”Ѕƒ с GreenSQL-FW - 09.06.2011
ќптимизаци€ запросов с помощью индексов - 12.07.2011
–асширенный анализ эффективности индексов в MySQL - 09.06.2011

Other

D-LINK DHCP Relay option 82 - 09.06.2011
FreeRADIUS as DHCP server - 09.06.2011
GSM-voip шлюз addpac GS1002 и Asterisk - 09.06.2011
ISC-DHCP - 09.06.2011
Multicast routing дл€ IPTV - 09.06.2011
NAS на MPD. ћен€ем скорость пользовател€ находу - 09.06.2011
NetFlow - 09.06.2011
OpenSER Ц ограничение SIP регистрации по IP адресам - 09.06.2011
OpenVPN HOWTO - 19.12.2011
Oбновлени€ проекта работающего с svn на сервере через FTP - 09.06.2011
Ђѕрив€зкаї IP телефона к определенному FXO порту. Translate pattern - 09.06.2011
Ѕлокировка нежелательного DNS трафика - 09.06.2011
»спользование Tripwire - 09.06.2011
 ак установить ProFTPd в Debian 6.0.1 - 09.06.2011
 эширование в Nginx - 09.06.2011
Ћокальный nntp-сервер - 09.06.2011
ћастер-класс управлени€ FreeBSD: ƒелаем домашний сервер с собственным именем в Internet - 09.06.2011
ћониторинг серверов с помощью Zabbix - 09.06.2011
ћониторинг сети с помощью tcpdump - 15.03.2012
Ќагрузочное тестирование web-сервера при помощи siege - 09.06.2011
Ќастройка Squid в св€зке с Rejik - 18.05.2012
Ќастройка и использование screen во FreeBSD - 09.06.2011
Ќастройка св€зки Sendmail+SASL с использованием TLS SSL - 08.09.2011
ќрганизаци€ IPTV-трансл€ции - 09.06.2011
ѕеревод руководства по Quagga - 29.08.2011
ѕрикручиваем spf к postfix-у - 09.06.2011
ѕринципы разработки биллинговой системы - 09.06.2011
—обираем HA кластер - 26.08.2011
—оздание man страницы - 09.06.2011
”становка и настройка ProFtpd - 09.06.2011
÷ентрализованна€ схема управлени€ сетью с использованием OpenLDAP - 09.06.2011
„то такое выравнивание, и как оно вли€ет на работу ваших программ - 09.06.2011

Postrgre

SQL

—сылочна€ целостность €вл€етс€ важной дл€ баз данных

—сылочна€ целостность €вл€етс€ важной дл€ баз данных

ѕредисловие переводчика

—тать€ "—сылочна€ целостность €вл€етс€ важной дл€ баз данных", написанна€ ћайклом Ѕлахой в 2005 г. специально дл€ портала
www.odbms.org, возможно, покажетс€ очевидной, тривиальной и немного путанной специалистам в области рел€ционных баз данных. Ќо она и не адресована подобным специалистам. ќсновна€ иде€ состоит в том, что ссылочной целостностью нельз€ пренебрегать и в области проектировани€ баз данных (не об€зательно рел€ционных), и в области моделировани€ и разработки приложений (не об€зательно приложений баз данных). ќпыт автора показывает, что, несмотр€ на очевидную фундаментальность пон€ти€ ссылочной целостности, больша€ часть разработчиков программного обеспечени€ (в том числе, и приложений баз данных) совершенно не заботитс€ о ссылочной целостности своих данных, что приводит к плачевным последстви€м.

1. ¬ведение

—сылочна€ целостность Ц это ограничение базы данных, гарантирующее, что ссылки между данными €вл€ютс€ действительно правомерными и неповрежденными. —сылочна€ целостность €вл€етс€ фундаментальным принципом теории баз данных и проистекает из той идеи, что база данных должна не только сохран€ть данные, но и активно содействовать обеспечению их качества. ¬от несколько дополнительных определений, найденных в Web:

  • Ђ—сылочна€ целостность в рел€ционной базе данных Ц это согласованность между св€занными таблицами. —сылочна€ целостность обычно поддерживаетс€ путем комбинировани€ первичного ключа и внешнего ключа. ƒл€ соблюдени€ ссылочной целостности требуетс€, чтобы любое поле в таблице, объ€вленное внешним ключом, могло содержать только значени€ из пол€ первичного ключа родительской таблицы Еї
  • Ђ[—сылочна€ целостность Ц это] свойство, обеспечиваемое рел€ционными системами управлени€ базами данных (–—”Ѕƒ), которое предотвращает ввод несогласованных данных пользовател€ми или приложени€ми. ¬ большинстве –—”Ѕƒ имеютс€ различные правила ссылочной целостности, которые можно применить при создании св€зи между двум€ таблицами.ї
  • Ђ[—сылочна€ целостность Ц это] предохранительное устройство системы управлени€ базами данных, гарантирующее, что каждый внешний ключ соответствует первичному ключу. Ќапример, номера заказчиков €вл€ютс€ первичными ключами в файле заказчиков и внешними ключами в файле заказов. ѕри удалении записи заказчика должны быть удалены соответствующие записи заказов; в противном случае они останутс€ без исходной св€зи. ≈сли —”Ѕƒ не провер€ет этого, соответствующий механизм должен программироватьс€ в приложении.ї

ѕоддержка ссылочной целостности в базе данных обеспечивает много преимуществ.

  • ”лучшенное качество данных. ќчевидным преимуществом €вл€етс€ поддержка качества данных, хранимых в базе данных. ќшибки могут по-прежнему существовать, но, по крайней мере, ссылки будут подлинными и неповрежденными.
  • ”быстрение разработки. —сылочна€ целостность объ€вл€етс€. Ёто гораздо продуктивнее (на один или два пор€дка), чем написание специального программного кода.
  • ћеньшее число ошибок. ќбъ€влени€ ссылочной целостности €вл€ютс€ гораздо более лаконичными, чем эквивалентный программный код. ѕо существу, такие объ€влени€ привод€т к повторному использованию проверенного и оттестированного кода общего назначени€ в сервере баз данных, а не к новой реализации одной и той же логики от случа€ к случаю.
  • —огласованность между приложени€ми. —сылочна€ целостность обеспечивает качество данных дл€ нескольких прикладных программ, которые могут обращатьс€ к базе данных.

«аметим, что определени€, вз€тые из Web, выражаютс€ в терминах рел€ционных баз данных. ќднако принципы ссылочной целостности примен€ютс€ в более широком контексте. —сылочна€ целостность применима как к рел€ционным, так и к объектно-ориентированным (ќќ) базам данных, а также к €зыкам программировани€ и моделированию.

2. —сылочна€ целостность и –—”Ѕƒ

—интаксис SQL дл€ определени€ ссылочной целостности выгл€дит, по существу, подобно следующему. —лова из прописных буква обозначают ключевые слова.  вадратные скобки выдел€ют необ€зательные параметры. —толбцы внешнего ключа наход€тс€ в таблице table1, а столбцы первичного ключа (или другой комбинации столбцов со свойством уникальности значений) Ц в таблице table2.

ALTER TABLE tableName1
ADD CONSTRAINT constraintName
FOREIGN KEY (columnList)
REFERENCES tableName2 [(columnList)]
[onDeleteAction] [onUpdateAction];

¬ SQL внешний ключ может ссылатьс€ на любую комбинацию столбцов со свойством уникальности в таблице, на которую ведет ссылка. ¬ стандарте SQL обеспечиваютс€ следующие действи€ по поддержанию ссылочной целостности при удалени€х строк.

  1. Cascade. ”даление записи может привести к удалению записей с соответствующим значением внешнего ключа. Ќапример, можно захотеть, чтобы при удалении записи о компании удал€лись все адреса компании.
  2. No action. ¬ качестве альтернативы можно запретить удаление записи, если имеютс€ зависимые записи с соответствующим значением внешнего ключа. Ќапример, если вы продали некоторой компании товары, то вы можете захотеть предотвратить удаление записи об этой компании.
  3. Set null. ”даление записи может приводить к установке в соответствующие внешние ключи неопределенного значени€. Ќапример, при замене самолета дл€ выполнени€ рейса может понадобитьс€ анулировать некоторые назначени€ посадочных мест. (“аким пассажирам придетс€ запросить другие посадочные места.)
  4. Set default. ћожно потребовать, чтобы при удалении записи во внешний ключ устанавливалось значение по умолчанию, а не неопределенное значение.

¬ стандарте SQL эти действи€ обеспечиваютс€ и при модификации записей. ѕоддержка стандарта различаетс€ в разных продуктах.

  1. SQL Server. ¬ SQL Server 2000 внешний ключ может ссылатьс€ на первичный ключ или на комбинацию столбцов со свойством уникальности. Ќе поддерживаютс€ опции set null и set default. ќднако опции cascade и no action поддерживаютс€ полностью, и на практике этого часто оказываетс€ достаточно. «аметим также, что синтаксис дл€ no action отличаетс€ от стандарта SQL. ¬ SQL Server при отсутствии €вного указани€ ссылочного действи€ подразумеваетс€ no action.
  2. Oracle. ¬ Oracle 10g внешний ключ также может ссылатьс€ на первичный ключ или на комбинацию столбцов со свойством уникальности. ¬ Oracle поддерживаютс€ ссылочные действи€ при удалении записей, но отсутствуют действи€ при модификации. ƒл€ действий при удалении поддерживаютс€ опции cascade, no action и set null. ѕоддержка опции set default отсутствует.  ак и в SQL Server, синтаксис no action отличаетс€ от стандарта SQL. ѕри отсутствии €вного указани€ ссылочного действи€ подразумеваетс€ no action.
  3. MySQL. ѕоддержка ссылочной целостности по€вилась в MySQL 5.0 (при использовании InnoDB). ¬ MySQL стандарт SQL поддерживаетс€ в более полном объеме, чем в SQL Server и Oracle. ѕоддерживаютс€ варианты on delete и on update со всеми четырьм€ ссылочными действи€. ¬ MySQL требуетс€, чтобы дл€ внешнего ключа и ключа, на который ведет ссылка, поддерживались индексы базы данных Ц это хороший обычай, которому мы советуем следовать.* —толбцы, на которые ведет ссылка, могут быть первичным ключом или комбинацией столбцов со свойством уникальности.
  4. MS-Access. ¬ MS-Access команды SQL дл€ определени€ ссылочной целостности поддерживаютс€ только частично, но средство графического св€зывани€ €вл€етс€ более сильным. — помощью графического интерфейса можно определить ссылочную целостность, а также ссылочные действи€ cascade и no action.

3. —сылочна€ целостность и ќќ—”Ѕƒ

ѕон€тие ссылочной целостности применимо и к ќќ—”Ѕƒ. ћежду объектами имеютс€ св€зи, которые привод€т к их взаимной зависимости, и поддержку этих зависимостей не следует возлагать на код приложени€.

—сылочна€ целостность поддерживаетс€ в некоторых ќќ—”Ѕƒ . Ќапример, в ObjectStore ссылочна€ целостность реализуетс€ с использованием сдвоенных указателей между парой объектов, которые поддерживаютс€ —”Ѕƒ во взаимно согласованном состо€нии . “аким образом, в ObjectStore сохран€етс€ стиль €зыков программировани€ Ц указатель представл€ет собой всего лишь еще одну переменную экземпл€ра, скрытую внутри объекта. ќднако в системе соблюдаетс€ и смысл ссылочной целостности путем поддержки зависимостей между объектами и предотвращени€ Ђвис€щихї ссылок.

Ёти пары взаимно согласованных указателей называютс€ в ObjectStore инверсными партнерами (inverse members). ¬ ObjectStore поддерживаетс€ целостность инверсных партнеров; при изменении одного партнера ObjectStore прозрачным образом измен€ет другого партнера. јналогично, при удалении объекта ObjectStore автоматически обновл€ет всех инверсных партнеров, чтобы предотвратить по€вление Ђвис€щихї ссылок.

4. —сылочна€ целостность и €зыки

¬ €зыках программировани€ (с небольшим числом исключений) ссылочной целосности не придаетс€ значение. ¬место этого в них делаетс€ упор на инкапсул€ции, на том, что детали реализации следует скрывать в классе. ѕроблема состоит в том, что инкапсул€ци€ часто подрываетс€ наличием зависимостей между объектами. «начение оказываетс€ недостаточным дл€ обеспечени€ ссылки на объект.

Ќапример, объект «ан€тость (Employment) ссылаетс€ на объекты „еловек (Person) и  омпани€ (Company). Ќевозможно иметь дело с изолированной «ан€тостью. ≈сли удал€етс€ „еловек, то должны быть удалены и св€занные с ним объекты «ан€тость, потому что иначе образуютс€ Ђвис€щиеї ссылки на объект. Ќельз€ создать объект «ан€тость без объектов „еловек и  омпани€.

 ак демонстриуетс€ в , в €зыке программировани€ можно поддерживать ссылочную целостность. ¬ GE R&D (General Electric Corporate Research and Development) –эмбо (Rumbaugh) реализовал объектно-ориентиованный €зык программировани€ DSM с семантической поддержкой зависимостей (называемых в статье отношени€ми) между объектами.

5. —сылочна€ целостность и UML

ѕри использовании UML за счет семантической поддержки ассоциаций также возникает ссылочна€ целостность. јссоциаци€ (association) Ц это описание группы соединений (link) с общей структурой и семантикой. —оединение Ц это физическа€ или концептуальна€ св€зь между объектами.

ѕри конструировании моделей классов UML важно €вно представить зависимости между объектами в виде ассоциаций и не скрывать их в виде атрибутов. “радиционные €зыки программировани€ вынуждают понижать статус ассоциаций, но они должны быть пон€тны, по крайней мере, на уровне мышлени€. “огда можно придумать наилучший обходной путь в пределах возможностей €зыка.

6. »спользуетс€ ли ссылочна€ целостность?

—сылочна€ целостность €вл€етс€ выдающимс€ аспектом теории рел€ционных баз данных. Ќо действительно ли она используетс€ на практике? ћы можем ответить на этот вопрос, поскольку на основе своих исследований в области обратной инженерии обладаем данными о 50 существующих базах данных.

Ќа практике ссылочна€ целостность обеспечиваетс€ редко. Ќасколько нам известно, она не поддерживаетс€ в большинстве программ, поскольку в €зыках программировани€ отсутствует соответствующий механизм, что затрудн€ет поддержку. ќднако проблема €вл€етс€ более глубокой. ¬ большинстве реализаций рел€ционных —”Ѕƒ также отсутствует ссылочна€ целостность. ƒаже в тех случа€х, когда в –—”Ѕƒ поддерживаетс€ механизм ссылочной целостности, многие разработчики его не используют. Ќаши исследовани€ в области обратной инженерии показали, что 90% разработчиков рел€ционных баз данных не используют ссылочную целостность в своих приложени€х.

ѕоследстви€ прискорбны, и мы видем их повседневно Ц программное обеспечение содержит ошибки, работает медленно, его трудно расшир€ть. ќдним из характерных примеров может служить стандарт LDAP. ¬ LDAP не включены средства подержки ссылочной целостности, и это приводит к печальным последстви€м.

7. «аключение

ќбычно термин Ђссылочна€ целостностьї ассоциируетс€ только с рел€ционными —”Ѕƒ. Ќо в действительности этот термин обладает более широким смыслом и относитс€ в базам данных вообще, а также к €зыкам программировани€ и моделированию. —мысл Ђссылочной целостностиї, происход€щий из рел€ционных —”Ѕƒ, относитс€ к механизму реализации. ќднако более глубокий смысл св€зан с зависимост€ми между объектами. ¬ этом расширенном смысле ссылочна€ целостность €вл€етс€ существенным аспектом нашего осмыслени€ проблем и представлени€ их на основе моделей. ѕоэтому ссылочную целостность необходимо учитывать вне зависимости от реализационной платформы Ц –—”Ѕƒ, ќќ—”Ѕƒ или €зыка программировани€.

»сточник: compdoc.ru

-
–ел€ционна€ модель данных дл€ больших совместно используемых банков данных

–ел€ционна€ модель данных дл€ больших совместно используемых банков данных

—одержание

1. –ел€ционна€ модель и нормальна€ форма
1.1. ¬ведение
1.2. «ависимости данных в существующих системах
1.3. –ел€ционное представление данных
1.4. Ќормальна€ форма
1.5. Ќекоторые лингвистические аспекты
1.6. ¬ыразимые, именованные и хранимые отношени€
2. »збыточность и согласованность
2.1. ќперации над отношени€ми.
2.2. »збыточность
2.3. —огласованность
2.4. «аключение
Ћитература

Ѕудущие пользователи больших банков данных должны быть освобождены от необходимости знать организацию данных в машине (внутреннее представление). Ќельз€ считать удовлетворительной какую-либо службу, если она предоставл€ет такую информацию. »зменение внутреннего представлени€ данных и даже изменение некоторых аспектов их внешнего представлени€ не должны вли€ть на работу пользователей за их терминалами и на выполнение большинства прикладных программ. »зменени€ представлени€ данных часто требуютс€ по причине изменени€ потока запросов, операций обновлени€ и отчетов, естественного увеличени€ числа типов хранимой информации.

—уществующие недедуктивные системы форматированных данных предоставл€ют пользовател€м файлы с древовидной структурой или немного более общие сетевые модели данных. ¬ разд. 1 обсуждаютс€ недостатки таких моделей. ¬вод€тс€ модель, основанна€ на n-арных отношени€х, нормальна€ форма отношений базы данных и универсальный подъ€зык данных. ¬ разд. 2 обсуждаютс€ некоторые операции над отношени€ми (отличные от операций логического вывода), а затем эти операции примен€ютс€ к проблемам избыточности и согласованности пользовательской модели.

 лючевые слова и фразы:
банк данных, база данных, структура данных, организаци€ данных, иерархии данных, сети данных, отношени€, порождаемость, избыточность, согласованность, композици€, соединение, €зык выборки, исчисление предикатов, безопасность, целостность данных.

1. –ел€ционна€ модель и нормальна€ форма

1.1. ¬ведение

Ёта стать€ посв€щаетс€ применению элементарной теории отношений к системам, которые обеспечивают совместный доступ к большим банкам форматированных данных. «а исключением статьи „айлдса (Childs) [1], основной областью применени€ отношений к системам данных €вл€ютс€ дедуктивные системы ответов на вопросы. ¬ статье Ћивейна (Levein) и ћарона (Maron) [2] привод€тс€ многочисленные ссылки на работы в этой области.

¬ отличие от этого, в данной статье рассматриваютс€ проблемы независимости данных, т.е. независимости прикладных программ и интерактивных действий от увеличени€ числа типов данных и изменений представлени€ данных, а также проблемы некоторых видов несогласованности данных, которые, видимо, вызывают наибольшее беспокойство даже в недедуктивных системах.

–ел€ционное представление (или модель) данных, описываемое в разд. 1, обладает некоторыми преимуществами по отношению к графовой, или сетевой модели [3,4], котора€ в насто€щее врем€ наиболее распространена среди систем, не основанных на логике. –ел€ционна€ модель предоставл€ет средства описани€ данных на основе только их естественной структуры, т.е. без потребности введени€ какой-либо дополнительной структуры дл€ целей машинного представлени€. —оответственно, эта модель обеспечивает основу €зыка данных высокого уровн€, который поддерживает максимальную независимость программ, с одной стороны, и машинного представлени€ и организации данных с другой.

ѕреимуществом рел€ционного представлени€ €вл€етс€ также то, что оно образует надежную основу дл€ решени€ проблем порождаемости, избыточности и согласованности отношений; эти проблемы обсуждаютс€ в разд. 2. — другой стороны, сетева€ модель привела к возникновению р€да недоразумений, не последним из которых €вл€етс€ ошибочное образование св€зей при образовании отношений (см. замечани€ в разд. 2 по поводу "ловушки св€зей").

Ќаконец, рел€ционное представление дает возможность более четко оценить область действи€ и логические ограничени€ существующих систем форматированных данных, а также сравнить достоинства (с логической точки зрени€) разных представлений данных в одной системе. —оответствующие примеры привод€тс€ в разных част€х этой статьи. –еализаци€ систем, поддерживающих рел€ционную модель, не обсуждаетс€.

1.2. «ависимости данных в существующих системах

ќбеспечение таблиц описани€ данных в разрабатываемых сегодн€ системах €вл€етс€ существенным продвижением на пути к независимости данных [5,6,7]. Ќаличие таких таблиц облегчает изменени€ некоторых характеристик представлени€ данных, хранимых в банках данных. ќднако набор характеристик представлени€ данных, которые могут быть изменены без нанесени€ логического ущерба некоторым прикладным программам, продолжает оставатьс€ ограниченным. ƒалее, модель данных, с которыми работают пользователи, по-прежнему загромождаетс€ характеристиками представлени€; в особенности это касаетс€ представлений коллекций данных (а не одиночных элементов данных). “рем€ основными видами зависимости данных, которые все еще требуетс€ устранить, €вл€ютс€ зависимость пор€дка, зависимость индексации и зависимость путей доступа. ¬ некоторых системах эти зависимости четко не отделены одна от другой.

1.2.1. «ависимость пор€дка. Ёлементы данных в банке данных могут хранитьс€ разными способами, некоторые из которых не предполагают наличи€ какого-либо пор€дка, некоторые допускают участие каждого элемента только в одном пор€дке, а некоторые Ц в нескольких пор€дках. ќбратим внимание на те существующие системы, в которых требуетс€ или хот€ бы допускаетс€ хранение элементов данных, по крайней мере, в одном полном пор€дке, тесно св€занном с зависимым от аппаратуры пор€дком адресов. Ќапример, записи в файле, описывающем детали, могут хранитьс€ в пор€дке убывани€ серийных номеров. ¬ таких системах обычно допускаетс€, чтобы прикладные программы основывались на предположении о том, что пор€док представлени€ записей идентичен пор€дку их хранени€ (или €вл€етс€ его частью). Ёти прикладные программы, использующие свойства упор€доченности файла, скорее всего не смогут правильно работать, если по какой-то причине потребуетс€ изменить этот пор€док. јналогичные замечани€ остаютс€ в силе дл€ случа€, когда пор€док хранени€ реализуетс€ посредством указателей.

Ќет необходимости выдел€ть в качестве примера какую-либо одну систему, поскольку во всех хорошо известных информационных системах, имеющихс€ на сегодн€шнем рынке, не проводитс€ четкое разделение пор€дка представлени€ и пор€дка хранени€. ƒл€ обеспечени€ независимости такого рода требуетс€ решить существенные реализационные проблемы.

1.2.2. «ависимость индексации. ¬ контексте форматированных данных индекс обычно полагаетс€ компонентом представлени€ данных, ориентированным исключительно на увеличение эффективности. Ќаличие индексов ускор€ет выполнение запросов и операций обновлени€, но в то же врем€ замедл€ет выполнение операций вставки и удалени€. — точки зрени€ информативности индекс €вл€етс€ избыточным компонентом представлени€ данных. ≈сли в системе используютс€ индексы, и она должна хорошо справл€тьс€ с изменени€ми активности среды по отношению к банку данных, то, веро€тно, потребуетс€ возможность врем€ от времени создавать и уничтожать индексы. ¬озникает вопрос: могут ли при этом остатьс€ неизменными прикладные программы и интерактивна€ де€тельность?

¬ современных системах форматированных данных примен€ютс€ разнообразные подходы к индексации. ¬ TDMS [7] обеспечиваетс€ об€зательна€ индексаци€ по всем атрибутам. ¬ текущей версии IMS [5] пользователю предоставл€етс€ выбор дл€ каждого файла: между полным отсутствием индексации (иерархическа€ последовательна€ организаци€) и индексацией только по первичному ключу (иерархическа€ индексно-последовательна€ организаци€). Ќи в одном из этих случаев логика пользовательского представлени€ не зависит от об€зательно поддерживаемых индексов. ќднако в IDS [8] проектировщикам файлов предоставл€етс€ возможность выбора индексных атрибутов и добавлени€ индексов в структуру файла с использованием средств дополнительных цепочек. ѕрикладные программы, в которых дл€ повышени€ эффективности используютс€ эти индексные цепочки, должны ссылатьс€ на них по именам. “акие программы не смогут работать правильно, если эти цепочки будут впоследствии удалены.

1.2.3. «ависимость путей доступа. ћногие существующие системы форматированных данных предоставл€ют пользователю файлы с древовидной организацией или немного более общие сетевые модели данных. Ќа прикладные программы, предназначенные дл€ работы с этими системами, логически вли€ют изменени€ структуры деревьев и сетей. ѕриведем простой пример.

ѕредположим, что банк данных содержит информацию о детал€х и проектах. ƒл€ каждой детали хранитс€ номер детали, название детали, описание детали, количество используемых деталей этого типа и количество заказанных деталей. ƒл€ каждого проекта хранитс€ номер проекта, название проекта и описание проекта. ≈сли в проекте используетс€ некоторый тип детали, регистрируетс€ и количество деталей этого типа, предназначенных дл€ данного проекта. ѕредположим, что система требует, чтобы пользователь или проектировщик файлов объ€вл€л или определ€л данные в терминах древовидных структур. “огда дл€ представлени€ упом€нутой выше информации годитс€ люба€ из представленных ниже иерархических структур (см. структуры 1-5).

 
—труктура 1. ѕроекты подчинены ƒетал€м

‘айл

—егмент

ѕол€

F

ƒ≈“јЋ№

номер детали



наименование детали



описание детали



имеющеес€ количество



заказанное количество


ѕ–ќ≈ “

номер проекта



наименование проекта



описание проекта



подтвержденное количество

 
—труктура 2. ƒетали подчинены ѕроектам

‘айл

—егмент

ѕол€

F

ѕ–ќ≈ “

номер проекта



наименование проекта



описание проекта

ƒ≈“јЋ№

номер детали



наименование детали



описание детали



имеющеес€ количество



заказанное количество



подтвержденное количество

 
—труктура 3. ƒетали и ѕроекты наравне, —в€зь назначени€ деталей проектам подчинена ѕроектам

‘айл

—егмент

ѕол€

F

ƒ≈“јЋ№

номер детали



наименование детали



описание детали



имеющеес€ количество



заказанное количество

G

ѕ–ќ≈ “

номер проекта



наименование проекта



описание проекта


ƒ≈“јЋ№

номер детали



подтвержденное количество

 
—труктура 4. ƒетали и ѕроекты наравне, —в€зь назначени€ деталей проектам подчинена ƒетал€м

‘айл

—егмент

ѕол€

F

ƒ≈“јЋ№

номер детали



наименование детали



описание детали



имеющеес€ количество



заказанное количество


ѕ–ќ≈ “

номер проекта



подтвержденное количество

G

ѕ–ќ≈ “

номер проекта



наименование проекта



описание проекта

 
—труктура 5. ƒетали, ѕроекты и —в€зь назначени€ деталей проектам наравне

‘айл

—егмент

ѕол€

F

ƒ≈“јЋ№

номер детали



наименование детали



описание детали



имеющеес€ количество



заказанное количество

G

ѕ–ќ≈ “

номер проекта



наименование проекта



описание проекта

H

ѕќƒ“¬≈–∆ƒ≈Ќ»≈

номер детали



номер проекта



подтвержденное количество

“еперь рассмотрим задачу выборки номера детали, названи€ детали и количества деталей этого типа дл€ каждой детали, используемой в проекте с названием "альфа". —ледующие наблюдени€ могут быть сделаны независимо от того, кака€ конкретна€ информационна€ система с древовидной организацией информации выбираетс€ дл€ решени€ этой задачи. ≈сли дл€ этого разрабатываетс€ программа P, ориентированна€ на использование одной из приведенных выше структур (т.е. P не определ€ет, какова реальна€ структура представлени€ данных), то при любом выборе P не сможет работать, по меньшей мере, с трем€ потенциально возможными структурами. Ѕолее точно, если P следует структуре 5, то ей не удастс€ работать со всеми другими структурами; если PP следует структуре 3 или 4, то ей, по меньшей мере, не удастс€ работать со структурами 1,2 и 5; если P следует структуре 1 или 2, ей, как минимум , не удастс€ работать со структурами 3, 4 и 5. ¬ каждом случае причина проста. ≈сли отсутствуют проверки дл€ определени€ реально заданной структуры, то работа P заканчитс€ неудачей по причине попытки перехода по ссылке к несуществующему файлу (в доступных сегодн€ системах это трактуетс€ как ошибка) или из-за отсутстви€ перехода по ссылке к файлу, содержащему нужную информацию. „итателю, который в этом сомневаетс€, рекомендуетс€ написать пробные программы дл€ решени€ этой простой задачи.

ѕоскольку в общем случае непрактично создавать прикладные программы, которые провер€ют все древовидные структуризации, допускаемые системой, эти программы перестают работать после выполнени€ необходимых изменений структуры.

—истемы, которые предоставл€ют пользовател€м сетевую модель данных, порождают аналогичные трудности. » в случае деревьев, и в случае сетей пользователь (или его программа) должен обеспечить набор путей доступа к данным. Ќеважно, наход€тс€ ли эти пути в точном соответствии с определ€емыми ссылками пут€ми в хранимом представлении (в IDS это соответствие €вл€етс€ предельно простым, в TDMS Ц совсем наоборот). ¬ результате, независимо от конкретного вида хранимого представлени€, интерактивна€ де€тельность и программы станов€тс€ зависимыми от существовани€ пользовательских путей доступа.

ќдно из решений состоит в следовании той политике, что определенный пользователем путь доступа нельз€ вывести из употреблени€ до тех пор, пока существуют программы, использующие этот путь доступа. “ака€ политика непрактична, поскольку число путей доступа в модели, общей дл€ сообщества пользователей банка данных, в конце концов станет чрезмерно велико.

1.3. –ел€ционное представление данных

“ермин отношение используетс€ здесь в его общеприн€том математическом смысле. ƒл€ заданных множеств S1, S2, ..., Sn (не об€зательно различных) R €вл€етс€ отношением на этих n множествах, если представл€ет собой множество кортежей степени n, у каждого из которых первый элемент вз€т из множества S1, второй Ц из множества S2 и т.д.1) ћы будем называть Sj j-тым доменом R. √овор€т, что такое отношение R имеет степень n. ќтношени€ степени 1 часто называют унарными, степени 2 Ц бинарными, степени 3 Ц тернарными и степени n Ц n-арными.

ƒл€ нагл€дности мы будем часто использовать представление отношений в виде массивов, но нужно помнить, что это конкретное представление не €вл€етс€ существенной частью излагаемого рел€ционного представлени€. ћассив, представл€ющий n-арное отношение R, обладает следующими свойствами:

  1.  ажда€ строка представл€ет кортеж степени n.
  2. ѕор€док строк не €вл€етс€ существенным.
  3. ¬се строки различны.
  4. ѕор€док столбцов €вл€етс€ существенным Ц он соответствует пор€дку S1, S2,..., Sn доменов, на которых определ€етс€ R (однако обратите внимание на приводимые ниже замечани€ по поводу отношений с упор€доченными и неупор€доченными доменами).
  5. «начимость каждого столбца частично выражаетс€ посредством его пометки именем соответствующего домена.

¬ примере на рис.1 показано отношение степени 4 поставка. ¬ этом отношении отражаютс€ выполн€емые поставки деталей от указанных поставщиков дл€ указанных проектов в указанных количествах.

поставка

(поставщик

деталь

проект

количество)


1

2

5

17


1

3

5

23


2

3

7

9


2

7

5

4


4

1

1

12

–исунок 1. ќтношение степени 4

ћожно спросить: если столбцы помечены именами соответствующих доменов, зачем нужна упор€доченность столбцов?  ак показывает рис.2, дл€ двух столбцов могут иметьс€ одинаковые заголовки (означающие одинаковые домены), но смысл этих столбцов может быть различным. ѕоказанное отношение называетс€ компонент. ¬ этом тернарном отношении два первых домена называютс€ деталь, а третий Ц количество. —мысл отношени€ компонент (x, y, z) состоит в том, что деталь x €вл€етс€ непосредственным компонентом (или составной частью) детали y, и дл€ сборки одного экземпл€ра детали y требуетс€ z экземпл€ров детали x. Ёто отношение играет критическую роль в проблеме разборки деталей.

компонент

(деталь

деталь

количество)


1

5

9


2

5

7


3

5

2


2

6

12


3

6

3


4

7

1


6

7

1

–исунок 2.ќтношение с двум€ одинаковыми доменами

ѕримечательным фактом €вл€етс€ то, что некоторые современные системы (главным образом, те, которые основываютс€ на файлах с древовидной структурой) не в состо€нии обеспечить представление данных дл€ отношений, которые имеют два или более одинаковых домена. ѕримером такой системы €вл€етс€ текуща€ верси€ IMS/360 [5].

 о всем данным, наход€щимс€ в банке данных, можно относитьс€ как к коллекции измен€ющихс€ во времени отношений. Ёти отношени€ обладают разными степен€ми. ¬о врем€ существовани€ каждого n-арного отношени€ в него могут вставл€тьс€ дополнительные кортежи степени n, удал€тьс€ существующие кортежи и измен€тьс€ компоненты существующих в нем кортежей.

ќднако во многих коммерческих, правительственных и научных банках данных степени некоторых отношений бывают достаточно велики (степень 30 не €вл€етс€ редкостью). ќбычно не следует обремен€ть пользователей потребностью помнить пор€док доменов в любом отношении (например, пор€док поставщик-деталь-количество в отношении поставка). ѕоэтому мы предлагаем, чтобы пользователи имели дело не с отношени€ми с упор€доченными доменами, а со св€з€ми, которые €вл€ютс€ двойниками отношений с неупор€доченными доменами.2) ƒл€ достижени€ этого домены должны быть однозначно идентифицируемы, по крайней мере, в пределах любого данного отношени€, без использовани€ их позиции. “аким образом, там, где существует два или более одинаковых домена, мы требуем, чтобы в каждом случае имена доменов были уточнены отдельным именем роли, служащим дл€ указани€ роли, которую этот домен играет в данном отношении.

Ќапример, в отношении компонент, приведенном на рис. 2, первый домен деталь может быть обозначен именем роли суб и второй - именем супер, чтобы пользователи могли работать со св€зью компонент и ее доменами Ц суб.деталь, супер.деталь, количество, не основыва€сь на каком-либо пор€дке этих доменов.

√овор€ в целом, мы предлагаем, чтобы пользователи взаимодействовали с рел€ционной моделью данных, состо€щей из измен€ющихс€ во времени св€зей (а не с отношени€ми).  аждый пользователь не должен знать ничего больше про св€зь, кроме ее имени и имен ее доменов (с указанными в случае необходимости именами ролей)3) » эта информаци€ могла бы предоставл€тьс€ системой в меню-ориентированном стиле (с соблюдением ограничений безопасности и конфиденциальности) по запросу пользовател€.

 ак правило, существует много альтернативных способов применени€ рел€ционной модели в банках данных. ƒл€ обсуждени€ предпочтительного способа (или нормальной формы) мы должны вначале ввести несколько дополнительных пон€тий (активный домен, первичный ключ, внешний ключ, непростой домен) и установить некоторые св€зи с терминологией, используемой в насто€щее врем€ при программировании информационных систем. ƒалее в этой статье мы не будем заботитьс€ о различии между отношени€ми и св€з€ми за исключением тех случаев, когда выгодно €вно подчеркнуть это различие.

–ассмотрим пример банка данных, включающего отношени€, которые содержат информацию о детал€х, проектах и поставщиках. ќдно отношение, называемое деталь, определено на следующих (и, возможно, на некоторых других) доменах:

  1. номер детали;
  2. наименование детали;
  3. цвет детали;
  4. вес детали;
  5. количество имеющихс€ деталей;
  6. количество заказанных деталей.

 аждый из этих доменов €вл€етс€, по существу, набором значений, некоторые или все из которых могут содержатьс€ в банке данных в любой момент времени. ≈сли еще можно предположить, что в некоторый момент представлены все цвета деталей, сделать такое предположение о всех возможных весах, наименовани€х и номерах деталей не представл€етс€ возможным. ћы будем называть множество хранимых в некоторый момент времени значений активным доменом в этот момент времени.

 ак правило, один домен (или комбинаци€ доменов) данного отношени€ содержит значени€, позвол€ющие однозначно идентифицировать каждый элемент (n-кортеж) этого отношени€. “акой домен (или комбинаци€ доменов) называетс€ первичным ключом. ¬ приведенном примере первичным ключом мог бы быть номер детали, в то врем€ как цвет детали Ц нет. ѕервичный ключ неизбыточен, если он либо €вл€етс€ простым доменом (не комбинацией), либо представл€ет собой такую комбинацию, что ни один из вход€щих в нее доменов не €вл€етс€ лишним при однозначной идентификации каждого элемента. ќтношение может обладать более чем одним неизбыточным первичным ключом. ¬ случае, когда отношение содержит два или более неизбыточных первичных ключа, произвольно выбираетс€ один из них и называетс€ѕервичным  лючом этого отношени€.

ќбщее требование дл€ элементов отношени€ Ц обеспечение взаимосв€зи с другими элементами данного отношени€ или с элементами другого отношени€.  лючи обеспечивают средства пользовательского уровн€ (но не только эти средства), дл€ выражени€ таких взаимосв€зей. ћы будем называть домен (или комбинацию доменов) отношени€ R внешним ключом, если он не €вл€етс€ ѕервичным  лючом R, но его элементы Ц это значени€ ѕервичного  люча некоторого отношени€ S (возможность идентичности R и S не исключаетс€). ¬ отношении поставка, приведенном на рис.1, комбинаци€ поставщик, деталь, проект - ѕервичный  люч, в то врем€ как каждый из этих доменов сам по себе €вл€етс€ внешним ключом.

–анее существовала строга€ тенденци€ трактовать данные в банке данных как состо€щие из двух частей Ц одна часть состоит из описаний сущностей (например, описани€ поставщиков), а друга€ часть состоит из отношений между различными сущност€ми или типами сущностей (например, отношение поставка). “акое различие трудно сохран€ть, если отношение может содержать внешние ключи дл€ какого-либо другого отношени€. ¬ пользовательской рел€ционной модели отсутствуют преимущества от проведени€ такого разделени€ (тем не менее, такие преимущества могут существовать при применении рел€ционных концепций к машинному представлению пользовательского набора св€зей).

“аким образом, мы обсудили примеры отношений, определенных над простыми доменами Ц доменами, элементы которых €вл€ютс€ атомарными (не поддающимис€ декомпозиции) значени€ми. ¬ рамках рел€ционного подхода могут обсуждатьс€ и неатомарные значени€. ћы имеем в виду то, что некоторые домены могут в качестве элементов содержать отношени€. Ёти отношени€ могут, в свою очередь, быть определены на непростых доменах и т.д. Ќапример, одним из доменов, на которых определено отношение служащий, мог бы быть домен истори€ зарплаты. Ёлемент домена истори€ зарплаты Ц бинарное отношение, определенное на домене дата и домене зарплата. ƒомен истори€ зарплаты €вл€етс€ множеством всех таких бинарных отношений. ¬ любой момент времени в банке данных существует столько же экземпл€ров отношени€ истори€ зарплаты, сколько и работников. Ќапротив, дл€ отношение служащий имеетс€ только один экземпл€р.

“ермины атрибут и повтор€юща€с€ группа в современной терминологии баз данных Ц это приблизительные аналоги простого и непростого домена соответственно. ќсновна€ путаница в существующей терминологии проистекает из отсутстви€ различи€ между типом и экземпл€ром (например, "запись") и между компонентами пользовательской модели данных, с одной стороны, и ее машинным представлением, с другой (оп€ть же "запись" в качестве примера).

1.4. Ќормальна€ форма

ќтношение, все домены которого €вл€ютс€ простыми, может быть представлено двухмерным массивом указанного выше вида с однородными столбцами. ƒл€ отношени€ с одним или более непростыми доменами требуютс€ несколько более сложные структуры данных. ѕо этой причине (остальные будут приведены ниже) возможность устранени€ непростых доменов кажетс€ сто€щей дополнительного исследовани€.4) ¬ действительности, существует очень проста€ процедура такого устранени€, которую мы будем называть нормализацией.

–ассмотрим, например, набор отношений, приведенный на рис.3(а). »стори€ работы и дети Ц непростые домены отношени€ служащий. »стори€ зарплаты Ц непростой домен отношени€ истори€ работы. Ќа дереве на рис.3(а) показаны именно эти взаимосв€зи указанных непростых доменов.

служащий (номер_служащего, им€, дата_рождени€, истори€_работы, дети)
истори€_работы (дата_приема_на_работу, название, истори€_зарплаты)
истори€_зарплаты (дата_назначени€_зарплаты,зарплата)
дети (им€_ребенка, год_рождени€)

–исунок 3(a). Ќенормализованное множество

служащий' (номер_служащего, им€, дата_рождени€)
истори€_работы' (номер_служащего, дата_приема_на_работу, название)
истори€_зарплаты' (номер_служащего, дата_приема_на_работу, дата_назначени€_зарплаты, зарплата)
дети' (номер_служащего, им€_ребенка, год_рождени€)

–исунок 3(б). Ќормализованное множество

Ќормализаци€ выполн€етс€ следующим образом. Ќачина€ с отношени€, наход€щегос€ наверху дерева, вз€ть его ѕервичный  люч, и каждое непосредственно подчиненное отношение расширить путем вставки домена или комбинации доменов этого ѕервичного  люча. ѕервичный  люч каждого расширенного таким образом отношени€ состоит из ѕервичного  люча, который был у этого отношени€ до расширени€ и добавленного ѕервичного  люча родительского отношени€. ѕосле этого из родительского отношени€ вычеркиваютс€ все непростые домены, удал€етс€ верхний узел дерева, и эта же процедура повтор€етс€ дл€ каждого из оставшихс€ поддеревьев.

–езультатом нормализации набора отношений, приведенного на рис.3(а), €вл€етс€ набор отношений, показанный на рис.3(б). ѕервичный  люч каждого отношени€ выделен курсивом, чтобы показать, как такие ключи расшир€ютс€ в процессе нормализации.

„тобы можно было применить описанную нормализации, ненормализованный набор отношений должен удовлетвор€ть следующим услови€м:

  1. √раф взаимосв€зей непростых доменов должен €вл€тьс€ набором деревьев.
  2. Ќи один первичный ключ не должен включает в себ€ непростые домены.

јвтор не знает приложений, в которых потребовалось бы ослабление этих условий. ¬озможно введение операций дальнейшей нормализации. ¬ данной статье это не обсуждаетс€.

ѕростота представлени€ отношений массивами, осуществима€ в случае приведени€ всех отношений в нормальную форму, предоставл€ет преимущества не только при хранении, но также при передаче больших объемов данных между системами, использующими во многом отличные представлени€ данных. ѕрименение при передаче соответствующим образом упакованного представлени€ в виде массива обеспечило бы следующие преимущества:

  1. ѕередаваема€ форма не содержала бы указатели (со значени€ми Ц адресами или смещени€ми).
  2. ¬ ней отсутствовали бы все зависимости от схемы хэш-адресации.
  3. ќна не содержала бы какие-либо индексы или упор€доченные списки.

≈сли рел€ционна€ модель пользовател€ приведена в нормальную форму, имена элементов данных в банке данных могут иметь более простую форму, чем в противном случае. ¬ общем случае им€ будет иметь следующую форму:

R(g).r.d

где R Ц им€ отношени€, g Ц необ€зательное им€ поколени€, r Ц необ€зательное им€ роли, d Ц им€ домена. ѕоскольку g необходимо только в случае существовани€ или ожидаемого по€влени€ нескольких поколений данного отношени€, а r необходимо только, если отношение R имеет два или более доменов с именем d, проста€ форма R.d часто будет достаточной.

1.5. Ќекоторые лингвистические аспекты

Ќа основе описанной выше рел€ционной модели данных возможна разработка универсального подъ€зыка данных, основанного на прикладном исчислении предикатов. ≈сли набор отношений находитс€ в нормальной форме, достаточно исчислени€ предикатов первого пор€дка. “акой €зык предоставл€л бы собой критерий лингвистической мощности дл€ всех остальных предлагаемых €зыков данных, и сам €вл€лс€ бы кандидатом дл€ встраивани€ (с соответствующими изменени€ми синтаксиса) в многочисленные включающие €зыки (программировани€, командно- или проблемно-ориентированные). ’от€ описание подробностей такого €зыка не €вл€етс€ целью данной статьи, укажем его наиболее €рко выраженные черты.

ѕусть R Ц подъ€зык данных, а H Ц включающий €зык. R допускает объ€вление отношений и их доменов. ¬ каждом объ€влении отношени€ указываетс€ первичный ключ этого отношени€. ќбъ€вленные отношени€ добавл€ютс€ в системный каталог дл€ использовани€ каждым участником сообщества пользователей, обладающим соответствующими правами. ¬ €зыке H возможны объ€влени€, отражающие представление этих отношений в пам€ти (такие объ€влени€ могут быть более изменчивыми). R допускает спецификации выборки любого подмножества данных из банка данных. ƒействи€ по запросу такой выборки Ц регулируютс€ ограничени€ми безопасности.

”ниверсальность подъ€зыка данных основана на его декларативности (а не на возможност€х вычислений). ¬ больших банках данных каждое подмножество данных имеет очень большое количество возможных (и осмысленных) описаний, даже если мы предполагаем (как мы это и делаем), что существует только конечное множество функций, к которым система получает доступ дл€ ограничени€ выбираемых данных. —ледовательно, класс выражений ограничени€, которые могут быть использованы дл€ спецификации множества, должен иметь выразительную мощность класса правильно построенных формул прикладного исчислени€ предикатов. ’орошо известно, что дл€ сохранени€ этой выразительной мощности не €вл€етс€ об€зательной возможность выражени€ (в соответствующем синтаксисе) каждой формулы выбранного исчислени€ предикатов. Ќапример, достаточно ограничитьс€ формулами, наход€щимис€ в предваренной нормальной форме [9].

¬ выражени€х ограничени€ или других част€х оператора выборки могут потребоватьс€ арифметические функции. ќни могут быть определены в H и использованы в R.

ќпределенное таким образом множество может быть получено только дл€ целей выполнени€ запроса или сохранено дл€ возможных изменений. ¬ставки принимают форму добавлени€ новых элементов в объ€вленные отношени€ без обращени€ внимани€ на какой-либо пор€док, который может существовать во внутреннем представлении. ”далени€, значимые дл€ всех пользователей (а не дл€ одного пользовател€ или некоторой группы), имеют форму удалени€ элементов из объ€вленных отношений. Ќекоторые удалени€ и обновлени€ могут порождатьс€ другими, если в R объ€влены зависимости удалени€ и обновлени€ между указанными отношени€ми.

ќдним существенным следствием прин€того представлени€ данных в €зыке, используемом дл€ выборки данных, €вл€ютс€ принципы именовани€ элементов данных и множеств. Ќекоторые аспекты этого были обсуждены в предыдущем разделе. ¬ обычном сетевом представлении пользователь часто обременен созданием и использованием большего числа имен отношений, чем это необходимо, т.к. имена ассоциированы скорее с пут€ми (или типами путей), чем с отношени€ми.

≈сли пользователь знает, что хранитс€ некоторое отношение, он будет ожидать возможности работы с ним,5) пользу€сь комбинацией известных ему аргументов и получа€ информацию об остальных "неизвестных" аргументах, поскольку именно они содержат интересующую его информацию. Ёту возможность системы (отсутствующую во многих современных информационных системах) мы будем называть симметричным использованием отношени€. ≈стественно, симметричность в производительности не ожидаетс€.

ƒл€ поддержки симметричного использовани€ одного бинарного отношени€ необходимы два направленных пути. ƒл€ отношени€ степени n количество путей, которые нужно именовать и контролировать, составл€ет n факториал (n!).

ќп€ть-таки, если прин€ть рел€ционное представление, в котором каждое n-арное отношение (n>2) должно быть описано пользователем как вложенное выражение, включающее только бинарные отношени€ (см., например, LEAP System ‘ельдмана (Feldman) [10]), то вместо всего лишь n+1 имен при использовании пр€мой n-арной нотации, описанной в разделе 1.2, потребуетс€ образовать 2n-1 имен. Ќапример, 4-арное отношение поставка, приведенное на рис.1 и содержащее 5 имен в n-арной нотации, во вложенной двоичной нотации было бы представлено в виде

P ( поставщик, Q ( деталь, R( проект, количество)))

и, таким образом, в нем использовались бы 7 имен.

ƒругим недостатком такого представлени€ €вл€етс€ его асимметри€. Ќесмотр€ на то, что эта асимметри€ не преп€тствует симметричному использованию, она, определенно, составл€ет некую основу дл€ запросов, которые трудно формулировать пользовател€м (попробуйте, например, выразить с использованием Q и R запрос о том, какие детали и в каком количестве используютс€ в данном проекте).

1.6. ¬ыразимые, именованные и хранимые отношени€

— банком данных св€заны два набора отношений: множество именованных и множество выразимых отношений. ћножество именованных отношений составл€ют те отношени€, которые сообщество пользователей может идентифицировать посредством простых имен (или идентификаторов). ќтношение R входит во множество именованных отношений после его объ€влени€ пользователем, обладающим соответствующими правами; оно выходит из этого множества, когда этот пользователь отмен€ет объ€вление R.

ћножество выразимых отношений включает все отношени€, которые могут быть описаны выражени€ми €зыка данных. “акие выражени€ состо€т из простых имен отношений из множества именованных отношений, имен поколений, ролей и доменов, логических св€зок, кванторов исчислени€ предикатов6) и некоторых символов константных отношений, таких как > и =. ћножество именованных отношений €вл€етс€ подмножеством множества выразимых отношений, как правило, очень малым подмножеством.

ѕоскольку некоторые отношени€ из множества именованных отношений могут €вл€тьс€ не завис€щими от времени комбинаци€ми других отношений из этого множества, полезно обсудить св€зывание с множеством именованных отношений набора утверждений, определ€ющих эти не завис€щие от времени ограничени€. ћы отложим дальнейшее обсуждение данного вопроса до введени€ нами нескольких операций над отношени€ми (см. разд. 2).

ќдна из основных проблем, с которыми сталкиваетс€ разработчик системы данных, обеспечивающей рел€ционную модель дл€ своих пользователей, Ц определение класса внутренних представлений, которые должны поддерживатьс€. ¬ идеале, разнообразие допустимых представлений данных должно быть достаточным, чтобы удовлетворить требовани€ к производительности при каждой установке системы. —лишком большое разнообразие приведет к ненужным накладным расходам внешней пам€ти и непрерывному повторному толкованию описаний уже используемых структур.

ƒл€ любого класса хранимых представлений система управлени€ данными должна предоставить средство преобразовани€ запросов пользовател€, выраженных на €зыке данных рел€ционной модели, в соответствующие (и эффективные) действи€ над текущим хранимым представлением. ƒл€ €зыка данных высокого уровн€ разработка такого средства представл€ет трудную проблему. “ем не менее, это проблема, котора€ должна быть решена: по мере увеличени€ количества пользователей, получающих параллельный доступ к большому банку данных, ответственность за обеспечение эффективного времени отклика и пропускной способности системы переходит от индивидуального пользовател€ к системе управлени€ данными.

2. »збыточность и согласованность

2.1. ќперации над отношени€ми.

ѕоскольку отношени€ €вл€ютс€ множествами, к ним применимы все обычные теоретико-множественные операции. ќднако результат может не быть отношением; например, объединение бинарного и тернарного отношений не €вл€етс€ отношением.

ќперации, обсуждаемые ниже, предназначены специально дл€ отношений. ќни ввод€тс€ по причине их ключевой роли при получении отношений из других отношений. ќсновное областью применени€ этих операций €вл€ютс€ информационные системы без логического вывода (т.е. системы, которые не обеспечивают механизм логического вывода), хот€ применимость операций не об€зательно исчезает при добавлении таких механизмов.

Ѕольшинство пользователей не должно быть напр€мую св€зано с этими операци€ми. ќднако проектировщикам информационных систем и люд€м, занимающимс€ управлением банком данных, следует знать их в совершенстве.

2.1.1. ѕерестановка. Ѕинарное отношение представл€етс€ в виде массива с двум€ столбцами. ¬ результате перестановки этих столбцов получаетс€ обратное отношение. ¬ общем случае, при перестановке столбцов n-арного отношени€ про результирующее отношение говор€т, что оно €вл€етс€ перестановкой заданного отношени€. —уществует, например, 4! = 24 перестановок отношени€ поставка, приведенного на рис. 1, с учетом тождественной перестановки, котора€ оставл€ет пор€док столбцов неизменным.

ѕоскольку пользовательска€ рел€ционна€ модель состоит из набора св€зей (отношений с неупор€доченными доменами), перестановка не €вл€етс€ существенной дл€ такой модели, рассматриваемой отдельно. ќна, тем не менее, существенна при рассмотрении хранимых представлений этой модели. ¬ системе, обеспечивающей симметричное использование отношений, множество запросов, на которые может быть получен ответ с использованием хранимого отношени€, совпадает с аналогично получаемым множеством дл€ любой перестановки этого отношени€. ’от€ одновременное хранение отношени€ и некоторой его перестановки не €вл€етс€ логически необходимым, соображени€ производительности могут сделать это целесообразным.

2.1.2. ѕроекци€. ѕредположим, что мы выбрали некоторые столбцы отношени€ (отбросив остальные) и затем удалили из полученного массива все дубликаты строк. ѕолученный в результате массив представл€ет отношение, про которое говор€т, что оно €вл€етс€ проекцией данного отношени€.

ќператор селекции ? используетс€ дл€ получени€ любой требуемой перестановки, проекции или комбинации этих операций. “ак, если L Ц список из k значений7) L = i1, i2,...,ik, и R Ц n-арное отношение (n?k), то ?L (R) есть k-арное отношение, j-тый столбец которого есть ij-тый столбец R (i=1,2,...,k) и в котором удалены дубликаты результирующих строк. –ассмотрим отношение поставка на рис.1. ѕерестановка проекции этого отношени€ приведена на рис.4. «аметьте, что в этом частном случае проекци€ имеет меньше n-кортежей, чем исходное отношение.

?31(поставка)

(проект

поставщик)


5

1


5

2


1

4


7

2

–исунок 4. ѕерестановка проекции отношени€ c рис.1

2.1.3. —оединение. ѕредположим, что нам даны два бинарных отношени€, имеющих некоторый общий домен. ѕри каких услови€х мы можем скомбинировать эти отношени€ дл€ построени€ тернарного отношени€, сохран€ющего всю информацию из данных отношений?

¬ примере на рис.5 показаны два отношени€ R и S, которые могут быть соединены без потери информации, а на рис.6 представлен результат соединени€ R и S. Ѕинарное отношение R соединимо с бинарным отношением S, если существует тернарное отношение U такое, что ?12(U)=R и ?23(U)=S. Ћюбое такое тернарное отношение называетс€ соединением R и S. ≈сли R, S €вл€ютс€ бинарными отношени€ми, такими, что ?2(R) = ?1(S), то R соединимо с S. ќдно из соединений, которое всегда существует в таком случае, это естественное соединение, определ€емое так:

R*S = {(a,b,c) : R(a,b) ? S(b,c)},

где R(a,b) имеет значение истина, если (a,b) €вл€етс€ элементом R, и S(b,c) Ц аналогично. ќчевидно, что

?12(R*S) = R

и

?23(R*S) = S.

«аметим, что соединение, показанное на рис.6, €вл€етс€ естественным соединением отношений R и S, представленных на рис.5. ƒругое соединение показано на рис.7.

R (поставщик деталь) S(деталь проект)
1 1 1 1
2 1 1 2
2 2 2 1

–исунок 5.ƒва соединимых отношени€

R*S (поставщик деталь проект)
1 1 1
1 1 2
2 1 1
2 1 2
2 2 1

–исунок 6.≈стественное соединение R и S (рис. 5)

U

(поставщик

деталь

проект)

1

1

2

2

1

1

2

2

1

–исунок 7. ƒругое соединение R и S (рис.5)

ѕри обследовании этих отношений обнаруживаетс€ элемент (элемент 1) домена деталь (домена, по которому производитс€ соединение), обладающий тем свойством, что он имеет более одного вхождени€ и в R, и в S. Ётот элемент увеличивает количество возможных соединений. “акой элемент домена соединени€ называетс€ точкой неоднозначности относительно соединени€ R и S.

≈сли ?21(R) или S €вл€ютс€ функци€ми,8) то при соединении R с S не может возникнуть точка неоднозначности. ¬ этом случае естественное соединение €вл€етс€ единственным соединением R с S. «аметьте, что повтор€ющеес€ уточнение "R с S" €вл€етс€ необходимым, поскольку S может быть соединимым с R (как и R с S), и это соединение должно быть предметом полностью отдельного рассмотрени€. Ќа рис.5 ни одно из отношений R, ?21(R), S, ?21(S) не €вл€етс€ функцией.

Ќеоднозначность в соединении R и S может быть иногда разрешена при помощи других отношений. ѕредположим, что нам даны или мы можем построить на доменах проект и поставщик из источников, не зависимых от R и S, отношение T со следующими свойствами:

  1. ?1(T) = ?2(S)
  2. ?1(T) = ?1(R)
  3. T(j,s) > ?p(R(s,p) ? S(p,j)
  4. R(s,p) > ?j(S(p,j) ? T(j,s)
  5. S(p,j) > ?s(T(j,s) ? R(s,p)

¬ этом случае мы можем построить соединение трех отношений R, S, T, то есть тернарное отношение такое, что

?12(U)=R, ?23(U)=S, ?31(U)=T

“акое соединение мы будем называть циклическим 3-соединением, чтобы отличать его от линейного 3-соединени€, которое представл€ло бы собой 4-арное отношение V такое, что

?12(V)=R, ?23(V)=S, ?34(V)=T.

ѕоскольку возможно существование более чем одного циклического 3-соединени€ (см., например, рис.8,9), обсто€тельства, при которых это может происходить, накладывают гораздо более сильные ограничени€, чем услови€ множественности 2-соединений. Ѕолее точно, отношени€ R, S, T должны содержать точки неоднозначности соединений R и S (скажем, точка x), S и T (скажем, y) и T и R ( скажем, z) и, более того, y должно соответствовать x в S, z соответствовать y в T и x соответствовать z в R. «аметьте, что на рис.8 точки x=a, y=d, z=2 обладают этими свойствами.

R (s p) S (p j) T (j s)
1 a a d d 1
2 a a e d 2
2 b b d e 2
b e e 2

–исунок 8.Ѕинарные отношени€ с несколькими циклическими 3-соединени€ми

U (s p j) U" (s p j)
1 a d 1 a d
2 a e 2 a d
2 b d 2 a e
2 b e 2 b d
2 b e

–исунок 9.ƒва циклических 3-соединени€ отношений c рис.8

≈стественное линейное соединение трех бинарных отношений R, S, T определ€етс€ так:

R*S*T = { (a,b,c,d) : R(a,b) ? S(b,c) ? T(c,d) },

где скобки в левой части равенства не нужны, т.к. естественное 2-соединение (*) ассоциативно. ƒл€ получени€ циклического аналога мы введем оператор ?, выдающий в качестве результата отношение степени n-1 из отношени€ степени n, св€зыва€ вместе его концы. ≈сли R есть n-арное отношение (n?2), то св€зывание R определ€етс€ уравнением

?(R) = { (a1, a2, ....,an-1) : R(a1, a2, ...., an-1, an) ? a1=an}

“еперь мы можем представить естественное циклическое 3-соединение R, S, T выражением

?(R*S*T).

ќбобщение пон€тий линейного и циклического 3-соединений и их естественных аналогов дл€ соединени€ n бинарных отношений (где n?3) очевидно. ќднако можно сказать несколько слов относительно соединени€ отношений, которые не об€зательно €вл€ютс€ бинарными. –ассмотрим случай двух отношений R (степени r) и S (степени s), которые должны быть соединены по р их доменам (р < r, р < s). ƒл€ простоты предположим, что эти р доменов €вл€ютс€ последними р из r доменов R и первыми р из s доменов S. ≈сли это не так, мы всегда можем применить соответствующую перестановку, чтобы этого добитьс€. “еперь возьмем ƒекартово произведение первых r-р доменов R и назовем это новым доменом A. ¬озьмем ƒекартово произведение последних р доменов R и назовем это B. ¬озьмем ƒекартово произведение последних s-р доменов S и назовем это C.

ћы можем трактовать R как бинарное отношение над доменами A, B. “очно так же, мы можем трактовать S как бинарное отношение над доменами B, C. “еперь полностью применимы пон€ти€ линейного и циклического 3-соединений. јналогичный подход может быть предприн€т дл€ линейных и циклических n-соединений n отношений разных степеней.

2.1.4.  омпозици€. „итатель, возможно, знаком с пон€тием композиции применительно к функци€м. ћы обсудим обобщение этого пон€ти€ и применим его вначале к бинарным отношени€м. Ќаши определени€ композиции и композиционности основаны непосредственно на определени€х соединени€ и соединимости, приведенных выше.

ѕредположим, что нам даны два отношени€ R и S. T €вл€етс€ композицией R и S, если существует соединение U отношений R и S такое, что T = ?13 (U). “аким образом, два отношени€ €вл€ютс€ композиционными в том и только в том случае, когда они €вл€ютс€ соедин€емыми. ќднако, существование более чем одного соединени€ R и S не влечет за собой существовани€ более чем одной композиции R и S.

ƒл€ естественного соединени€ R и S существует естественна€ композици€,9) определ€ема€ как

R Ј S = ?13 (R*S) .

≈стественна€ композици€ отношений R и S, приведенных на рис. 5, показана на рис.10, друга€ композици€ приведена на рис.11 (получена из соединени€, представленного на рис.7).

¬ случае существовани€ двух или более соединений, количество различных композиций может варьироватьс€ от 1 до общего количества различных соединений. Ha рис.12 представлен пример двух отношений, имеющих несколько соединений и всего одну композицию. «аметьте, что точка неоднозначности c тер€етс€ при композиции R и S, т.к. однозначное соответствие устанавливаетс€ через точки a,b,d,e.

R Ј S (проект поставщик)
1 1
1 2
2 1
2 2

–исунок 10. ≈стественна€ композици€ отношений R и S (показанных на рис.5)

T (проект поставщик)
1 2
2 1

–исунок 11. ƒруга€ композици€ отношений R и S (показанных на рис.5)

R

(поставщик

деталь)

S

(деталь

проект)


1

a

a

g


1

b

b

f


1

c

c

f


2

c

c

g


2

d

d

g


2

e

e

f

–исунок 12. ћного соединений, только одна композици€

–асширение пон€ти€ композиции на пары необ€зательно бинарных отношений (возможно, с разными степен€ми) следует тому же подходу, что и расширение пон€ти€ попарного соединени€ таких отношений.

Ќедостаточное понимание пон€ти€ композиции привело некоторых разработчиков систем к ситуации, которую можно назвать ловушкой св€зей. Ёта ловушка может быть проиллюстрирована на следующем примере. ѕредположим, что описание каждого поставщика св€зано указател€ми с описани€ми каждой из деталей, поставл€емых этим поставщиком, и, аналогичным образом, описание каждой детали св€зано с описани€ми каждого проекта, использующего эту деталь. Ќапрашивающийс€ вывод, €вл€ющийс€, вообще говор€, ошибочным, заключаетс€ в том, что если проследовать по всем пут€м от данного поставщика через детали, поставл€емые им к проектам, в которых используютс€ эти детали, то можно получить правильное множество всех проектов, в которых участвует этот поставщик. “акое заключение верно только в очень частном случае, когда искомое отношение между проектами и поставщиками €вл€етс€, по существу, естественным соединением двух других отношений Ц и конечно, мы должны добавить фразу "в любой момент времени", т.к. обычно это свойство подразумевает существование требований, относ€щихс€ к технике путей доступа.

2.1.5. ќграничение. ѕодмножество отношени€ €вл€етс€ отношением. ќдин из способов воздействи€ отношени€ S на отношение R дл€ получени€ подмножества R заключаетс€ в применении операции ограничени€ отношени€ R по отношению S. Ёта операци€ €вл€етс€ обобщением ограничени€ функции на подмножество ее области определени€ и определ€етс€ следующим образом.

ѕусть L, M Ц списки индексных значений одинаковой длины такие, что L = i1, i2,..., ik, M = j1, j2, ..., jk, где k? степень R и k? степень S. “огда L,M-ограничение R по S, обозначаемое как RL|MS, есть максимальное подмножество R' множества R, такое, что

?L(R') = ?M (S).

Ёта операци€ определена только в том случае, если применима операци€ равенства между элементами ?ih( R), с одной стороны и pjh(S), с другой, дл€ всех h=1,2,...k.

“ри отношени€ R, S, R', приведенные на рис.13, удовлетвор€ют соотношению R'=R(2,3)|(1,2)S.

R ( s р j ) S( р j ) R"( s р j )
1 a A a A 1 a A
2 a A c B 2 a A
2 a B b B 2 b B
2 b A
2 b B

–исунок 13. ѕример ограничени€

“еперь мы готовы рассмотреть различные применени€ этих операций над отношени€ми.

2.2. »збыточность

Ќеобходимо различать избыточность во множестве именованных отношений и избыточность в хранимом множестве представлений. «десь мы будем касатьс€ в основном первого вида избыточности. ƒл€ начала нам необходимо точное пон€тие порождаемости дл€ отношений.

ѕредположим, что ? Ц это набор операций над отношени€ми, и кажда€ операци€ обладает тем свойством, что вырабатывает единственное отношение из своих операндов (т.е. естественное соединение допустимо, а соединение нет). ќтношение R €вл€етс€ ?-выводимым из множества отношений S, если существует последовательность операций из набора ?, котора€ "в любой момент времени" производит R из элементов S. ‘раза "в любой момент времени" присутствует потому, что мы рассматриваем измен€ющиес€ во времени отношени€, и дл€ нас представл€ет интерес свойство порождаемости, сохран€ющеес€ в течение длительного периода времени. ƒл€ набора именованных св€зей в системах без логического вывода достаточный набор ?1 содержит следующие операции: проекци€, естественное соединение, св€зывание и ограничение. ѕерестановка неуместна, а естественную композицию включать не требуетс€, т.к. ее можно получить путем естественного соединени€ с последующей проекцией. ƒл€ хранимого множества представлений достаточный набор ?2 должен включать перестановку и дополнительные операции, св€занные с получением подмножеств и сли€нием отношений, упор€дочиванием и св€зыванием их элементов.

2.2.1. —ильна€ избыточность. ћножество отношений €вл€етс€ сильно избыточным, если оно содержит по меньшей мере одно отношение, некотора€ проекци€ которого может быть порождена из других проекций отношений этого множества. —ледующие два примера приведены дл€ того, чтобы объ€снить, почему сильна€ избыточность определ€етс€ таким образом, а также дл€ демонстрации ее практического использовани€. ¬ первом примере набор отношений состоит из одного следующего отношени€:

служащий (номер, им€, номер_менеджера, им€_менеджера)

где номер €вл€етс€ первичным ключом, и номер_менеджера €вл€етс€ внешним ключом. ќбозначим активный домен через ?t и предположим, что

?t (номер_менеджера) ? ?t (номер)

и

?t (им€_менеджера) ? ?t (им€)

в любой момент времени t. ¬ этом случае избыточность очевидна: домен им€_менеджера не €вл€етс€ необходимым. „тобы убедитьс€ в том, что эта избыточность €вл€етс€ сильной избыточностью в соответствии с приведенным выше определением, заметим, что

?34 (служащий) = ?12 (служащий)1|1?3(служащий).

¬о втором примере набор отношений включает описывающее поставщиков отношение S с первичным ключом s#, описывающее отделы отношение D с первичным ключом d# и описывающее проекты отношение J с первичным ключом j#, а также следующие отношени€:

P(s#, d#,...), Q(s#, j#,...), R(d#, j#,...),

где в каждом случае многоточие означает домены, отличающиес€ от s#, d#, j#. ѕредположим, что удовлетвор€етс€ следующее не завис€щее от времени условие C: поставщик s обслуживает отдел d (отношение P) тогда и только тогда, когда поставщик s обслуживает некоторый проект j# (отношение Q), который выполн€етс€ отделом d# (отношение R). “огда мы можем записать соотношение

?12(P) = ?12 (Q) Ј ?21 (R)

и таким образом показать наличие сильной избыточности.

¬ажна€ причина существовани€ сильной избыточности в множестве именованных св€зей заключаетс€ в удобстве дл€ пользовател€. „астным случаем ее применени€ €вл€етс€ сохранение во множестве именованных св€зей полуустаревших св€зей дл€ того, чтобы старые программы, ссылающиес€ на них по имени, могли правильно выполн€тьс€. Ќаличие знаний о существовании сильной избыточности во множестве именованных отношений предоставл€ет администратору системы или базы данных большую свободу в выборе внутреннего представлени€ дл€ более эффективного управлени€ текущей нагрузкой. ≈сли сильна€ избыточность во множестве именованных отношений непосредственно отражаетс€ в сильной избыточности во множестве хранимых представлений (или если во множество хранимых представлений внесена дополнительна€ сильна€ избыточность), то, вообще говор€, могут потребоватьс€ дополнительные внешн€€ пам€ть и врем€ дл€ выполнени€ операций обновлени€, с возможным замедлением выполнени€ некоторых запросов и увеличением нагрузки на центральный процессор.

2.2.2. —лаба€ избыточность. ћожет существовать другой тип избыточности. ¬ отличие от сильной избыточности она не описываетс€ каким-либо соотношением. Ќабор отношений €вл€етс€ слабо избыточным, если в него входит отношение, которое содержит проекцию, не порождаемую из других отношений набора, но в любой момент времени совпадающую с проекцией некоторого соединени€ проекций отношений из этого набора.

ћы можем проиллюстрировать слабую избыточность, рассмотрев второй пример сильной избыточности (из приведенных выше) и предположив, что условие C в некоторые моменты времени не выполн€етс€. ќтношени€ ?12(P), ?12(Q), ?12(R) €вл€ютс€ сложными 10) отношени€ми с возможным существованием точек неоднозначности, по€вл€ющихс€ иногда в потенциальных соединени€х каких-либо двух отношений. ѕри этих услови€х ни одно из них не порождаетс€ из двух других. ќднако между ними существует зависимость, поскольку каждое из них €вл€етс€ проекцией некоторого циклического соединени€ трех отношений. ќдин из видов слабой избыточности может быть охарактеризован следующим утверждением: в любой момент времени ?12(P) €вл€етс€ некоторой композицией ?12(Q) и ?21(R). Ёта композици€ может быть естественной при одних обсто€тельствах и может не €вл€тьс€ таковой при других.

¬ообще говор€, слабые избыточности €вл€ютс€ неотъемлемой частью логических потребностей сообщества пользователей. ќни не могут быть устранены администратором системы или базы данных. ≈сли они все-таки возникают, они возникают и во множестве именованных отношений, и во множестве хранимых представлений.

2.3. —огласованность

¬ каком бы смысле не €вл€лось избыточным множество именованных отношений, мы будем св€зывать с этим множеством набор утверждений, определ€ющих все избыточности, имеющие место в любой момент времени дл€ отношений этого множества. ≈сли в информационной системе отсутствует подробна€ семантическа€ информаци€ о каждом именованном отношении (наиболее веро€тный случай), то система не может вы€вить избыточность, существующую во множестве именованных отношений. ќна может, по истечении некоторого периода времени, предпринимать попытки установить наличие избыточностей, но такие попытки могут быть подвержены ошибкам.

ƒл€ данного набора C измен€емых во времени отношений, ассоциированного с ним множества Z ограничительных утверждений и значени€ V набора C в какой-либо момент времени мы будем называть состо€ние (C, Z, V) согласованным или несогласованным в зависимости от того, удовлетвор€ет ли V набору условий Z или нет. Ќапример, дл€ набора хранимых отношений R,S,T вместе с ограничительным утверждением "?12(T) €вл€етс€ композицией ?12 (R) и ?12 (S)" мы можем периодически провер€ть, что значени€, хран€щиес€ в R,S,T, удовлетвор€ют этому условию. јлгоритм осуществлени€ такой проверки должен просматривать первые два столбца каждого из отношений R,S,T (вне зависимости от способа их представлени€ в системе) и определ€ть, выполн€ютс€ ли следующие услови€

  1. ?1(T) = ?1 (R)
  2. ?2(T) = ?2 (S)
  3. дл€ каждой пары элементов (a,c) отношени€ ?12 (T) существует элемент b, такой, что (a,b) содержитс€ в ?12 (R) и (b,c) содержитс€ в ?12 (S).

—уществуют практические проблемы (которые мы не будем здесь обсуждать) получени€ моментального снимка набора отношений, некоторые из которых могут быть очень большими и сильно изменчивыми.

¬ажно отметить, что согласованность в том виде, как она определена выше, €вл€етс€ свойством состо€ни€ банка данных в какой-либо момент времени и не зависит от того, как это состо€ние было достигнуто. Ёто означает, в частности, что невозможно отличить несогласованное состо€ние, возникшее в результате оплошности пользовател€, от состо€ни€, порожденного преднамеренными действи€ми. –ассмотрение простого примера показывает обоснованность такого (возможно, нешаблонного) подхода к согласованности.

ѕредположим, что множество именованных отношений C содержит отношени€ S, J, D, P, Q, R из примера раздела 2.2, и что P, Q, R обладают сильной или слабой избыточностью в определенном выше смысле (в рассматриваемом нами случае не важно, кака€ именно избыточность имеет место). ƒалее, предположим, что в некоторый момент времени t банк данных находитс€ в согласованном состо€нии и не содержит никакого проекта j такого, что поставщик 2 обслуживает проект j, и проект j ведетс€ отделом 5. —оответственно, в ?12(P) не существует элемента (2,5). ѕусть теперь пользователь вводит элемент (2,5) в ?12(P), вставл€€ соответствующий элемент в P. ¬ этот момент состо€ние банка данных €вл€етс€ несогласованным. Ёта несогласованность могла возникнуть вследствие оплошности, если по€вление (2,5) €вл€етс€ правильным, и действительно существует проект j такой, что поставщик 2 обслуживает проект j и проект j ведетс€ отделом 5. ¬ этом случае очень веро€тно, что пользователь собираетс€ в ближайшем будущем добавить элементы в Q и R, результатом чего €витс€ по€вление (2,j) в ?12(Q) и (5,j) в ?12(R). — другой стороны, ввод (2,5) мог быть ошибочным. “ак могло бы получитьс€, если бы пользователь намеревалс€ вставить в P некоторый другой элемент, по€вление которого перевело бы согласованное состо€ние в согласованное состо€ние. —уть в том, что как правило, в системе будут отсутствовать средства разрешени€ этого вопроса без опроса окружени€ системы (например, пользовател€, породившего несогласованность).

 онечно, существует несколько возможных способов, при помощи которых система сможет обнаружить несогласованность и отреагировать на нее. ѕри одном из подходов, система определ€ет наличие несогласованности при выполнении любой операции вставки и удалени€ записей или обновлени€ ключа. ≈стественно, така€ проверка замедлит эти операции. ¬ случае возникновени€ несогласованности подробности ситуации сохран€ютс€ в системе, и, если в течение некоторого периода времени ситуаци€ не будет исправлена, пользователь или человек, ответственный за безопасность и целостность данных, будет об этом извещен. ƒругой подход Ц производить проверку согласованности как фоновую операцию раз в день или реже. ¬новь поступившие данные, по€вление которых вызвало несогласованность, оставшуюс€ в банке данных на момент проверки, могут быть установлены, если система поддерживает журнал транзакций, привод€щих к изменению состо€ни€. ¬торой подход будет, конечно же, предпочтительнее, если возникает только немного посто€нных несогласованностей.

2.4. «аключение

¬ разделе 1 предлагаетс€ рел€ционна€ модель данных, служаща€ основой дл€ защиты пользователей систем форматированных данных от потенциально разрушительных изменений представлени€ данных, вызванных увеличением банка данных или изменением нагрузки. ¬водитс€ нормальна€ форма дл€ набора измен€ющихс€ во времени отношений.

¬ разделе 2 определ€ютс€ операции над отношени€ми и два вида избыточности, которые затем примен€ютс€ к решению проблемы поддержки данных в согласованном состо€нии. “ака€ поддержка может стать очень серьезной проблемой по мере увеличени€ количества различных типов данных, содержащихс€ в общих банках данных.

ћногие вопросы поставлены и остались без ответа. Ќапример, в разделе 1.4 упом€нуты только наиболее важные свойства подъ€зыка данных. He обсуждаютс€ ни чисто лингвистические детали такого €зыка, ни проблемы его реализации. “ем не менее, представленный материал может быть достаточным дл€ опытных системных программистов при реализации некоторых подходов. Ќадеемс€ также, что эта стать€ будет способствовать повышению уровн€ точности при работе с системами форматированных данных.

Ѕлагодарности. C.T. Davis из IBM Poughkeepsie убедил автора в необходимости независимости данных в будущих информационных системах. јвтор выражает благодарность ему и, также, F.P.Palermo, C.P.Wang, E.B.Altman и M.E.Senko из IBM San Jose Research Laboratory за полезные обсуждени€.

ѕолучена в сент€бре 1969 г., пересмотрена в феврале 1970 г.

Ћитература

  1. Childs, D.L. Feasibility of a set-theoretical data structure Ц a general structure based on a reconstituted definition of relation. proc. IFIP Cong., 1968, North Holland Pub. Co., Amsterdam, р. 162-172.
  2. Levein, R.E., and Maron, M.E. A computer system for inference execution and data retrieval. Comm. ACM 10,11 (Nov. 1967), 715-721.
  3. Bachman, C.W. Software for random access processing. Datamation (Apr. 1965), 36-41.
  4. McGee, W.C. Generalized file processing. In Annual Review in Automatic Programming 5, 13, Pergamon Press, New York, 1969, рр. 77-149.
  5. Information Management System/360, Application Description Manual H20-0524-1. IBM Corp., White plains, N.Y., July 1968.
  6. GIS (Generalized Information System), Application Description Manual H20-0574. IBM Corp., White Plains, N.Y., 1965.
  7. Bleier, R.E. Treating hierarchial data structures in the SDC time-shared data management system (TDMS). Proc. ACM 22nd Nat. Conf., 1967, MDI Publications, Wayne, pa., рр. 41-49.
  8. IDS Reference Manual GE 625/635, GE Inform. Sys. Div., Pheonix, Ariz., CPB 1093B, Feb. 1968.
  9. Church, A. An Introduction to Mathematical Logic I. Princeton U. Press, Princeton, N.J., 1956.
  10. Feldman, J.A., and Rovner, P.D. An Algol-based associative language. Stanford Artificial Intelligence Rep. AI-66, Aug. 1, 1968.


1) Ѕолее точно, R €вл€етс€ подмножеством ƒекартова произведени€ S1 ? S2 ? ... ? Sn.

2) √овор€ математическим €зыком, св€зь - это класс эквивалентности отношений, эквивалентных относительно перестановки доменов (—м. п.2.1.1).

3) ≈стественно, пользователь производит ввод данных в компьютерную систему и их выборку гораздо более эффективно, если он понимает смысл данных.

4) ћ.≈. —енко из IBM, —ан-’осе, независимо указывает на желательность устранени€ непростых доменов.

5) –абота с отношением включает запросы, обновление и удаление.

6) ѕоскольку каждое отношение в реальном банке данных €вл€етс€ конечным в каждый момент времени, кванторы существовани€ и всеобщности могут быть выражены в терминах функции, вычисл€ющей количество элементов в любом конечном множестве.

7) ѕри работе со св€з€ми мы используем имена доменов (в случае необходимости уточненные именами ролей) вместо позиций доменов.

8) ‘ункци€ Ц бинарное отношение "один-к-одному" или "многие-к-одному", но не "один-ко-многим".

9) ƒругие авторы склон€ютс€ к игнорированию композиций, отличных от естественной, и, соответственно, называют композицией именно этот частный случай Ц см., например, "ќбщую топологию"  елли.

10) Ѕинарное отношение €вл€етс€ сложным, если ни оно само, ни обратное к нему не €вл€ютс€ функци€ми.


»сточник: citforum.ru

-
–ел€ционные базы данных обречены?

–ел€ционные базы данных обречены?

ѕримечание переводчика: хоть стать€ довольно стара€ (опубликована 2 года назад) и носит громкое название, в ней все же даетс€ хорошее представление о различи€х рел€ционных Ѕƒ и NoSQL Ѕƒ, их преимуществах и недостатках, а также приводитс€ краткий обзор нерел€ционных хранилищ.

image
¬ последнее врем€ по€вилось много нерел€ционных баз данных. Ёто говорит о том, что если вам нужна практически неограниченна€ масштабируемость по требованию, вам нужна нерел€ционна€ Ѕƒ.

≈сли это правда, значит ли это, что могучие рел€ционные Ѕƒ стали у€звимы? «начит ли это, что дни рел€ционных Ѕƒ проход€т и скоро совсем пройдут? ¬ этой статье мы рассмотрим попул€рное течение нерел€ционных баз данных применительно к различным ситуаци€м и посмотрим, повли€ет ли это на будущее рел€ционных Ѕƒ.

–ел€ционные базы данных существуют уже около 30 лет. «а это врем€ вспыхивало несколько революций, которые должны были положить конец рел€ционным хранилищам.  онечно, ни одна из этих революций не состо€лась, и одна из них ни на йоту не поколебала позиции рел€ционных Ѕƒ.

Ќачнем с основ


–ел€ционна€ база данных представл€ет собой набор таблиц (сущностей). “аблицы состо€т из колонок и строк (кортежей). ¬нутри таблиц могут быть определены ограничени€, между таблицами существуют отношени€. ѕри помощи SQL можно выполн€ть запросы, которые возвращают наборы данных, получаемых из одной или нескольких таблиц. ¬ рамках одного запроса данные получаютс€ из нескольких таблиц путем их соединени€ (JOIN), чаще всего дл€ соединени€ используютс€ те же колонки, которые определ€ют отношени€ между таблицами. Ќормализаци€ Ч это процесс структурировани€ модели данных, обеспечивающий св€зность и отсутствие избыточности в данных.
image
ƒоступ к рел€ционным базам данных осуществл€етс€ через рел€ционные системы управлени€ базами данных (–—”Ѕƒ). ѕочти все системы баз данных, которые мы используем, €вл€ютс€ рел€ционными, такие как Oracle, SQL Server, MySQL, Sybase, DB2, TeraData и так далее.

ѕричины такого доминировани€ неочевидны. Ќа прот€жении всего существовани€ рел€ционных Ѕƒ они посто€нно предлагали наилучшую смесь простоты, устойчивости, гибкости, производительности, масштабируемости и совместимости в сфере управлении данными.

ќднако чтобы обеспечить все эти особенности, рел€ционные хранилища неверо€тно сложны внутри. Ќапример, простой SELECT запрос может иметь сотни потенциальных путей выполнени€, которые оптимизатор оценит непосредственно во врем€ выполнени€ запроса. ¬се это скрыто от пользователей, однако внутри –—”Ѕƒ создает план выполнени€, основывающийс€ на вещах вроде алгоритмов оценки стоимости и наилучшим образом отвечающий запросу.

ѕроблемы рел€ционных Ѕƒ


’от€ рел€ционные хранилища и обеспечивают наилучшую смесь простоты, устойчивости, гибкости, производительности, масштабируемости и совместимости, их показатели по каждому из этих пунктов не об€зательно выше, чем у аналогичных систем, ориентированных на какую-то одну особенность. Ёто не €вл€лось большой проблемой, поскольку всеобщее доминирование рел€ционных —”Ѕƒ перевешивало какие-либо недочеты. “ем не менее, если обычные –Ѕƒ не отвечали потребност€м, всегда существовали альтернативы.

—егодн€ ситуаци€ немного друга€. –азнообразие приложений растет, а с ним растет и важность перечисленных особенностей. » с ростом количества баз данных, одна особенность начинает затмевать все другие. Ёто масштабируемость. ѕоскольку все больше приложений работают в услови€х высокой нагрузки, например, таких как веб-сервисы, их требовани€ к масштабируемости могут очень быстро мен€тьс€ и сильно расти. ѕервую проблему может быть очень сложно разрешить, если у вас есть рел€ционна€ Ѕƒ, расположенна€ на собственном сервере. ѕредположим, нагрузка на сервер за ночь увеличилась втрое.  ак быстро вы сможете проапгрейдить железо? –ешение второй проблемы также вызывает трудности в случае использовани€ рел€ционных Ѕƒ.

–ел€ционные Ѕƒ хорошо масштабируютс€ только в том случае, если располагаютс€ на единственном сервере.  огда ресурсы этого сервера закончатс€, вам необходимо будет добавить больше машин и распределить нагрузку между ними. » вот тут сложность рел€ционных Ѕƒ начинает играть против масштабируемости. ≈сли вы попробуете увеличить количество серверов не до нескольких штук, а до сотни или тыс€чи, сложность возрастет на пор€док, и характеристики, которые делают рел€ционные Ѕƒ такими привлекательными, стремительно снижают к нулю шансы использовать их в качестве платформы дл€ больших распределенных систем.

„тобы оставатьс€ конкурентоспособными, вендорам облачных сервисов приходитс€ как-то боротьс€ с этим ограничением, потому что кака€ ж это облачна€ платформа без масштабируемого хранилища данных. ѕоэтому у вендоров остаетс€ только один вариант, если они хот€т предоставл€ть пользовател€м масштабируемое место дл€ хранени€ данных. Ќужно примен€ть другие типы баз данных, которые обладают более высокой способностью к масштабированию, пусть и ценой других возможностей, доступных в рел€ционных Ѕƒ.

Ёти преимущества, а также существующий спрос на них, привел к волне новых систем управлени€ базами данных.

Ќова€ волна


“акой тип баз данных прин€то называть хранилище типа ключ-значение (key-value store). ‘актически, никакого официального названи€ не существует, поэтому вы можете встретить его в контексте документо-ориентированных, атрибутно-ориентированных, распределенных баз данных (хот€ они также могут быть рел€ционными), шардированных упор€доченных массивов (sharded sorted arrays), распределенных хэш-таблиц и хранилищ типа ключ-значени€. » хот€ каждое из этих названий указывает на конкретные особенности системы, все они €вл€ютс€ вариаци€ми на тему, которую мы будем назвать хранилище типа ключ-значение.

¬прочем, как бы вы его не называли, этот Ђновыйї тип баз данных не такой уж новый и всегда примен€лс€ в основном дл€ приложений, дл€ которых использование рел€ционных Ѕƒ было бы непригодно. ќднако без потребности веба и Ђоблакаї в масштабируемости, эти системы оставались не сильно востребованными. “еперь же задача состоит в том, чтобы определить, какой тип хранилища больше подходит дл€ конкретной системы.
–ел€ционные Ѕƒ и хранилища типа ключ-значение отличаютс€ коренным образом и предназначены дл€ решени€ разных задач. —равнение характеристик позволит всего лишь пон€ть разницу между ними, однако начнем с этого:

’арактеристики хранилищ
–ел€ционна€ Ѕƒ ’ранилище типа ключ-значение
Ѕаза данных состоит из таблиц, таблицы содержат колонки и строки, а строки состо€т из значений колонок. ¬се строки одной таблицы имеют единую структуру.
ƒл€ доменов можно провести аналогию с таблицами, однако в отличие от таблиц дл€ доменов не определ€етс€ структура данных. ƒомен Ц это така€ коробка, в которую вы можете складывать все что угодно. «аписи внутри одного домена могут иметь разную структуру.
ћодель данных1 определена заранее. явл€етс€ строго типизированной, содержит ограничени€ и отношени€ дл€ обеспечени€ целостности данных.
«аписи идентифицируютс€ по ключу, при этом кажда€ запись имеет динамический набор атрибутов, св€занных с ней.
ћодель данных основана на естественном представлении содержащихс€ данных, а не на функциональности приложени€.
¬ некоторых реализаци€ атрибуты могут быть только строковыми. ¬ других реализаци€х атрибуты имеют простые типы данных, которые отражают типы, использующиес€ в программировании: целые числа, массива строк и списки.
ћодель данных подвергаетс€ нормализации, чтобы избежать дублировани€ данных. Ќормализаци€ порождает отношени€ между таблицами. ќтношени€ св€зывают данные разных таблиц.
ћежду доменами, также как и внутри одного домена, отношени€ €вно не определены.

Ќикаких joinТов


’ранилища типа ключ-значение ориентированы на работу с запис€ми. Ёто значит, что вс€ информаци€, относ€ща€с€ к данной записи, хранитс€ вместе с ней. ƒомен (о котором вы можете думать как о таблице) может содержать бессчетное количество различных записей. Ќапример, домен может содержать информацию о клиентах и о заказах. Ёто означает, что данные, как правило, дублируютс€ между разными доменами. Ёто приемлемый подход, поскольку дисковое пространство дешево. √лавное, что он позвол€ет все св€занные данные хранить в одном месте, что улучшает масштабируемость, поскольку исчезает необходимость соедин€ть данные из различных таблиц. ѕри использовании рел€ционной Ѕƒ, потребовалось бы использовать соединени€, чтобы сгруппировать в одном месте нужную информацию.
image
’от€ дл€ хранени€ пар ключ-значение потребность в отношени€ резко падает, отношени€ все же нужны. “акие отношени€ обычно существуют между основными сущност€ми. Ќапример, система заказов имела бы записи, которые содержат данные о покупател€х, товарах и заказах. ѕри этом неважно, наход€тс€ ли эти данные в одном домене или в нескольких. —уть в том, что когда покупатель размещает заказ, вам скорее всего не захочетс€ хранить информацию о покупателе и о заказе в одной записи.
¬место этого, запись о заказе должна содержать ключи, которые указывают на соответствующие записи о покупателе и товаре. ѕоскольку в запис€х можно хранить любую информацию, а отношени€ не определены в самой модели данных, система управлени€ базой данных не сможет проконтролировать целостность отношений. Ёто значит, что вы можете удал€ть покупателей и товары, которые они заказывали. ќбеспечение целостности данных целиком ложитс€ на приложение.

ƒоступ к данным
–ел€ционна€ Ѕƒ ’ранилище типа ключ-значение
ƒанные создаютс€, обновл€ютс€, удал€ютс€ и запрашиваютс€ с использованием €зыка структурированных запросов (SQL).
ƒанные создаютс€, обновл€ютс€, удал€ютс€ и запрашиваютс€ с использованием вызова API методов.
SQL-запросы могут извлекать данные как из одиночной таблица, так и из нескольких таблиц, использу€ при этом соединени€ (joinТы).
Ќекоторые реализации предоставл€ют SQL-подобный синтаксис дл€ задани€ условий фильтрации.
SQL-запросы могут включать агрегации и сложные фильтры.
«ачастую можно использовать только базовые операторы сравнений (=, !=, <, >, <= и =>).
–ел€ционна€ Ѕƒ обычно содержит встроенную логику, такую как триггеры, хранимые процедуры и функции.
¬с€ бизнес-логика и логика дл€ поддержки целостности данных содержитс€ в коде приложений.

¬заимодействие с приложени€ми
–ел€ционна€ Ѕƒ ’ранилище типа ключ-значение
„аще всего используютс€ собственные API, или обобщенные, такие как OLE DB или ODBC.
„аще всего используютс€ SOAP и/или REST API, с помощью которых осуществл€етс€ доступ к данным.
ƒанные хран€тс€ в формате, который отображает их натуральную структуру, поэтому необходим маппинг структур приложени€ и рел€ционных структур базы.
ƒанные могут более эффективно отображатьс€ в структуры приложени€, нужен только код дл€ записи данных в объекты.

’ранилища типа ключ-значение: преимущества


≈сть два четких преимущества таких систем перед рел€ционными хранилищами.

ѕодход€т дл€ облачных сервисов

ѕервое преимущество хранилищ типа ключ-значение состоит в том, что они проще, а значит обладают большей масштабируемостью, чем рел€ционные Ѕƒ. ≈сли вы размещаете вместе собственную систему, и планируете разместить дюжину или сотню серверов, которым потребуетс€ справл€тьс€ с возрастающей нагрузкой, за вашим хранилищем данных, тогда ваш выбор Ц хранилища типа ключ-значение.

Ѕлагодар€ тому, что такие хранилища легко и динамически расшир€ютс€, они также пригод€тс€ вендорам, которые предоставл€ют многопользовательскую веб-платформу хранени€ данных. “ака€ база представл€ет относительно дешевое средство хранени€ данных с большим потенциалом к масштабируемости. ѕользователи обычно плат€т только за то, что они используют, однако их потребности могут вырасти. ¬ендор сможет динамически и практически без ограничений увеличить размер платформы, исход€ из нагрузки.

Ѕолее естественна€ интеграци€ с кодом

–ел€ционна€ модель данных и объектна€ модель кода обычно стро€тс€ по-разному, что ведет к некоторой несовместимости. –азработчики решают эту проблему при помощи написани€ кода, который отображает рел€ционную модель в объектную модель. Ётот процесс не имеет четкой и быстро достижимой ценности и может зан€ть довольно значительное врем€, которое могло быть потрачено на разработку самого приложени€. “ем временем многие хранилища типа ключ-значение хран€т данные в такой структуре, котора€ отображаетс€ в объекты более естественно. Ёто может существенно уменьшить врем€ разработки.

ƒругие аргументы в пользу использовани€ хранилищ типа ключ-значение, наподобие Ђ–ел€ционные базы могут стать неуклюжимиї (кстати, € без пон€ти€, что это значит), €вл€ютс€ менее убедительными. Ќо прежде чем стать сторонником таких хранилищ, ознакомьтесь со следующим разделом.

’ранилища типа ключ-значение: недостатки


ќграничени€ в рел€ционных Ѕƒ гарантируют целостность данных на самом низком уровне. ƒанные, которые не удовлетвор€ют ограничени€м, физически не могут попасть в базу. ¬ хранилищах типа ключ-значение таких ограничений нет, поэтому контроль целостности данных полностью лежит на приложени€х. ќднако в любом коде есть ошибки. ≈сли ошибки в правильно спроектированной рел€ционной Ѕƒ обычно не ведут к проблемам целостности данных, то ошибки в хранилищах типа ключ-значение обычно привод€т к таким проблемам.

ƒругое преимущество рел€ционных Ѕƒ заключаетс€ в том, что они вынуждают вас пройти через процесс разработки модели данных. ≈сли вы хорошо спроектировали модель, то база данных будет содержать логическую структуру, котора€ полностью отражает структуру хранимых данных, однако расходитс€ со структурой приложени€. “аким образом, данные станов€тс€ независимы от приложени€. Ёто значит, что другое приложение сможет использовать те же самые данные и логика приложени€ может быть изменена без каких-либо изменений в модели базы. „тобы проделать то же самое с хранилищем типа ключ-значение, попробуйте заменить процесс проектировани€ рел€ционной модели проектированием классов, при котором создаютс€ общие классы, основанные на естественной структуре данных.

» не забудьте о совместимости. ¬ отличие от рел€ционных Ѕƒ, хранилища, ориентированные на использование в Ђоблакеї, имеют гораздо меньше общих стандартов. ’оть концептуально они и не отличаютс€, они все имеют разные API, интерфейсы запросов и свою специфику. ѕоэтому вам лучше довер€ть вашему вендору, потому что в случае чего, вы не сможете легко переключитьс€ на другого поставщика услуг. ј учитыва€ тот факт, что почти все современные хранилища типа ключ-значение наход€тс€ в стадии бета-версий2, довер€ть становитс€ еще рискованнее, чем в случае использовани€ рел€ционных Ѕƒ.

ќграниченна€ аналитика данных

ќбычно все облачные хранилища стро€тс€ по типу множественной аренды, что означает, что одну и ту же систему использует большое количество пользователей и приложений. „тобы предотвратить Ђзахватї общей системы, вендоры обычно каким-то образом ограничивают выполнение запросов. Ќапример, в SimpleDB запрос не может выполн€тьс€ дольше 5 секунд. ¬ Google AppEngine Datastore за один запрос нельз€ получить больше, чем 1000 записей3.

Ёти ограничени€ не страшны дл€ простой логики (создание, обновление, удаление и извлечение небольшого количества записей). Ќо что если ваше приложение становитс€ попул€рным? ¬ы получили много новых пользователей и много новых данных, и теперь хотите сделать новые возможности дл€ пользователей или каким-то образом извлечь выгоду из данных. “ут вы можете жестко обломатьс€ с выполнением даже простых запросов дл€ анализа данных. ‘ичи наподобие отслеживани€ шаблонов использовани€ приложени€ или системы рекомендаций, основанной на истории пользовател€, в лучшем случае могут оказатьс€ сложны в реализации. ј в худшем Ч просто невозможны.

¬ таком случае дл€ аналитики лучше сделать отдельную базу данных, котора€ будет заполн€тьс€ данными из вашего хранилища типа ключ-значение. ѕродумайте заранее, каким образом это можно будет сделать. Ѕудете ли вы размещать сервер в облаке или у себ€? Ќе будет ли проблем из-за задержек сигнала между вами и вашим провайдером? ѕоддерживает ли ваше хранилище такой перенос данных? ≈сли у вас 100 миллионов записей, а за один раз вы можете вз€ть 1000 записей, сколько потребуетс€ на перенос всех данных?

ќднако не ставьте масштабируемость превыше всего. ќна будет бесполезна, если ваши пользователи решат пользоватьс€ услугами другого сервиса, потому что тот предоставл€ет больше возможностей и настроек.

ќблачные хранилища


ћножество поставщиков веб-сервисов предлагают многопользовательские хранилища типа ключ-значение. Ѕольшинство из них удовлетвор€ют критери€м, перечисленным выше, однако каждое обладает своими отличительными фичами и отличаетс€ от стандартов, описанных выше. ƒавайте взгл€нем на конкретные пример хранилищ, такие как SimpleDB, Google AppEngine Datastore и SQL Data Services.

Amazon: SimpleDB

SimpleDB Ч это атрибутно-ориентированное хранилище типа ключ-значение, вход€щее в состав Amazon WebServices. SimpleDB находитс€ в стадии бета-версии; пользователи могут пользовать ей бесплатно Ч до тех пор пока их потребности не превыс€т определенный предел.
image
” SimpleDB есть несколько ограничений. ѕервое Ч врем€ выполнени€ запроса ограничено 5-ю секундами. ¬торое Ч нет никаких типов данных, кроме строк. ¬се хранитс€, извлекаетс€ и сравниваетс€ как строка, поэтому дл€ того, чтобы сравнить даты, вам нужно будет преобразовать их в формат ISO8601. “ретье Ч максимальные размер любой строки составл€ет 1024 байта, что ограничивает размер текста (например, описание товара), который вы можете хранить в качестве атрибута. ќднако поскольку структура данных гибка€, вы можете обойти это ограничени€, добавл€€ атрибуты Ђќписание“овара1ї, Ђќписание товара2ї и т.д. Ќо количество атрибутов также ограничено Ч максимум 256 атрибутов. ѕока SimpleDB находитс€ в стадии бета-версии, размер домена ограничен 10-ю гигабайтами, а вс€ база не может занимать больше 1-го терабайта.

ќдной из ключевых особенностей SimpleDB €вл€етс€ использование модели конечной констистенции (eventual consistency model). Ёта модель подходит дл€ многопоточной работы, однако следует иметь в виду, что после того, как вы изменили значение атрибута в какой-то записи, при последующих операци€х чтени€ эти изменени€ могут быть не видны. ¬еро€тность такого развити€ событий достаточно низка€, тем не менее, о ней нужно помнить. ¬ы же не хотите продать последний билет п€ти покупател€м только потому, что ваши данные были неконсистентны в момент продажи.

Google AppEngine Data Store

Google's AppEngine Datastore построен на основе BigTable, внутренней системе хранени€ структурированных данных от Google. AppEngine Datastore не предоставл€ет пр€мой доступ к BigTable, но может восприниматьс€ как упрощенный интерфейс взаимодействи€ с BigTable.
image
AppEngine Datastore поддерживает большее число типов данных внутри одной записи, нежели SimpleDB. Ќапример, списки, которые могут содержать коллекции внутри записи.

—корее всего вы будете использовать именно это хранилище данных при разработке с помощью Google AppEngine. ќднако в отличии от SimpleDB, вы не сможете использовать AppEngine Datastore (или BigTable) вне веб-сервисов Google.

Microsoft: SQL Data Services

image
SQL Data Services €вл€етс€ частью платформы Microsoft Azure. SQL Data Services €вл€етс€ бесплатной, находитс€ в стадии бета-версии и имеет ограничени€ на размер базы. SQL Data Services представл€ет собой отдельное приложение Ч надстройку над множеством SQL серверов, которые и хран€т данные. Ёти хранилища могут быть рел€ционными, однако дл€ вас SDS €вл€етс€ хранилищем типа ключ-значение, как и описанные выше продукты.

Ќеоблачные хранилища


—уществует также р€д хранилищ, которыми вы можете воспользоватьс€ вне облака, установив их у себ€. ѕочти все эти проекты €вл€ютс€ молодыми, наход€тс€ в стадии альфа- или бета-версии, и имеют открытый код. — открытыми исходниками вы, возможно, будете больше осведомлены о возможных проблемах и ограничени€х, нежели в случае использовани€ закрытых продуктов.

CouchDB

CouchDB Ч это свободно распростран€ема€ документо-ориентированна€ Ѕƒ с открытым исходным кодом. ¬ качестве формата хранени€ данных используетс€ JSON. CouchDB призвана заполнить пробел между документо-ориентированными и рел€ционными базами данных с помощью Ђпредставленийї. “акие представлени€ содержат данные из документов в виде, схожим с табличным, и позвол€ют строить индексы и выполн€ть запросы.
image
¬ насто€щее врем€ CouchDB не €вл€етс€ по-насто€щему распределенной Ѕƒ. ¬ ней есть функции репликации, позвол€ющие синхронизировать данные между серверами, однако это не та распределенность, котора€ нужна дл€ построени€ высокомасштабируемого окружени€. ќднако разработчики CouchDB работают над этим.

ѕроект Voldemort

ѕроект Voldemort Ч это распределенна€ база данных типа ключ-значение, предназначенна€ дл€ горизонтального масштабировани€ на большом количестве серверов. ќн родилась в процессе разработки LinkedIn и использовалась дл€ нескольких систем, имеющих высокие требовани€ к масштабируемости. ¬ проекте Voldemort также используетс€ модель конечной консистенции.

Mongo

image
Mongo Ч это база данных, разрабатываема€ в 10gen √ейром ћагнуссоном и ƒуайтом ћеррименом (которого вы можете знать по DoubleClick).  ак и CouchDB, Mongo Ч это документо-ориентированна€ база данных, хран€ща€ данные в JSON формате. ќднако Mongo скорее €вл€етс€ объектной базой, нежели чистым хранилищем типа ключ-значение.

Drizzle

image
Drizzle представл€ет совсем другой подход к решению проблем, с которыми призваны боротьс€ хранилища типа ключ-значение. Drizzle начиналс€ как одна из веток MySQL 6.0. ѕозже разработчики удалили р€д функций (включа€ представлени€, триггеры, скомпилированные выражени€, хранимые процедуры, кэш запросов, ACL, и часть типов данных), с целью создани€ более простой и быстрой —”Ѕƒ. “ем не менее, Drizzle все еще можно использовать дл€ хранени€ рел€ционных данных. ÷ель разработчиков Ч построить полурел€ционную платформу, предназначенную дл€ веб-приложений и облачных приложений, работающих на системах с 16-ю и более €драми.

–ешение


¬ конечном счете, есть четыре причины, по которым вы можете выбрать нерел€ционное хранилище типа ключ-значение дл€ своего приложени€:
  1. ¬аши данные сильно документо-ориентированны, и больше подход€т дл€ модели данных ключ-значение, чем дл€ рел€ционной модели.
  2. ¬аша доменна€ модель сильно объектно-ориентированна, поэтому использовани€ хранилища типа ключ-значение уменьшит размер дополнительного кода дл€ преобразовани€ данных.
  3. ’ранилище данных дешево и легко интегрируетс€ с веб-сервисами вашего вендора.
  4. ¬аша главна€ проблема Ч высока€ масштабируемость по запросу.

ќднако принима€ решение, помните об ограничени€х конкретных Ѕƒ и о рисках, которые вы встретите, пойд€ по пути использовани€ нерел€ционных Ѕƒ.

ƒл€ всех остальных требований лучше выбрать старые добрые рел€ционные —”Ѕƒ. “ак обречены ли они?  онечно, нет. ѕо крайней мере, пока.

»сточник: habrahabr.ru

-
SQL Foreign Key - 17.07.2012
GIF89a/uА€€€!щ,/u@€МП©Ћн£ЬіЏЛ≥ёЉыЖ@јqЪ®Ь•K∆пЪґвНзъќчNн ЗƒҐ<*Чћ¶3Т|JІЙ(хКЌJJYЂц ÷r±ё∞щћoMЃЂS•f,vЭЖѓѕЂиюy/'gгWhxИИTЦ»Ўиhч)…®6iyЙЩ©Й»’¶чўў≤G*HJЪ*ЄЄщ KЅ:шfУд9:Чл*лыџы+<\L|МЉ`ЬLиь -=M]m}НЭ≠љЌЁнљ\ќ<~S9%NЮоaЃёоќј™З:zл&W ;_ ъЫ™ї5 ,Иp“ЅД -l1CЉ]1D™GWF€7 иWЇИ$KЪ<Й2•JQt≤з…Ю*Ш4WЏƒр ЌЭбxъ|2тІPAЗЁPф®R IЧ:’щTD”®Ік∞JхRN%X≥*мZќЂї≠GјКuDцђZ≠k)Е|иЮВ61EВ¬£ПЯ≠Z2_b|ў÷HЂ{їо≈81<≥Кy¶mЬх1д®Т';≠lY)жћF7sкщ≥и—Йиv3xРi√~яжЩєсНk“С≥¶Нін№∆|LЁqпяАЉeµіХo_.д4wГЪєкU∞OЙЇэ -
SQL Foreign Key

SQL Foreign Key

FOREIGN KEY - в одной таблице указывает на другой PRIMARY KEY.

ѕосмотрите на две следующие таблицы:

≈сть таблица "Persons":

P_IdLastNameFirstNameAddressCity
1 Hansen Ola Timoteivn 10 Sandnes
2 Svendson Tove Borgvn 23 Sandnes
3 Pettersen Kari Storgt 20 Stavanger

≈сть таблица "Orders":

O_IdOrderNoP_Id
1 77895 3
2 44678 3
3 22456 2
4 24562 1

«аметим что колонка "P_Id" в таблице "Orders" указывает на "P_Id" в таблице "Persons".

 олонка  "P_Id" в таблице "Persons" €вл€етс€ PRIMARY KEY.

 олонка  "P_Id" в таблице "Orders" €вл€етс€ FOREIGN KEY.

FOREIGN KEY не позвол€ет вставл€ть неверные данные в колонку "P_Id" в таблице "Orders" и "Persons".

SQL FOREIGN KEY ќграничени€ при CREATE TABLE

—ледующие SQL создает FOREIGN KEY в колонке "P_Id", при создании таблицы "Orders":

MySQL:

CREATE TABLE Orders (
O_Id int NOT NULL,
OrderNo int NOT NULL,
P_Id int,
PRIMARY KEY (O_Id),
FOREIGN KEY (P_Id) REFERENCES Persons(P_Id)
)

SQL Server / Oracle / MS Access:

CREATE TABLE Orders (
O_Id int NOT NULL PRIMARY KEY,
OrderNo int NOT NULL,
P_Id int FOREIGN KEY REFERENCES Persons(P_Id)
)

ћожно распределить ограничитель FOREIGN KEY на несколько столбцов, дл€ этого используйте следующий синтаксис SQL:

MySQL / SQL Server / Oracle / MS Access:

1
2
3
4
5
6
7
8
CREATE TABLE Orders(
O_Id int NOT NULL,
OrderNo int NOT NULL,
P_Id int,
PRIMARY KEY (O_Id),
CONSTRAINT fk_PerOrders FOREIGN KEY (P_Id)
REFERENCES Persons(P_Id)
)

SQL FOREIGN KEY ќграничени€ при ALTER TABLE

—ледующие SQL создает FOREIGN KEY в колонке "P_Id", когда таблица "Orders" уже создан:

MySQL / SQL Server / Oracle / MS Access:

1
2
3
ALTER TABLE Orders
ADD FOREIGN KEY (P_Id)
REFERENCES Persons(P_Id)

ћожно распределить ограничитель FOREIGN KEY на несколько столбцов, дл€ этого используйте следующий синтаксис SQL:

MySQL / SQL Server / Oracle / MS Access:

1
2
3
4
ALTER TABLE Orders
ADD CONSTRAINT fk_PerOrders
FOREIGN KEY (P_Id)
REFERENCES Persons(P_Id)

”даление FOREIGN KEY

ƒл€ удалени€ ограничител€ FOREIGN KEY используйте следующий SQL:

MySQL:

1
2
ALTER TABLE Orders
DROP FOREIGN KEY fk_PerOrders

SQL Server / Oracle / MS Access:

1
2
ALTER TABLE Orders
DROP CONSTRAINT fk_PerOrders

»сточник: dmitry.dn.ua

-
–ел€ционна€ модель данных дл€ больших совместно используемых банков данных - 17.07.2012
–ел€ционные базы данных обречены? - 17.07.2012
—сылочна€ целостность €вл€етс€ важной дл€ баз данных - 17.07.2012

Secure

Security

XSS новичкам. ѕредназначение XSS-атак - 16.11.2011
Ћикбез по у€звимост€м в веб-приложени€х, а также самые частые ошибки разработчиков - 16.11.2011

apache

ћодуль Apache mod_rewrite - 07.02.2012

asterisk

—оздание Skype - SIP гейта (sip voip skype asterisk) - 09.03.2012
”становка и настройка Asterisk 1.6 на Debian - 09.03.2012

cron

–абота по расписанию во FreeBSD - 03.01.2012

dhcp

ups

ѕрикручивание бесперебойника Smart-UPS APC-1500 к FreeBSD - 09.09.2011