Организация электронной библиотеки с учетом принципов оптимизации реляционных СУБД

§ 0.1. Состояние вопроса.

Одним из важнейших событий, ознаменовавших собой окончание XX века, по праву можно назвать наступление информационной революции. Этот факт довольно часто отмечается в трудах как зарубежных, так и отечественных социологов, обществоведов и специалистов по информационным технологиям [1, 3, 14, 20−23, 32].

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

В последние несколько лет благодаря технологии World Wide Web [3, 7, 23, 49] появилась возможность легко получать доступ не только к библиографической и полнотекстовой, но также к красочной графической и даже аудиовизуальной информации, находящейся на удаленных компьютерах. Уже привычными становятся электронные газеты и журналы, многие из которых во многом повторяют внешний вид своих печатных собратьев, включая цветные фотографии и особенности оформления. Электронные книги также находят все более широкое распространение. В информационной вселенной существует множество музеев, содержащих электронные репродукции полотен великих художников прошлого и современности.

Таким образом, электронное информационное пространство существует и стремительно развивается, образуя как бы параллельный мир традиционной коммуникационной инфраструктуре, включающей такие информационные институты как издательства, средства массовой информации в виде печатных периодических изданий, радио и телевидения, библиотеки, архивы, книжные магазины и т. д. Несомненно, что уже в скором времени ситуация в информационной сфере может серьезно измениться под воздействием новых технологий, что скажется на изменении привычных функций информационных институтов. Естественно, что библиотеки как одни из ведущих субъектов информационной деятельности испытают качественные преобразования под воздействием новых условий.

Природа изменений в библиотеке как информационном учреждении предопределяется и теснейшим образом связана с изменениями в сфере документальных коммуникаций, частично описанными в [1, 10, 11, 14, 21, 32], поскольку сегодня библиотеки ориентированы, прежде всего, на работу с массивами документов. Главные события в этой области будут связаны с тем, что компьютеризация издательских процессов приведет к повсеместному распространению электронной печати. Тогда практически все периодические издания, монографии, сборники, справочники, словари и энциклопедии, выполненные в привычной ныне форме на бумажном носителе, будут иметь своих компьютерных «двойников», т. е. будут представлены также и в виде компьютерных файлов. Помимо этого уже появляются издания, существующие только в электронной форме на CD-ROM или подобном носителе или/и доступные по глобальной сети [1].

Как отмечают некоторые аналитики, в настоящее время этот процесс несколько сдерживается не столько технологическими проблемами, сколько недостаточно отрегулированной работой законов об авторском праве на электронные издания, проблематичностью оплаты их использования. Однако, по нашему мнению, во многих странах законодательство уже предусматривает защиту прав авторов электронных публикаций, а вопросы оплаты решаются путем применения электронных кредитных карт. Можно надеяться, что в скором времени юридические и финансовые вопросы будут урегулированы повсеместно. Что касается аппаратного обеспечения, в последние годы персональные компьютеры становятся все доступнее для подавляющего большинства населения, как по своей стоимости, так и по стоимости машинного времени. То же самое можно сказать и об использовании компьютерных сетей. Очевидные же преимущества электронной печати, заключающиеся в компактности хранения информационного массива, его оперативном обновлении, относительной дешевизне и, конечно же, в предоставлении пользователям таких дополнительных возможностей как сочетание текста, звука и видеоизображения обеспечивают ей гарантию широчайшего распространения. Еще одно важное достоинство — возможность для пользователя получить информацию в любое удобное для него время и без «физического» обращения в библиотеку, например, на своем домашнем или рабочем компьютере, имеющем связь с глобальной сетью. Более подробно преимущества электронной библиотеки с точки зрения пользователя автор описывает в [11].

Несмотря на радужные перспективы и неоспоримые достоинства электронной информации, современное состояние дел в области организации электронных библиотек оставляет желать лучшего. В настоящее время в сети Internet представлено немалое количество публичных и научных библиотек, однако, подавляющее большинство из них ограничивается опубликованием электронного каталога, при помощи которого можно лишь убедиться в наличии необходимого материала в библиотеке. Зачастую этот электронный каталог является неполным, малофункциональным и неудобным с точки зрения пользователя, вызывая неприятие у посетителей сервера библиотеки. Тотальный перевод всех видов публикаций на электронную основу и создание удобных электронных каталогов должны резко увеличить популярность электронных библиотек, и если решение первой из этих двух проблем — вопрос времени, то решение второй требует определенных затрат от разработчиков моделей, программистов и библиотекарей.

