На Хабре и за его пределами часто обсуждают реляционную алгебру и SQL, но далеко не так часто акцентируют внимание на связи между этими формализмами. В данной статье мы отправимся к самым корням теории запросов: реляционному исчислению, реляционной алгебре и языку SQL. Мы разберем их на простых примерах, а также увидим, что бывает полезно переключаться между формализмами для анализа и написания запросов.

Зачем это может быть нужно сегодня? Не только специалистам по анализу данных и администраторам баз данных приходится работать с данными, фактически мало кому не приходится что-то извлекать из (полу-)структурированных данных или трансформировать уже имеющиеся. Для того, чтобы иметь хорошее представление почему языки запросов устроены определенным образом и осознанно их использовать нужно разобраться с ядром, лежащим в основе. Об этом мы сегодня и поговорим.

Большую часть статьи составляют примеры с вкраплениями теории. В конце разделов приведены ссылки на дополнительные материалы, а для заинтересовавшихся и небольшая подборка литературы и курсов в конце.

Содержание

• Реляционная алгебра
• SQL
• Реляционное исчисление
• Равенство формализмов (теорема Кодда)
• Conjunctive Queries (CQ)
• Вычислительная сложность
• Свойства и анализ запросов
• Пример использования RA для оптимизации запросов
• Литература, материалы и слайды

Hello, Habr! Недавно мы получили от “Известий” заказ на проведение исследования общественного мнения по поводу фильма «Звёздные войны: Пробуждение Силы», премьера которого состоялась 17 декабря. Для этого мы решили провести анализ тональности российского сегмента Twitter по нескольким релевантным хэштегам. Результата от нас ждали всего через 3 дня (и это в самом конце года!), поэтому нам нужен был очень быстрый способ. В интернете мы нашли несколько подобных онлайн-сервисов (среди которых sentiment140 и tweet_viz), но оказалось, что они не работают с русским языком и по каким-то причинам анализируют только маленький процент твитов. Нам помог бы сервис AlchemyAPI, но ограничение в 1000 запросов в сутки нас также не устраивало. Тогда мы решили сделать свой анализатор тональности с блэк-джеком и всем остальным, создав простенькую рекурентную нейронную сеть с памятью. Результаты нашего исследования были использованы в статье “Известий”, опубликованной 3 января.



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

Всё время, пока в Голливуде снимали фильмы про хакеров, самым популярным инструментом для «взлома» была утилита nmap. Когда продюсеры фильма пытались добавить немного реалистичности, на экране компьютеров мелькал вывод nmap. Вроде бы первой отличилась Тринити из фильма «Матрица». Также эта утилита появлялась в Elysium, The Bourne Ultimatum, Die Hard 4 и других киношках.



Первый сезон Mr Robot получил одобрение от специалистов по безопасности за попытки реалистичного показа работы хакеров. В показанных эпизодах хакеры общались через IRC, использовали виртуальные машины Linux, а главный герой ходил в толстовке с капюшоном. Естественно, поскольку это телешоу, создателям пришлось проявить толику творчества. И пока им удаётся сохранять неплохой баланс между повествованием и реальными техническими возможностями.

Кратко рассмотрим увиденные нами в сериале средства для взлома.

Kali Linux

Несколько раз можно видеть использование дистрибутива Kali Linux – операционки, изначально снабжённой инструментами для проникновения и тестирования безопасности систем. Если вам интересна тема сетевой безопасности – скачивайте её себе и начинайте пробовать. Естественно, только в учебных целях. Не взламывайте чужие компьютеры – это незаконно!

На новый год купил племяннику головоломку Галакуб. Задача собрать из разных деталей куб размером 4х4х4. Суммарный объём деталей, как раз, 4х4х4. Прежде, чем дарить надо было собрать головоломку. Красивое симметричное решение нашлось достаточно быстро. Но стало интересно единственное это решение или нет. Интуиция подсказывала, что единственное, но хотелось проверить.


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

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

Как Чарли Миллер и Крис Валасек взломали Jeep Cherokee.



В начале своего исследования Миллер и Валасек пытались взломать мультимедийную систему Jeep через Wi-Fi. Производитель автомобиля, компания Chrysler, предлагает возможность использования Wi-Fi по подписке. Оказалось, что эту беспроводную связь взломать достаточно легко, из-за того, что пароль на неё генерился автоматически на основе времени, когда машина и мультимедийная система включались впервые.

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

Shock at the wheel: your Jeep can be hacked while driving down the road https://t.co/40h8StaLFG pic.twitter.com/bOvjzQb9K4

— Kaspersky Lab (@kaspersky) 23 июля 2015

Проблема в том, что в течение всего часа необходимо находиться поблизости от этого джипа, чтобы оставаться в пределах досягаемости Wi-Fi. Но исследователи нашли другой путь. Оказалось, что пароль для Wi-Fi создаётся до того, как в системе будут установлены дата и время – то есть, дефолтное время отсчёта плюс несколько секунд на то, чтобы бортовой компьютер загрузился.

И это время составляет ровно January 01 2013 00.00.32 GMT.

