公交換乘系統的數據庫結構及算法優化

胡云峰

(文山學院計科系,云南 文山 663000)

公交換乘系統的數據庫結構及算法優化

胡云峰

(文山學院計科系,云南 文山 663000)

自從計算機和計算機網絡進入人們的日常生活中,各大中型城市中出現了一種以服務廣大市民出行為目的的非營利性網站,其主要的功能是輔助使用者找出一個最省時、最方便的出行方案。此類網站在數據庫設計和算法上有一定的復雜性,文章針對此類網站的數據庫設計和算法優化進行研究,以文山縣城為原型進行系統的設計開發。

T-SQL;存儲過程;觸發器;算法優化;數據庫設計

1 公交換乘系統的設計理念

為滿足人們日常生活中不同的出行需求,方便進行出行線路的快速查詢,參照目前一些大中型城市里已經在運行使用的類似系統,以文山縣城為原型,設計開發了該系統,系統主要包括以下幾個功能:(1)用戶可以向系統提供自己要乘坐的公交線路,查詢得到本路公交車經過的所有站點;(2)用戶可以根據某個站點名,通過系統查詢出所有經過該站點的公交車線路;(3)用戶還可以輸入起始站點和目標站點的站點名,經過系統運算和查詢后給出最佳出行方案。

2 公交換乘系統的主要功能模塊

2.1 管理模塊

在整個系統正常運行之前,需要對各個相關站點數據進行維護,確保系統的安全、數據的完整以及站點的及時更新。進入系統管理模塊前需要登陸系統,根據用戶名和密碼檢測賬號的合法性。當用戶名和密碼不正確時,返回登陸界面重新登陸。反之,表示驗證成功,進入管理員管理界面。維護管理員管理界面具有三大功能,分別是管理賬號維護、公交線路維護和公交站點維護。管理賬號維護,提供創建和刪除管理賬號的功能,在需要多人管理本系統時進行操作;公交線路維護,提供公交線路的維護功能,主要用于城市新增或撤銷公交線路時對系統數據進行操作;公交站點維護,可對某條已經存在的公交線路內的站點進行維護,主要用于某條公交線路內的站點發生變化更新站點信息。詳細的功能結構見圖1。

圖1 公交換乘系統功能結構圖

2.2 換乘查詢模塊數據流程

一般用戶操作的是公交換乘查詢頁面。換乘查詢,可分為三個功能:根據線路查詢站點、根據站點查詢線路和根據起始站點和目的站點查詢出行方案。用戶進入查詢頁面以后,選擇需要的查詢方式,系統根據用戶的選擇,判斷屬于哪一種查詢,然后根據用戶所提交的數據,給出查詢結果。公交換乘模塊的數據流程圖[1]見圖2。

圖2 公交換乘模塊的數據流程圖

3 公交換乘數據庫的建立及數據庫算法實現

3.1 根據線路查詢站點的功能實現

文山縣城目前共有10路公交車,將所有站點數據整理后錄入,形成線路站點表,部分線路站點表見圖3。

圖3 線路站點表

線路站點表記錄了每條線路經過的所有公交站點,由于某些線路去程和回程的站點有差異,因此在表中利用“方向”字段加以區分。通過此表,直接利用查詢語句(SELECT線路,站點,方向FROM線路站點表WHERE線路=“[用戶提供的查詢線路名]”)進行查詢,即可根據用戶輸入的線路,查詢出該線路所包含的站點信息。

3.2 根據站點查詢線路的功能實現

要實現根據提供的站點名稱查詢出所有經過該站點的公交線路,利用原先建立的線路站點表難以實現。可以將線路站點表按照線路和站點進行拆分,細化為新的線路站點表,將每條線路的各個站點獨立出來作為一條新記錄錄入數據表,建立如圖4所示新的線路站點表。這樣做雖然增大了記錄的條數,但是,根據新的線路站點表,可以方便地利用用戶所提供的站點名查詢出經過此站點的公交線路,通過查詢語句(SELECT線路,方向FROM線路站點表WHERE站點=“[用戶提供的站點名]”)實現根據站點查詢線路的功能。而要想實現根據線路查詢站點的功能,只需要簡單修改程序代碼,利用數組的概念,經過循環運算即可。

