Сайт Информационных Технологий

A.S. Druzhinin

Russia, St-Petersburg, SP.ARM, andrew@sparm.com

FORMAL NAMES AS APPROACH TO DATA STRUCTURING

Abstract. Considerations on several approaches to data structuring using formal names and associated methods are discussed in this article.

 

А.С.Дружинин

Россия, Санкт-Петербург, СП.АРМ, andrew@sparm.com

ФОРМАЛЬНЫЕ ИМЕНА КАК СПОСОБ СТРУКТУРИРОВАНИЯ ДАННЫХ

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

Информация=структурированные данные + соответствующие методы работы с ними.

Смысл этого утверждения состоит в том, что сама структура данных является не менее важной, чем собственно данные, т.е. также несет в себе семантически значимую информацию. Поэтому вопрос, каким способом структурировать данные, представляется весьма значимым. Один из таких подходов, интенсивно развиваемых в настоящее время - расширяемый язык разметки XML и связанные с ним технологии - XSL, XQL. Не менее важным представляется и набор методов, который предлагается для работы со структурированными данными. В настоящей статье приводится ряд соображений о способах структуризации данных с помощью формальных имен и необходимых методах работы с этими именами.

Представляется, что во многих случаях наблюдается дисбаланс между используемыми структурами данных и методами работы с этими структурами. Например, SQL представляет весьма бедные сами по себе структуры данных (плоские таблицы) и весьма развитый язык запросов к данным. XML, наоборот, предлагает весьма развитые средства описания структур данных, но не включает вообще никаких методов работы с этими структурами. Объектные СУБД в принципе предлагают потенциально богатые структуры данных в совокупности с методами, но эти методы, как правило, предназначены для работы с уже имеющимися данными, а не для их структуризации.

Данные сами по себе образуют некоторое множество. Для того, чтобы работать с ними, необходимо каким-то образом нумеровать (именовать) элементы этого множества (или его подмножества). В результате такой операции образуется уже два множества: исходное и множество имен, между которыми существует некоторое отображение. Основная идея заключается в том, что очень часто гораздо проще работать не с исходным множеством, а с каким-то другим его образом. Важным является лишь сохранение некоторых инвариантных сущностей, В математике это является рутинной операцией, и применяется повсеместно. Как правило, вместо исходного множества берется тот его образ, с которым в некотором смысле "удобнее" работать в данной конкретной ситуации. Примером может служить операционное исчисление Хевисайда, когда дифференцированию исходной функции соответствует умножение на аргумент. Еще более типичный пример - это преобразование матрицы общего вида к некоторому специальному виду - диагональному, жордановой форме, треугольной, трехдиагональной и т.п. В случае диагонализации матрицы вместо n2 параметров (значений элементов матрицы) существенными оказываются только n (собственные числа), а собственные вектора матрицы образуют "естественный" базис.

Одним из более близких по теме примеров реализации разного именования одних и тех же сущностей дает объектная модель HTML-страницы, реализованная в Intmet Explorer'e. Допустим, имеется таблица с id="MyTable. Тогда семейство этих строк может быть представлено несколькими способами:

document.all["МуТаЫе"]rows

document.all["MyTable"].all.tags("tr")

Естественно, эта идея является далеко не новой, и повсеместно применяется в программировании. В "хороших" языках программирования имеются развитые средства создания фактически произвольных структур данных из некоторых атомарных типов. Как правило, в языках компилирующего типа, эта структура жестко задается на стадии описания, и не может быть изменена при работе программы. В интерпретирующих языках имеется возможность динамического создания структур данных. Однако во многих случаях это не подкрепляется достаточным набором операций работы с собственно именами как таковыми. Рассмотрим типичную ситуацию:

Имя=3начение

В подавляющем большинстве случаев к имени применяется всего две операции:

Get (Имя) - взять значение имени

Put (Имя) - дать значение имени.

В "хороших" языках программирования появляются дополнительные возможности по работе с именами:

New Имя - создать новое имя

Kill Имя - уничтожить имя