Независимый специалист по безопасности Уэсли Вайнберг (Wesley Wineberg) подвергся серьёзному давлению со стороны компании Facebook. Она не заплатила за найденные уязвимости на сервере Instagram, да ещё угрожает судебным иском.

Уэсли обнаружил уязвимость в инфраструктуре Instagram, с помощью которой нашёл (и, возможно, скачал) практически всё ценное, что есть на серверах Instagram: исходный код последней версии, SSL-сертификаты и приватные ключи для Instagram.com, ключи для подписи куков аутентификации, учётные данные от почтового сервера и ключи для некоторых других продуктов, в том числе для подписи мобильных приложений под iOS и Android.

Привет всем!

Сегодня я рада анонсировать курс “Hacking PostgreSQL” из 16 занятий, на которых мы вместе будем исследовать особенности архитектуры открытой СУБД и вносить изменения на уровне исходного кода. Курс будет проходить в Москве, на площадке компании Postgres Professional. Начало курса запланировано на февраль 2016 года. Лекции начнутся сразу после февральской конференции pgconf.ru и будут проходить один раз в неделю вечером. Видеозаписи и материалы лекций мы будем выкладывать по мере обработки.

Курс собран из личного опыта разработчиков нашей компании, материалов с конференций, статей и вдумчивого чтения документации и исходников. В первую очередь он адресован начинающим разработчикам ядра PostgreSQL. Но он будет интересен и DBA, которым иногда приходится влезать в код, и просто всем неравнодушным к архитектуре большой системы, желающим узнать “А как это работает на самом деле?”

Когда я первый раз столкнулся с темой бинарных деревьев в программировании, то сразу нашел на Хабре ответы почти на все возникшие у меня вопросы, но время шло, вопросов становилось больше и совсем недавно я нашел тему, которую еще не осветили на данном ресурсе — это 2-3-4 деревья. Есть отличная статья на тему 2-3 деревьев, в которой можно найти ответы на вопросы «Что такое куча?», «Что такое 2-3 деревья», а также информацию про основные операции со структурой, поэтому я не буду повторяться и сразу перейду к главной теме.

Итак, главное отличие 2-3-4 деревьев от 2-3 состоит в том, что они могут содержать более трех дочерних узлов, что дает возможность создавать четырехместные узлы (узлы, имеющие четыре дочерних узла и три элемента данных). Можно увидеть отличия визуально на гифке под эти текстом.На первом слайде показано 2-3 дерево, на втором — 2-3-4.

Исследователи безопасности Гектор Марко (Hector Marco) и Исмаэль Риполл (Ismael Ripoll) опубликовали информацию об обнаруженной ими 0-day уязвимости в популярном загрузчике Grub2, который используется в большинстве Linux-системах. Эксплуатация уязвимости позволяет получить доступ к аварийной консоли Grub2 в обход пароля. Это, в свою очередь, открывает злоумышленнику возможность проведение атаки направленной на повышение привилегий в систем и доступа ко всей информации.

Яндекс.Метрика сегодня это не только система веб-аналитики, но и AppMetrica — система аналитики для приложений. На входе в Метрику мы имеем поток данных — событий, происходящих на сайтах или в приложениях. Наша задача — обработать эти данные и представить их в подходящем для анализа виде.



Но обработка данных — это не проблема. Проблема в том, как и в каком виде сохранять результаты обработки, чтобы с ними можно было удобно работать. В процессе разработки нам приходилось несколько раз полностью менять подход к организации хранения данных. Мы начинали с таблиц MyISAM, использовали LSM-деревья и в конце концов пришли к column-oriented базе данных. В этой статье я хочу рассказать, что нас вынуждало это делать.

Яндекс.Метрика работает с 2008 года — более семи лет. Каждый раз изменение подхода к хранению данных было обусловлено тем, что то или иное решение работало слишком плохо — с недостаточным запасом по производительности, недостаточно надёжно и с большим количеством проблем при эксплуатации, использовало слишком много вычислительных ресурсов, или же просто не позволяло нам реализовать то, что мы хотим.

При создании любой компании можно наделать немало промахов, которые впоследствии могут похоронить весь бизнес. В каждой сфере есть свои специфические ошибки, в том числе и в IT. На тему того, как не бегать по граблям, в Технопарке рассказал Стас Щукин, обладающий 15-летним опытом работы с IT в таких компаниях, как «Ситроникс», «Связной», Tvigle Media и А1. Кроме того, шесть лет назад Стас основал собственную компанию, разрабатывающую заказные проекты, где периодически выступает в роли подрядчика, консультанта и основного разработчика. Текст выступления читайте под катом.

Многие боятся переходить с «мускуля» на «посгрес» из-за того, что лишь смутно понимают, что это даст. Некоторых останавливает мысль, что наверно Postgres — это слишком сложная база и требует обучения. А также, что возможно чего-то придется лишиться в связи с переходом. Попробую немного прояснить ситуацию.

Все наверное знают, что есть очень много разных способов угрозы безопасности. Их действительно достаточно, сколько их узнаете прочитав под катом.

