Естественное соединение (natural join)

Использование реляционной теории при оптимальном проектировании интегральных схем

Предложен подход к адаптации реляционной теории для решения задач систем автоматизированного проектирования интегральных схем. Разработан алгоритм оптимального поиска неявных Don't Care (безразличных) значений. Алгоритм описан в терминах адаптированной теории, что позволило получить простое описание алгоритма как для неформального понимания, так и для формального анализа. Предложенный подход позволяет использовать позитивный опыт реляционных баз данных по эффективной (в том числе распределенной) реализации операций реляционной алгебры. Проведен сравнительный анализ предложенного алгоритма и классического алгоритма оптимального поиска неявных Don't Care значений. В ходе сравнительного анализа формально доказана корректность предложенного алгоритма. Показано, что предложенный алгоритм, по сравнению с классическим, имеет значительно меньшую асимптотическую сложность в худшем случае. Поиск неявных Don't Care значений в процессе проектирования интегральных схем позволяет повы...