1. На основе построенной модели спроектирован каталог универсальной электронной библиотеки с использованием СУБД Paradox с учетом принципов оптимизации реляционных СУБД и предполагаемых запросов.

2. Разработана схема доступа к каталогу электронной библиотеки путем организации оптимальных запросов на языке SQL на основе заполняемых пользователем стандартной и расширенной форм запросов.

3. Автоматизированные информационные ресурсы России. Состояние и тенденции развития. // Национальный доклад. Научнотехническая информация. Серия 1. 1994. — № 11. — С. 2−30.

4. Атре Ш. Структурный подход к организации баз данных. М.: Финансы и статистика, 1983. — 320 с.

5. Бабушкин М., Иваненко С., Коростелев В. Web-сервер в действии. СПб.: Питер, 1997. — 272 с.

6. Бойко В. В., Савинков В. М. Проектирование баз данных информационных систем. М.: Финансы и статистика, 1989. -351 с.

7. Грофф Дж. Р., Вайнберг П. H. SQL: Полное руководство. Киев: BHVСпарк, 1998. — 608 с.

8. Дадли К. Соответствие стандарту SQL. // Мир Oracle, 1996. № 1 (39). Январь март. (Перевод на русский язык). — С. 7−16.

9. Дайсон П. Web-узел на базе Microsoft Internet Information Server: Пер. с англ. яз. М.: Мир, 1997. — 591 с.

10. Дейт К.

Введение

в системы баз данных: Пер. с англ. М.: Наука, 1980. — 463 с. •.

11. Дискретная математика и математические вопросы кибернетики. / Под общей ред. C.B. Яблонского и О. Б. Лупанова. Т.1. М.: Наука, 1974. •.. vЮ. Дунаев С. Доступ к базам данных и техника работы в сети. М.: Диалог-МИФИ, 1999— 416 с.

12. Жильцов А. Е. Подход — к^ организации специализированных электронных библиотек. —VНИИ вычислит, математики и процессов управления. С.-Петерб. ун-т. С.-Петерб., 1999. Деп. вВИНИТИ 16.12.99, № 3752-В99. 8 с.

13. Кнут Д. Искусство программирования для ЭВМ. Т. З. Сортировка и поиск: Пер. с англ. М: Мир, 1978. — 848 с.

14. Кузнецов С. Д.

Введение

в СУБД. // Системы управления базами данных. Открытые системы, 1995. — № 1−4: 1996.-№ 1−6.

15. Ланг К., Чоу Дж. Публикация баз данных в Интернете: Пер. с англ. яз. СПб.: Символ-Плюс, 1998. -480 с.

16. Мейер М. Теория реляционных баз данных. М.: Мир, 1987. -608 с.

17. Минаси М. Графический интерфейс пользователя. Секреты проектирования. М.: Мир, 1996. — 159 с.

18. Салседо. Paradox. Методы программирования: Пер. с англ. М.: Радио и связь, 1996.

19. Степанов В. К. Информационная эра: Завтра? Сегодня? Сейчас!- Кафедра Общего библиографоведения МГУК, М., 1996.-21. Субботин М. М. Гипертекст. Новая форма письменной коммуникации. // Итоги науки и техники. Серия: Информатика. -. 1994. № 18. С. 1−157.

20. Тиори Т., Фрай Дж. Проектирование структур баз данных. В 2 кн., — М.: Мир, 1985. Кн. 1. 287 е.: Кн. 2. 320 с.

21. Уолл Д. А. Использование World Wjde Web. Киев: Диалектика, —. — 1997. 384 с.

22. Хансен. Базы данных. Разработка и управление: Практическое пособие для специалистов. М.: Бином, 1999. — 704 с.

23. Чаудхари С. Методы оптимизации запросов в реляционных системах. // Системы управления базами данных. Открытые системы, 1998. — № 3.

24. Шамис В. А. Borland С++ Builder. Программирование на С++ без проблем. М.: «Нолидж», I997. — 266 е., ил.

25. Шилд Г. Программирование. на BORLAND С++: Для профессионалов. Минск: Попурри, 1999. — 800 с.

26. Abitboul S., Scholl M., Gardarin G., Simon E. Towards DBMSs for Supporting New Applications. // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25−28, 1986. Los Altos, Calif., 1986. С. 423−435.

27. Aho A.V., Sagiv Y., Ullman J.D. Efficient Optimization of a Class of Relational Expressions, // ACM Trans. Database Syst. 1979. — Vol. 4, № 4.-C. 435−454.

28. Aho A.V., Sagiv Y. s Ullman J.D. Equivalence of Relational Expressions. // SIAM J. Comput. 1979. — Vol. 8, № 2. — C. 218 246. :

29. Astrahan M.M., Schkolnick M., Whang K.Y. Counting Unique Values of an Attribute without Sorting. // Inf. Syst. 1987. -Vol. 12, № 1. C. 11−16.

30. Barker Philip. Electronic Libraries: The Future. // Electron. Libr., ^ 1994,-Vol. 12, № 4.-C. 221−230.

31. Bell D.A. Issues in Relational Database Performance. // Data and Knowledge Eng. -1988. Vol. 3, № 1. — C. 46−61.

32. Bergamaschi S., Scales M.R. Choice of the Optimal Number of Blocks for Data Access by an Index. // Inf. Syst. 1986. Vol. 11, № 3i- / C, 199−209.

33. Blasgen M.W., Eswaran K.P. Sforage and Access in Relational Data • Bases. // IBM Syst. J., 1977. Vott6^№ X — C. 363−377.

34. Bodorik P., Riordon J.S. Distributed Query Processing OptimizationObjectives. // 4th Int. Conf. Data Eng., West Berlin, Sept. 13−15, 1988. New York, 1988.-C. 320−329.

35. Bultzingsloewen G. Translating and Optimizing SQL Queries Having Aggregates. // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif., 1987. C. 235−244.

36. Ceri S., Gottlob G. Translating SQL into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. /7 IEEE Trans, on Software Eng. -1985. Vol. 11, № 4. — C. — 324−345.

37. Ceri S., Gottlob G., Lavazza L. Translation and Optimization of Logic Queries: The Algebraic Approach. // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. C. 395−402.

38. Chakravarthy U.S., Fishman D.H., Minker J. Semantic Query Optimization in Expert Systems and Database Systems. // Expert Database Syst.: Proc. 1st Int. Workshop, Menlo Park, Calif., Feb. 1986. New York, 1986. C. 326−341.

39. Chandra A.K., Merlin P.M. Optimal Implementation of Conjuctive Queries in Relational Databases. // Proc. 9th Ann. ACM Symp. Theory of Comput., New York, May 1976. New York, 1976. C. 7790.

40. Christodoulakis S. Estimating Record Selectivities. // Inf. Syst. — 1983. — Vol. 8, № 2. C. 105−115.

41. Christodoulakis S. Estimating Block Selectivities. // Inf. Syst. 1984. -Vol. 9, № 1. — C. 69−79.

42. Codd E.F. An Evaluation Scheme for Database Management Systems that are Claimed to be Relational. // Proc. IEEE CSInternational Conference, № 2 onData Engineering, Los Angeles, /" February 1986.

43. Cornell D.W., Yu P. S. A Vertical Partitioning Algorithm for Relational Databases. // 3rd Int. Conf. Data Eng., Los Angeles, Ca, Febr. 3−5,951 987. Proc. Washington, D.C., 1987.-С. 30−35.

44. DeWitt D.J., Katz R.H., Olken F., Shapiro L.D., Stonebraker M.R., Wood D. Implementation Techniques for Main Memory Database Systems. // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., June 18−21, 1984. New York, 1984. C. 1−8.

45. Finkelstein S., Schkolnick M., Tiberio P. Physical Database Design for Relational Databases. // ACM Trans. Database Syst. 1988. -Vol. 13, № 1.-C. 91−128.

46. Freytag J.С., Goodman N. Translating Aggregate Queries into Iteractive Programs. // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. -C. 138−146.

47. Gilster P. Навигатор Internet. // ComputerWeek (Moskow). 1995. — № 19. -C.1,17−20.

48. Graefe G. Query Evaluation Techniques for Large Databases. //ACM Computing Surveys. June 1993,-Vol, 25, № 2.

49. Grazzini E., Pinzani RM Pippolini F. A Physical Structure for Efficient Processing of Relational Queries. // Pound. Data Organ. Proc. Int. Conf., Kyoto, May 22−24, 1985. New YorkLondon, 1987. C. 501 514.

50. Hall P.A.V. Optimization of a Single Relational Expression in a Relational Data Base System. // IBM J. of Res' and Dev. -1976. Vol. 20, № 3. C. 244−257.

51. Hagmann R.B. An Observation on Database Buffering Performance Metrics. // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Л Aug. 1986, Los Altos, Calif., 1986: —С— 289−293.

52. Hawthorn P., Stonebraker M.R. Performance Analisys of Relational Data Base Management System. // Proc. ACM SIGMOD Int. Conf.Manag. Data, Boston, Mass., Mayv30 ^ June: 1- 1979. New York, 1979.-C. 1−12. '.

53. Hiyoshi S., Mizuma M., Watanabe M. Hierarchical OptimizationStrategy for Query Evaluation. // NEC Res. and Dev. 1984. — № 12.-C. 48−55.

54. Jarke M., Koch J. Query Optimization in Database Systems. // ACM Computing Surveys.-1984.-Vol. 16, № 2.-C. 111−152.

55. Jhingram A. A Performance Study of. Query Optimization Algorithms on a Database System Supporting Procedural Objects. // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988,-C. 88−99.

56. Kiessling W. Access Path Selection in Databases with Intelligent Disc Subsystems.//Comput. J. 1988.-Vol. 31, № 1.-C. 41−50.

57. Kim W. Global Optimization of Relational Queries: A First Step // Query Processing in Database Systems. New York: Springer.- 1985. — C. 206−216.

58. Kim W. On Optimizing an SQL-Like Nested Query // ACM Trans. Database Syst. 1982. — Vol. 7, № 3. — C. 443−469.

59. King J.J. QUIST: A System for Semantic Query Optimization in. Relational Databases. // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3−11, 1981. New York, 1981.-C. 510−517.

60. Krishnamurthy R., Boyal H., Zaniolo C. Optimization of Nonrecursive Queries.- // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. CM 28−137.

61. Lee M, Freytag J., Lohman G. Implementing an Interpreter for Functional Rules in a Query Optimizers. // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, V Calii, 1988, -C. 218−229. /;

62. Lee S., Han J. Semantic Query Optimization in Recursive Databases 4th Int. Conf. Data Eng., West Berlin, Sept: T3−15, 1988. New York, 1988.-C. 444−451. .

63. Lorie R.A., Nilsson J.F. An Access Specification Language for a Relatiomal Data Base System. // IBM J. Res. and Dev. 1979. Vol.23, № 3.-C. 1−13.

64. Luk W.S. On Estimating Block Accesses in Database Organization. // Commun. ACM. -1983. Vol. 26, № 11. — C. 945−947.

65. Melton J., Simon A. Understanding The New SQL: A CompleteVGuide. Morgan Kaufman.

66. Miyao J., Tominaga K., Kikuno T., Yoshida N. Optimization of Multiple Queries in Relational Database Systems. // Syst. and Comput. in Japan.-1988.-Vol. 19, № 4. C. 56−65.

67. Motzkin D. Database Performance Optimization. // AFIPS Conf. Proc.: Nat. Comput. Conf., Chicago, III., July 15−18, 1985. Reston, Virg., 1985. — C. 555, 557−566.

68. Pascal F. Understanding Relational Databases with Examples in SQL-92. John Wiley & Sons, 1993.

69. Pecherer R.M. Efficient Evaluation of Expressions in a Relational Algebra // Proc. ACM Pacific Reg. Conf., New York, Apr. 1975. New York, 1975.-G. 44−49.

70. Rosental A., Chakravarthy U. Anatomy of a Modular Multiple Query Optimizer. // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988. C. 230 239. V.

71. Roth nie J.B. An Approach to Implementing a Relational Data Management System. // Proc. ACM SIGMOD Workshop on Data Descr., Acc. and Contr., Ann Arbo!, Mich., May 1974. New York, 1974.-C. 133−140.