Добрый день, уважаемые читатели.
В сегодняшней статье я покажу основы разбора HTML разметки страниц с помощью библиотеки lxml для Python.
Если вкратце, то lxml это быстрая и гибкая библиотека для обработки разметки XML и HTML на Python. Кроме того, в ней присутствует возможность разложения элементов документа в дерево. В статье я постараюсь показать, насколько просто ее применение на практике.

Добрый день, уважаемые читатели.

В сегодняшней статье я хотел бы, как можно подробнее, рассмотреть интеграцию приложений Python и MS Excel. Данные вопрос может возникнуть, например, при создании какой-либо системы онлайн отчетности, которая должна выгружать результаты в общепринятый формат ну или какие-либо другие задачи. Также в статье я покажу и обратную интеграцию, т.е. как использовать функцию написанную на python в Excel, что также может быть полезно для автоматизации отчетов.

Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.

Лекция 1. Основы

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

Вступление

Давно хотел написать статью про образование в Computer Science, но руки не доходили. Решил все-таки это наконец сделать. Итак, о чем пойдет речь? Речь о том, что из себя представляет диплом MSc Computer Science топовых университетов США (во всех подробностях, включая основные курсы, книги и проекты) и как ему соответствовать.

Почему именно MSc? Это — некая развилка: с одной стороны после MSc — вы уже готовый к жизни инженер (да, речь идет о инженерной подготовке, как мне кажется это самое больное место в нашей системе образования), с другой — можно спокойно идти по пути PhD. Как известно, в PhD программу можно попасть и не особо умея программировать — особенно это касается теоретического Computer Science. С другой стороны найти работу программиста тоже дело не очень сложное, и часто не требует мощного образования. Но достигнув уровня MSc — вы получаете возможность разбираться как во всех новый идеях в Computer Science, так и возможность их воплотить в практику. То есть с одной стороны круто разобраться в каком-нибудь deep learning и сделать в нем что-то новое, а также взять и написать свою операционную систему (кто так сделал?). Причем вы не зажаты в рамки узкой специализации (если конечно продолжаете учиться). То есть вы теперь — универсальный солдат, готовый на все.

Надеюсь что эта статья будет полезна:
1. Студентам, которые хотят соответствовать высоким стандартам топ вузов США, или собирающиеся туда в аспирантуру по Computer Science
2. Профессионалам, которые хотят закрыть «дыры» и пробелы
3. Может кто-то из преподавателей возьмет на заметку для своих курсов.
4. Студентам, аспирантам американских вузов — хотелось бы тоже получить фидбэк, особенно касается последних трендов в образовании

Что же здесь будет написано? Минимум философии и общих мыслей: конкретная программа undergraduate и graduate курсов, конечно из дисциплин наиболее мне близких. Все курсы были лично прочувствованы на собственной шкуре, по этому и пишу. (Я пытался записаться на все интересные курсы, которые были, но мой основной упор — системное программирование, базы данных и искусственный интеллект. Отсюда конечно некий bias, но пытаюсь предложить более-менее универсальную программу).

Тим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.

Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

Казалось бы, зачем сейчас вообще вспоминать про IPv6? Ведь несмотря на то, что последние блоки IPv4-адресов были розданы региональным регистраторам, интернет работает без каких-либо изменений. Дело в том, что IPv6 впервые появился в 1995 году, а полностью его заголовок описали в RFC в 1998 году. Почему это важно? Да по той причине, что разрабатывался он без учета угроз, с той же доверительной схемой, что и IPv4. И в процессе разработки стояли задачи сделать более быстрый протокол и с большим количеством адресов, а не более безопасный и защищенный.

Прочитал недавно статью «IPv6 под прицелом» и решил написать более подробно об атаке SLAAC (SLAAC Attack), т.к. эту атаку я уже давно в голове держу, развернутого материала на русском не нашел, да и самому интересно ее было повторить.

Суть атаки

В чем суть атаки? Во-первых, она очень простая и надежная, т.к. использует стандартные технологии и инструменты ОС. По сути, вы просто становитесь единственным IPv6-маршрутизатором в сети и раздаете клиентам IPv6-подсеть, из которой клиенты берут себе адреса либо автоматически генерируя их (SLAAC), либо спрашивая у вашего же DHCPv6-сервера. Напомню, что IPv6 включен по умолчанию во всех современных десктопных, мобильных и серверных ОС, имеет приоритет над IPv4 (кроме некоторых случаев), адрес IPv6, в отличие от IPv4, может быть получен в любой момент, а не только в момент совершения подключения, и крупные веб-сайты уже давно доступны через IPv6. Атака работает как в проводных сетях, так и в беспроводных. Не все свитчи, даже современные, поддерживают фильтрацию Router Advertisement, и, как я полагаю, не все включают эту функцию, даже если она поддерживается свитчем, полагая, что раз в сети нет IPv6, то и фильтровать ничего не нужно. К слову, на данный момент, фильтр Router Advertisement можно обойти на всех свитчах, использовав недостатки реализации.

Я смог придумать две реализации атаки: