MC726 2000/1 - Projeto

A base de dados

Informações necessárias

Nas discussões até o momento, determinamos que as seguintes informações são necessárias para o funcionamento da ``planta inteligente'':

• Descrição da rede viária:
  • Geometria (posição e forma dos logradouros.).
  • Aparência (cores, estilos de linhas, etc.).
  • Topologia (conexões entre logradouros).
  • Dados de trânsito (mãos de direção, tempos de percurso, etc.)
  • Identificação (nomes de logradouros, números de casas, CEPs, etc.)
• Descrição dos serviços:
  • Geometria (coordenadas, forma, dimensões.).
  • Aparência (cores, estilos, símbolos, etc.).
  • Topologia (pontos de acesso à rede viária).
  • Tipo de serviço (hospital/restaurante/etc.).
  • Identificação (nome do estabelecimento, endereço, etc.).

Estas listas possivelmente serão ampiadas à medida que aprofundarmos a análise.

Estrutura da rede viária

Na discussão em classe decidimos direcionar o produto para motoristas, pois o planejamento de rotas para pedestres é muito mais complicado (precisa levar em conta linhas de ônibus e horários).

O planejamento de caminho mais curto entre dois pontos exige obviamente conecimento da planta da cidade: basicamente, as ruas, seus comprimentos, a ordem e posição de seus cruzamentos, etc. Além disso, essa tarefa exige conhecimento das mãos de direção nas ruas, e dos sentidos permitidos de conversão nas esquinas.

Após analisar o problema, concluímos que é necessário considerar separadamente cada pedaço de rua entre duas esquinas, e além disso distinguir as duas mãos de direção de cada pedaço.

Portanto, podemos analisar a estrutura lógica da rede viária como uma coleção intersecções (cruzamentos, entroncamentos, etc.), ligadas entre si por de trechos de rua de mão única. Um trajeto de carro pode então ser descrito como uma seqüência de trechos e intersecções. Note-se que, para fins de planejamento de trajeto, não é preciso pensar na posição exata do carro; basta saber em que trecho o carro está. Uma vez num trecho, o carro não tem escolha: se o local de destino almejado se encontra nesse trecho, o carro deve parar; senão ele deve continuar no trecho, na mão correta, até a próxima esquina.

Comparando caminhos

Para a escolha da rota ótima entre dois pontos, precisamos implementar algum critério numérico da "qualidade" ou "desejabilidade" de uma rota. O comprimento total é um critério óbvio, mas não muito útil, pois a velocidade varia muito de uma rua para outra; e nesse caso o tempo é mais importante que a distância em si. (A velocidade varia também com a hora, obviamente; mas, numa primeira aproximação, podemos supor que o efeito da congestão de tráfego é diminuir a velocidade de todas as ruas ao mesmo tempo, na mesma proporção; de modo que a duração relativa de duas rotas não depende da hora.)

Para calcular o tempo de percurso de uma rota, a partir do comprimento da mesma, o programa precisaria saber a velocidade média do tráfego em cada trecho. Além disso, uma parte importante da duração de um trajeto urbano é gasta em cruzamentos e semáforos, e dobrando esquinas; e calcular esses tempos seria também bastante complicado. Mas podemos evitar essa dor de cabeça supondo que o tempo necessário para percurso de cada trecho e para cruzar ou dobrar cada esquina é fornecido diretamente pela base de dados. Com isso, o cálculo ou medida desses tempos deixa de ser um problema do "Departamento de Desenvolvimento de Software" (os alunos) e passa para o "Departamento de Coleta de Dados" (o professor).

Na verdade, o tempo de percurso também não é o único critério: ha' outros fatores como complexidade do trajeto, segurança, qualidade do asfalto, etc. Portanto, em vez de associar um tempo a cada trecho ou esquina, podemos associar diretamente um custo --- basicamente proporcional ao tempo, mas incluindo penalidades por todos os outros fatores.

Serviços

Cada serviço estará "pendurado" num determinado trecho de logradouro, onde fica sua entrada (do ponto de vista de quem vai de carro, naturalmente). Temos que prever serviços grandes (shoppings, parques, hospitais, etc.) que possuem várias entradas e saídas, possivelmente em trechos de ruas diferentes.

Descrição formal (abstrata) dos dados

Antes de estudarmos como essas informações serão armazenadas (isto é, o conteúdo e formato da base de dados), é altamente desejável definir mais precisamente quais informações devem estar disponíveis, bem como as principais restrições sobre as mesmas que podem ser relevantes para o projeto e implementação do software. Este passo é necessário para que a próxima rodada de especificação, análise e projeto seja mais precisa e eficiente.

Para uma especificação precisa, nada melhor que a linguagem da matemática. (Afinal, essa é a razão de ser da matemática.) Em particular, os conceitos de relação, função, e conjunto formam uma linguagem simples mas poderosa, que permite descrever estruturas e algoritmos complicados de forma compacta e sem ambigüidades.

Nas descrições abaixo, Z, N, R e B denotam os conjuntos de números inteiros, naturais (inteiros não-negativos), reais, e booleanos (false e true), respectivamente. Tambem denotaremos por C o conjunto dos caracteres (ISO-Latin-1, para ser preciso), e por C* o conjunto das cadeias de caracteres.

• Elementos lógicos da base de dados:
  • T conjunto de trechos.
  • E conjunto de intersecções (esquinas).
  • L conjunto de logradouros.
  • S conjunto de serviços.
• Informações sobre a rede viária:
  • orig, dest: T -> E
    orig(t) = esquina de origem do trecho t,
    dest(t) = esquina de destino do trecho t
  • oposto: T -> T + { ¤ }
    oposto(t) = trecho paralelo a t, na mesma rua, de mão contrária (ou um valor especial ¤ se a rua for de mão única).
  • pcusto: T -> R
    pcusto(t) = ``custo'' (demora, desconforto, etc.) em percorrer o trecho t, de esquina a esquina.
  • logr: T -> L
    logr(t) = logradouro a que pertence o trecho t.
  • pode: T×T -> B
    pode(t<sub>1</sub>,t<sub>2</sub>) = é possivel passar diretamente do fim do trecho t<sub>1</sub> para o início do techo t<sub>2</sub>. Obviamente pode(t<sub>1</sub>,t<sub>2</sub>) = true se somente se dest(t<sub>1</sub>) = orig(t<sub>2</sub>) e é permitido efetuar a curva necessária.
  • vcusto: T×T -> R
    vcusto(t<sub>1</sub>,t<sub>2</sub>) = ``custo'' de passar do fim do trecho t₁ para o início do trecho t₂. Em particular, vcusto(t₁,t₂) = +oo se pode(t₁,t₂) = false.
  • nome: L -> C*
    nome(h) = nome do logradouro h.
  • inum, fnum: T -> N
    inum(t) = número do primeiro imóvel no trecho t;
    fnum(t) = número do último imóvel no trecho.
• Informações sobre serviços:
  • entrada, saida: T×S -> B
    entrada(t,s) = diz se no trecho t existe uma entrada (usável por quem está de carro) para o serviço s.
    saida(s,t) = idem para saída do serviço s.
    
  • tipo: S -> C*
    tipo(s) = "hospital", "restaurante", etc. A COMPLETAR