фрази визначає базовий клас, для об'єктів якого визначається запит;
• for, що обмежує умовами на дані кожного з деяких окремих класів;
• links, визначальною зв'язку класів;
• where, що обмежує умовами на дані різних класів.
Спрощений мову SODQL-запитів (верхнього рівня) опускає фразу links і може не містити фрази from. У цьому випадку базовий клас визначається за першим даним фрази select, а всі інші дані ODQL-запиту виходять при побудові схеми шарів. Схема шарів визначається алгоритмом, наведеним в [4] по класах даних фрази select і зв'язків цих класів один з одним послідовно, починаючи від базового класу. При цьому будуються фрази from і links, що фіксують порядок класів і зв'язків у схемі шарів. Тому можна вважати, що схема шарів запиту записана в одержуваному або перетвореному ODQL-запиті.
Рис. 7. Схема шарів (представлені 2 шари: верхній з базовим класом і наступний)
Ідея алгоритму виконання запиту [5] полягає в тому, що для кожного класу, що бере участь у запиті, створюється індекс-вибірка [5]. Потім, рухаючись по схемі верств [4] від шару з максимальним рівнем до нульового (до базового класу), ми встановлюємо індекс-вибірки відносин класів [5].
Реалізація індекс-вибірок за допомогою динамічної пам'яті неможлива, так як її покажчики мають бути пов'язані з вузлами індексних дерев, що знаходяться в зовнішній пам'яті. Тому для реалізації індекс-вибірки класу використовуються поля таблиці об'єктів класу: Mark (для позначки об'єкта), NextldObject із зовнішнім індексом до цієї ж таблиці (для організації списку індекс-вибірки), а також поле MarkList записи класу в таблиці Class (для позначки переліку індекс вибірки). Для реалізації індекс-вибірки відносини об'єктів класів в таблиці зв'язку об'єктів цих класів використовуються пов'язані з нею зовнішні індекси на відповідні об'єкти таблиць об'єктів обох класів, що дає можливість організувати алгоритм корекції індекс-вибірок класів.
Алгоритм використання індекс-вибірок пов'язаний з початковим встановленням індекс-вибірок класів по фразі for запиту [6], [5]. Потім при русі по схемі верств класів від самого нижнього шару до самого верхнього (базового класу запиту) по індекс-вибірках відносин більш нижнього у схемі класу зі зв'язаним з ним більш верхнім класом схеми коригується індекс-вибірка останнього класу. Трудомісткість цього алгоритму, як показано в [5], мінімально можлива (евристично).
Третій етап алгоритму виконання запиту полягає в отриманні «дерев» (це може бути ациклічний граф) об'єктів запиту, в кожному з яких для поміченого об'єкту базового класу запиту будується дерево його даних, що визначаються фразою select запиту і задовольняють умовам фрази where запиту. Реалізація цього відбувається при русі вниз від кожного з об'єктів базового класу схеми шарів з перевіркою умов фрази where запиту.
Зробимо ще 2 зауваження.
1. Етап корекції індекс-вибірок класів ми можемо починати тільки від тих класів, що знаходяться в нижніх шарах схеми, які містять не всі помічені об'єкти. Для ц...