圖4 新的線路站點表

3.3 站-站查詢的功能實現

公交換乘系統應用最廣泛的功能是實現站站查詢,即根據起始站點和目標站點查詢出行線路。僅根據前面建立好的線路站點表,要實現根據用戶所提供的起始站點和目標站點,查詢出出行線路,是不可能實現的,于是,考慮將線路站點表中各條線路所包含的公共站點提取出來,創建一個線路站點交叉表,該表主要是記錄各條公交線路的交叉站點。1路和4路、7路車在“交通集團”這站有交點,也就是說交通集團就是1路、4路和7路的公共站點,如圖5所示:

圖5 線路站點交叉表

根據線路站點交叉表,就可以實現站站查詢。當獲取到用戶提供的起始站點(B)和目標站點(E)后,首先,根據B和E查詢線路站點交叉表,看里面有沒有一條線路滿足同時包含起始站點和目標站點,如果有,則表示不用換乘,直接乘坐一路公交車即可到達。如果沒有,則查詢哪幾條線路包含站點B,將所有的包含B站點的線路保存在一個數組A 1中。然后查詢哪幾條線路包含站點E,將所有包含站點E的線路保存在數組A 2中,再將數組A 1和數組A 2中的元素分別一一配對,和上表線路站點交叉表中的記錄進行對比,如果有一條記錄中的線路一、線路二字段的值正好與兩個數組中的值一致,即說明在這條記錄的公共站點可以實現換乘,從而得出從起始站點B到目標站點E的換乘方案。

4 數據庫結構及算法的優化

公交換乘系統在公交線路和公交站點不斷增加以后,各線路和各站點之間換乘運算的數據量將變得異常龐大,因此,數據庫結構和換乘算法需要從以下幾方面進行優化。

(1)從Access到SQL Server的過渡。Access作為Microsoft Office套件中的一部分,獲取和安裝都很容易。系統最初是利用Access數據庫,在實現各項功能方面都可以滿足。但是隨著城市規模的擴大,公交線路肯定會日益增加,這樣將直接導致站點數據成倍增長。由于Access只能滿足于個人的、小規模的數據庫的管理,一旦數據量加大就不適用了,所以在系統最終測試階段,選擇可以管理更多數據的SQL Server,這是處理將來不斷增加的數據量的最佳方案。

(2)數據表結構的優化。一個高效、合理的數據庫,需要滿足第三范式的規范。所謂第三范式,是一個數據庫表中不包含已在其它表中已包含的非主關鍵字信息。簡單來說,就是非主鍵屬性只依賴于主鍵屬性。作為主鍵,也就是一條記錄中可以唯一標示這條記錄的字段,在各個表中一定要唯一。[2]在以上三個表中,都設計了編號這個字段作為主鍵。這樣在進行數據查詢的時候就能避免錯亂。

(3)T-SQL語句的優化。此部分的主要工作是將實現功能的代碼進行優化,在優化所有的查詢語句的時候,制定了以下規則:

a)盡可能少的行。

b)避免排序或為盡可能少的行排序,若要做大量數據排序,最好將相關數據放在臨時表中操作,用簡單的鍵(列)排序,如整型或短字符串排序。

c)避免表內的相關子查詢。

d)避免在W here子句中使用復雜的表達式或非起始的子字符串、用長字符串連接。

e)在W here子句中多使用“與”(And)連接,少使用“或”(O r)連接。