Само имя может быть “переменным”, т.е. содержать в своем составе как литералы, так и другие имена, быть структурированным. В качестве примеров можно привести массивы или объектные ссылки:

Array[i,j]

Obj[Ref].Prop

Как только мы допускаем структурированность имени, так неизбежно должен появиться набор операций, позволяющий работать с отдельными атомами структурированного имени. Оставим на время эту богатую тему, и посмотрим, для чего могут применяться структурированные имена. Как нетрудно догадаться, для структурирования данных. Если некоторым именам соответствуют значения, то мы получаем отображение множества значений на множество имен, а поскольку, как уже упоминалось, это отображение мы вольны выбирать сами для нашего же удобства, то и вложим в структуру имени структуру данных. Более того, никто не утверждал, что все данные должны образовывать одно большое множество. Поэтому часть данных мы имеем полное право разместить в множестве имен. Нетрудно видеть, что обычно тот атом структурированного имени, который заключается в [], и представляет собственно некоторые данные, хотя это и необязательно.

Теперь, когда у нас есть два множества, никто не мешает нам рассматривать множество имен как обычное множество значений, и в свою очередь проименовать и его, и так далее. Эта конструкция также повсеместно применяется в виде указателей, ссылок, и т.п. Вообще говоря, это как раз и позволяет по разному структурировать одни и те же данные в зависимости от задачи. Механизмы же, применяемые в разных СУБД и языках программирования для реализации этого "переименования" весьма различны, и, как представляется, недостаточно общи. Например, в SQL это запросы, для реализации которых предложено множество всяких команд, ключевых параметров и т.д. В XML-XSL дело обстоит уже гораздо лучше, но, тем не менее, также используется огромное количество частных атрибутов, видов селекторов, правил и т.п. В JavaScript дело обстоит несколько лучше, но и там имеются свои недостатки, связанные с жесткой ориентацией этого языка на обслуживание HTML. Да этот язык и не предназначен для обслуживания СУБД.

Для практических применений наиболее важными являются два типа имени:

1. Имя элемента множества - "простое" имя.

2. Имя подмножества (коллекции) - "параметрическое" имя. Для любого такого имени должен существовать метод перечисления всех членов коллекции.

Первый тип имен интересен лишь в том случае, когда он является экземпляром параметрического имени. Второй тип имен в принципе позволяет производить операции над множествами объектов, т.е. осуществлять то, для чего и придуманы базы данных.

Рассмотрим ситуацию на примере объектного синтаксиса. В объектной парадигме естественным образом имеются следующие типы атомарных имен, из которых могут получаться структурированные имена:

Могут порождаться следующие типы структурированных имен:

Как только мы допускаем, что некоторые свойства (Prop) на самом деле могут быть атомами типа Obj, то автоматически получается деревянная структура, определяемая следующими формальными правилами:

StrAtom: := строка символов, не содержащая символов-разделителей (.,[]())

Prop::=StrAtom

ObjRef::=StrAtom

Obj::=StrAtom|Obj.Obj|0bj[ObjRef].Obj

Method::=StrAtom()

Заметим, что потенциально конструкция Obj .Method (Parm1, Parm2, . . .) также может применяться для образования имен-коллекций.

К именам разного типа можно применять разные операции, например, к свойству экземпляра объекта применимы операции Get и Put, к экземпляру объекта - New и Kill, к методу - Xecute (выполнить). Но наибольший интерес для нас представляют операции собственно со структурированным именем. Очертим их примерный круг. Во-первых, это операции, позволяющие разобрать структурированное имя на атомы и установить тип каждого атома. Во-вторых, это операции, позволяющие определить "родственников" данного имени. Этих "родственников" всего два типа - "Отец" (всегда один, поскольку это дерево), и "братья"-"сыновья". В-третьих, это операции порождения новых корректных имен, и, возможно, присваивания им значений.

Таким образом, весьма естественным представляется наличие следующих операций(методов), применяемых к структурированному имени:

1. Имя. Parent ( ) - выдает имя "отца" данного имени

2. Имя. Children ( ) - имя коллекции сыновей данного имени. Применяется, как было сказано выше в контексте метода перечисления сыновей данного имени, детали реализации которого не столь важны. Например, это может быть такая конструкция NextChild=CurrChild.Brother ( ).

Представляется, что такая простая модель позволяет интегрировать достоинства иерархической, реляционной и объектной модели данных. Опишем, например, как просто организуется реляционный словарь для любого объекта (или реализующего его иерархического дерева-хранилища). Имеется один-единственный дополнительный объект- cлoвapь(Dict), экземпляры которого образуются из атомарных имен и значений атрибутов экземпляра объекта по следующему формальному правилу:

Obj[ObjRef].Prop=Value

Dict[Prop][Value][Obj][ObjRef]=" "

Первая совокупность имен предназначена для хранения значений атрибутов экземпляров объектов, вторая позволяет осуществлять быстрые поиски ссылок на экземпляры объектов, т.е. выделять требуемые подмножества в исходной БД.

Второй пример - реализация отношения в виде формального имени. Пусть, например, имеется тернарное отношение, связывающее три объекта (объект, как нетрудно видеть, если пренебречь методами есть, просто реляционная таблица). Тогда устраиваем следующую формальную конструкцию объектного типа:

Join групповое имя для объекта отношения
Join[Ref] экземпляр отношения
Join[Ref].Parm[i] параметры отношения
Join[Ref].ObjA коллекция экземпляров первого объекта
Join[Ref].ObjB коллекция экземпляров второго объекта
Join[Ref].ObjC коллекция экземпляров третьего объекта
Join[Ref].ObjA.PropGet()= метод получения значений свойств атрибутов
ObjA[RefA].PropGetO экземпляра объекта ObjA

 

Естественно, у этого объекта должны быть определены стандартные методы перечисления членов имен-коллекций Join[Ref] .ObjA{B,C, . . .}, и, возможно, метод типа "Создать", применение которого реально создает соответствующие коллекции ссылок на экземпляры объектов. Следует отметить, что до поры до времени нет никакой необходимости в реальном наличии сыновей у Join[Ref] .ObjA и т.д., т.е. экземпляров объектов, удовлетворяющих отношению. Тем не менее, мы можем писать выражения с именами, ссылающимися на значения свойств атрибутов этих экземпляров. В частности, таким образом можно реализовывать подзапросы произвольной глубины вложенности. На самом деле, как только мы определили все необходимые атрибуты собственно объекта-отношения (параметры отношения), имя может считаться полностью определенным, но виртуальным. Более того, во многих случаях можно извлечь выгоду из этой виртуальности, не вычисляя (не порождая), например, совокупность ссылок на конкретные экземпляры объекта ObjC, если они по какой-то причине не нужны в дальнейших вычислениях.

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

Y=F (X)

F - совокупность правил (методов) вычисления значения атрибутов экземпляров объекта Y, Х - область определения (совокупность ссылок на экземпляры объектов, из значений атрибутов которых будут построены экземпляры новых объектов). Сама область определения может быть также описана некоторым символическим именем + метод перечисления ее отдельных компонент.

Заметим, что есть и языки, и СУБД, в которых имеются вышеупомянутые операции с именами. Примером может служить СУБД Cache (подробности см. www.intersys.iu www.sparm.com, а также в книге В.Кирстен, М.Ирингер, П.Шульте "Объектно- ориентированная разработка приложений в среде постреляционной СУБД Cache") и применяемый в ней язык CacheObjectScript. Там реализован мощный базовый набор средств работы со структурированными именами, в принципе позволяющий реализовать изложенный выше подход.

Резюме.

Формальные имена молекулярной структуры представляются удобным способом структурирования данных. Для реализации преимуществ этого способа в языке должны присутствовать развитые методы работы с именами.

Подробный вариант статьи см. www.sparm.com/science/sname.htm


Site of Information Technologies
Designed by  inftech@webservis.ru.