72. Rothnie J.B. Evaluating Inter-Entry Retrieval Expressions in a Relational Data Base Management System. // AFIPS Conf. Proc.: Nat. Comput. Conf., Anaheim, Calif., May 1975. Montvale, N.Y., 1975.-C. 152−159.

73. Rowe N.C. Absolute Bounds on Set Intersection and Union Sizes from Distribution Information. // IEEE Trans. Software Eng. 1988. -Vol, 14, № 7.-C. 1033−1048.

74. Rzeczkowski W., Subieta K. Stored Queries—A Data Organization for Query Optimization. // Data and Knowledge Eng. —1988. — Vol. 3, № 1.-C. 29−48.

75. Sagiv Y., Yannakakis M. Equivalences Among Relational Expressions with Union and Difference Operators. // J. ACM, 1980. — Vol. 27, № 4. C. 633−655.

76. Satoh K., Tsuchida M., Nakamura F., Oomachi K. Local and Global Query. Optimization Mechanisms for Relational Databases.-// Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985. C. 405−417.

77. Sellis T. Multiple-Query Optimization. // ACM Trans. Database Syst.:: 99 -1988.-Vol. 13, № 1.-C. 23−52.

78. Shenoy S.T., Ozsoyoglu Z.M. A System for Semantic Query Optimization. // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York, 1987. -C. 181−195. :

79. Smith J.M., Chang P.Y.-T. Optimizing the ~ Performance of a Relational Algebra Database Interface. // Commun. — 1975. — Vol. 18, № 10. -C. 568−579.

80. Stockmeyer L.H., Wong O.K. On the Number of Comparisons to Find the Intersection of Two Relations. // SIAM J. of Comput. 1979. -Vol. 8, № 3. — C. 388−404.

81. Stonebraker M., Woodfil L., Ranstrom J., Murphy M., Meyer M., Allman E, Performance Enhancements to a Relational Database System. // ACM Trans. Database Syst. 1983. — Vol. 8, № 2. — C. 189−222;

82. Subieta K.: Rzeczkowski W. Query Optimization by Stored Queries. // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif., 1987.-C. 369−380, :

83. Talbot S. An Invistigation into Optimization of Relational Query Languages. // Comput. J. 1984. — Vol. 27, № 4. — C. 301−309.

84. Webster’s Tenth New Collegiate Dictionary, 1967.

85. West V. An Optimizer for a Relational Database CommandLanguage, //" Software: Pract. and Exper. -1983.-Vol. 13, № 11. -C/1005−1O12 •.

86. Whang K.-Y. Index Selection in Relational Databases // Found. Data- -, 100 ' «¦¦ /.-•¦-¦—» Organ. Proc. Int. Conf., Kyoto, Japan, May 22−24, 1985. New YorkLondon, 1987. C. 487−500.

87. Whang K., Wiederhold G., Sagalowicz D. Estimating Block Accesses in Database Organizations — A Closed Noniterative Formula. // Commun. ACM. 1983. -Vol. 26, № 11. — C. 940−944.

88. Wong E., Youssefi K. Decomposition A Strategy for Query Processing. // ACM Trans. Database Syst. — 1976. — Vol. 1, № 3. -C. 223−241.

89. Yao S.B. An Attribute Based Model for Database Access Cost Analyses. //ACM Trans/Database Syst. 1977. — Vol. 2, № 1. — C. 45−67.

90. Yao S.B. Approximating Block Access in Database Organizations. // Commun. ACM.-1977.-Vol. 20, № 4. C. 260−261.

91. Yao S.B. Optimization of Query Evaluation Algorithms. // ACM Trans. Database Syst, — 1979. — Vol. 4, № 2. C. 133−155. :.

92. Youssefi K., Wong E. Query Processing in a Relational Database Management System.// Proc. 5th Int. Conf. Very Large Data Bases, Rio de Janeiro, Brasil, Oct. 3−5, 1979. New York, 1979. C. 409 417.

93. Yu C.T., Gun K.-C., Zhang W" Templeton M" Brill D" Chen A.L.P. Algorithms to Process Distributed Queries in Fast Local Networks. // IEEE Trans. Comput. -1987. Vol. 36, № 10. — C. 1153−1164.