(4)頻繁的數據庫查詢到存儲過程的過渡。由以上公交換乘數據庫的建立及數據庫算法實現可以看出,系統主要是構造實現各個功能模塊的查詢語句來實現最終的功能,這一切,都建立在與數據庫系統的交互上,可以想象,終端用戶量如果過大,同一時間內,由客戶端向服務器發送的代碼量將是一個很龐大的數據。為了減少從客戶機通過網絡向服務器發送的代碼量,最好將代碼以一定的形式存放在服務器上,利用SQL Server的存儲過程就可以做到。存儲過程就是在SQL Server數據庫重存放的查詢,是存儲在服務器中的一組預編譯過的T-SQL語句,而不是在客戶機上前端代碼中存放的查詢。[3]由于程序的三個功能主要是由三塊的T-SQL語句所構成,所以,在每次使用本系統的時候,都會將對應的語句發送到服務器,再由服務器處理得出結果后返回客戶機。利用存儲過程,將實現三個功能的語句放在服務器上,每次調用直接從服務器上取出即可。這樣既減少了反復查詢產生的代碼傳送量,又加快了查詢速度,同時減輕了網絡負擔。

(5)大量功能代碼到觸發器的轉換。觸發器是一種特殊的存儲過程,其過程由對數據庫表的添加、刪除、修改等事件觸發。[3]在設計和創建數據庫表結構的時候,由于整個系統不是由單一的、關系相對獨立的表組成的,相反,所有的表之間存在一個相互影響的關系,所以在遇到某些情況,比如新增加一個站點或刪除一條線路時,就要進行大量的數據變動。在原先的設計中,采取的辦法是利用數據庫表自身的相應操作將變動的數據進行設計,但是這種做法不但工作量大,而且在操作員進行系統管理的時候,經常由于疏忽會遺忘掉一部分的操作,造成數據的不一致,最終導致系統產生嚴重錯誤。于是,在系統測試階段,將所有的有聯系的操作利用觸發器的思想解決。經過觸發器技術,在對某條線路進行調整或者修改后,系統會自動將與此線路相關的、存在于所有表中的記錄完全進行調整,這樣就解決了先前處理這些變更線路所產生的大量代碼和復雜的操作。

(6)代碼的優化。文山公交換乘系統的開發是由三個項目組成員組成,在進行編碼的時候,難免會有各自的編碼習慣。針對這點,在版本上統一使用微軟公司的VSS,以保證開發成員使用的一定是最新的代碼版本;在程序代碼編寫上,建立規范的數據字典[1]和編碼規則,力求統一;在程序測試階段,分別利用白盒測試和黑盒測試[4],對整個程序進行測試,避免產生一切可預料到的錯誤。

5 結 語

文山州公交換乘系統(www.0876city.com)的開發用時一年,已經進入實際使用階段。目前系統所提供的查詢功能僅限于文山城區的10條公交線路,并且只提供一次換乘查詢,后期的二次換乘查詢和查詢網絡在全州八個縣的全面覆蓋是下一步的目標。

[1] 侯炳輝.信息管理系統[M].北京:中央廣播電視大學出版社,2001:51-172.

[2] 薩師煊,王珊.數據庫系統概論[M].北京:高等教育出版社,2004:176.

[3] 陳玉峰.SQL Server2000數據庫開發教程[M].北京:科學出版社,2003:65-199.

[4] 白鵬.數據庫編程[M].北京:科學出版社,2003:228-231.

Public Transit System Database Structure and the Optimization Algorithm

HU Yun-feng
(Department of Computer Science,Wenshan University,Wenshan Yunnan 663000,China)

Since computer and computer network com e into people's daily life,there appears a kind of Nonprofit website serving for people in large and medium -sized cities. Its main function is to assist its user to find out most economical and convenient travel plan.This kind of website's database structure and optimization algorithm has some comp lex characteristics.This paper,based on its database structure and optimization algorithm,carries out research to take Wenshan city as prototype to design a network development.

T-SQL;trigger;optimization algorithm;database design

U 491.17

A

1674-9200(2010)02-0104-04

2009-12-17

文山師范高等?？茖W?？蒲谢痦椖俊拔纳街莨粨Q乘系統”(08W SY04)

胡云峰(1981-),男,云南文山人,助教,碩士研究生,主要從事計算機應用程序開發的教學及研究。

(責任編輯 劉常福)