公交換乘系統(tǒng)的數(shù)據(jù)庫(kù)結(jié)構(gòu)及算法優(yōu)化

胡云峰

(文山學(xué)院計(jì)科系,云南 文山 663000)

公交換乘系統(tǒng)的數(shù)據(jù)庫(kù)結(jié)構(gòu)及算法優(yōu)化

胡云峰

(文山學(xué)院計(jì)科系,云南 文山 663000)

自從計(jì)算機(jī)和計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)入人們的日常生活中,各大中型城市中出現(xiàn)了一種以服務(wù)廣大市民出行為目的的非營(yíng)利性網(wǎng)站,其主要的功能是輔助使用者找出一個(gè)最省時(shí)、最方便的出行方案。此類網(wǎng)站在數(shù)據(jù)庫(kù)設(shè)計(jì)和算法上有一定的復(fù)雜性,文章針對(duì)此類網(wǎng)站的數(shù)據(jù)庫(kù)設(shè)計(jì)和算法優(yōu)化進(jìn)行研究,以文山縣城為原型進(jìn)行系統(tǒng)的設(shè)計(jì)開發(fā)。

T-SQL;存儲(chǔ)過(guò)程;觸發(fā)器;算法優(yōu)化;數(shù)據(jù)庫(kù)設(shè)計(jì)

1 公交換乘系統(tǒng)的設(shè)計(jì)理念

為滿足人們?nèi)粘Ｉ钪胁煌某鲂行枨?方便進(jìn)行出行線路的快速查詢,參照目前一些大中型城市里已經(jīng)在運(yùn)行使用的類似系統(tǒng),以文山縣城為原型,設(shè)計(jì)開發(fā)了該系統(tǒng),系統(tǒng)主要包括以下幾個(gè)功能:(1)用戶可以向系統(tǒng)提供自己要乘坐的公交線路,查詢得到本路公交車經(jīng)過(guò)的所有站點(diǎn);(2)用戶可以根據(jù)某個(gè)站點(diǎn)名,通過(guò)系統(tǒng)查詢出所有經(jīng)過(guò)該站點(diǎn)的公交車線路;(3)用戶還可以輸入起始站點(diǎn)和目標(biāo)站點(diǎn)的站點(diǎn)名,經(jīng)過(guò)系統(tǒng)運(yùn)算和查詢后給出最佳出行方案。

2 公交換乘系統(tǒng)的主要功能模塊

2.1 管理模塊

在整個(gè)系統(tǒng)正常運(yùn)行之前,需要對(duì)各個(gè)相關(guān)站點(diǎn)數(shù)據(jù)進(jìn)行維護(hù),確保系統(tǒng)的安全、數(shù)據(jù)的完整以及站點(diǎn)的及時(shí)更新。進(jìn)入系統(tǒng)管理模塊前需要登陸系統(tǒng),根據(jù)用戶名和密碼檢測(cè)賬號(hào)的合法性。當(dāng)用戶名和密碼不正確時(shí),返回登陸界面重新登陸。反之,表示驗(yàn)證成功,進(jìn)入管理員管理界面。維護(hù)管理員管理界面具有三大功能,分別是管理賬號(hào)維護(hù)、公交線路維護(hù)和公交站點(diǎn)維護(hù)。管理賬號(hào)維護(hù),提供創(chuàng)建和刪除管理賬號(hào)的功能,在需要多人管理本系統(tǒng)時(shí)進(jìn)行操作;公交線路維護(hù),提供公交線路的維護(hù)功能,主要用于城市新增或撤銷公交線路時(shí)對(duì)系統(tǒng)數(shù)據(jù)進(jìn)行操作;公交站點(diǎn)維護(hù),可對(duì)某條已經(jīng)存在的公交線路內(nèi)的站點(diǎn)進(jìn)行維護(hù),主要用于某條公交線路內(nèi)的站點(diǎn)發(fā)生變化更新站點(diǎn)信息。詳細(xì)的功能結(jié)構(gòu)見圖1。

圖1 公交換乘系統(tǒng)功能結(jié)構(gòu)圖

2.2 換乘查詢模塊數(shù)據(jù)流程

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

圖2 公交換乘模塊的數(shù)據(jù)流程圖

3 公交換乘數(shù)據(jù)庫(kù)的建立及數(shù)據(jù)庫(kù)算法實(shí)現(xiàn)

3.1 根據(jù)線路查詢站點(diǎn)的功能實(shí)現(xiàn)

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

圖3 線路站點(diǎn)表

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

3.2 根據(jù)站點(diǎn)查詢線路的功能實(shí)現(xiàn)

要實(shí)現(xiàn)根據(jù)提供的站點(diǎn)名稱查詢出所有經(jīng)過(guò)該站點(diǎn)的公交線路,利用原先建立的線路站點(diǎn)表難以實(shí)現(xiàn)?？梢詫⒕€路站點(diǎn)表按照線路和站點(diǎn)進(jìn)行拆分,細(xì)化為新的線路站點(diǎn)表,將每條線路的各個(gè)站點(diǎn)獨(dú)立出來(lái)作為一條新記錄錄入數(shù)據(jù)表,建立如圖4所示新的線路站點(diǎn)表。這樣做雖然增大了記錄的條數(shù),但是,根據(jù)新的線路站點(diǎn)表,可以方便地利用用戶所提供的站點(diǎn)名查詢出經(jīng)過(guò)此站點(diǎn)的公交線路,通過(guò)查詢語(yǔ)句(SELECT線路,方向FROM線路站點(diǎn)表WHERE站點(diǎn)=“[用戶提供的站點(diǎn)名]”)實(shí)現(xiàn)根據(jù)站點(diǎn)查詢線路的功能。而要想實(shí)現(xiàn)根據(jù)線路查詢站點(diǎn)的功能,只需要簡(jiǎn)單修改程序代碼,利用數(shù)組的概念,經(jīng)過(guò)循環(huán)運(yùn)算即可。

圖4 新的線路站點(diǎn)表

3.3 站-站查詢的功能實(shí)現(xiàn)

公交換乘系統(tǒng)應(yīng)用最廣泛的功能是實(shí)現(xiàn)站站查詢,即根據(jù)起始站點(diǎn)和目標(biāo)站點(diǎn)查詢出行線路。僅根據(jù)前面建立好的線路站點(diǎn)表,要實(shí)現(xiàn)根據(jù)用戶所提供的起始站點(diǎn)和目標(biāo)站點(diǎn),查詢出出行線路,是不可能實(shí)現(xiàn)的,于是,考慮將線路站點(diǎn)表中各條線路所包含的公共站點(diǎn)提取出來(lái),創(chuàng)建一個(gè)線路站點(diǎn)交叉表,該表主要是記錄各條公交線路的交叉站點(diǎn)。1路和4路、7路車在“交通集團(tuán)”這站有交點(diǎn),也就是說(shuō)交通集團(tuán)就是1路、4路和7路的公共站點(diǎn),如圖5所示:

圖5 線路站點(diǎn)交叉表

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

4 數(shù)據(jù)庫(kù)結(jié)構(gòu)及算法的優(yōu)化

公交換乘系統(tǒng)在公交線路和公交站點(diǎn)不斷增加以后,各線路和各站點(diǎn)之間換乘運(yùn)算的數(shù)據(jù)量將變得異常龐大,因此,數(shù)據(jù)庫(kù)結(jié)構(gòu)和換乘算法需要從以下幾方面進(jìn)行優(yōu)化。

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

(2)數(shù)據(jù)表結(jié)構(gòu)的優(yōu)化。一個(gè)高效、合理的數(shù)據(jù)庫(kù),需要滿足第三范式的規(guī)范。所謂第三范式,是一個(gè)數(shù)據(jù)庫(kù)表中不包含已在其它表中已包含的非主關(guān)鍵字信息。簡(jiǎn)單來(lái)說(shuō),就是非主鍵屬性只依賴于主鍵屬性。作為主鍵,也就是一條記錄中可以唯一標(biāo)示這條記錄的字段,在各個(gè)表中一定要唯一。[2]在以上三個(gè)表中,都設(shè)計(jì)了編號(hào)這個(gè)字段作為主鍵。這樣在進(jìn)行數(shù)據(jù)查詢的時(shí)候就能避免錯(cuò)亂。

(3)T-SQL語(yǔ)句的優(yōu)化。此部分的主要工作是將實(shí)現(xiàn)功能的代碼進(jìn)行優(yōu)化,在優(yōu)化所有的查詢語(yǔ)句的時(shí)候,制定了以下規(guī)則:

a)盡可能少的行。

b)避免排序或?yàn)楸M可能少的行排序,若要做大量數(shù)據(jù)排序,最好將相關(guān)數(shù)據(jù)放在臨時(shí)表中操作,用簡(jiǎn)單的鍵(列)排序,如整型或短字符串排序。

c)避免表內(nèi)的相關(guān)子查詢。

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

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

(4)頻繁的數(shù)據(jù)庫(kù)查詢到存儲(chǔ)過(guò)程的過(guò)渡。由以上公交換乘數(shù)據(jù)庫(kù)的建立及數(shù)據(jù)庫(kù)算法實(shí)現(xiàn)可以看出,系統(tǒng)主要是構(gòu)造實(shí)現(xiàn)各個(gè)功能模塊的查詢語(yǔ)句來(lái)實(shí)現(xiàn)最終的功能,這一切,都建立在與數(shù)據(jù)庫(kù)系統(tǒng)的交互上,可以想象,終端用戶量如果過(guò)大,同一時(shí)間內(nèi),由客戶端向服務(wù)器發(fā)送的代碼量將是一個(gè)很龐大的數(shù)據(jù)。為了減少?gòu)目蛻魴C(jī)通過(guò)網(wǎng)絡(luò)向服務(wù)器發(fā)送的代碼量,最好將代碼以一定的形式存放在服務(wù)器上,利用SQL Server的存儲(chǔ)過(guò)程就可以做到。存儲(chǔ)過(guò)程就是在SQL Server數(shù)據(jù)庫(kù)重存放的查詢,是存儲(chǔ)在服務(wù)器中的一組預(yù)編譯過(guò)的T-SQL語(yǔ)句,而不是在客戶機(jī)上前端代碼中存放的查詢。[3]由于程序的三個(gè)功能主要是由三塊的T-SQL語(yǔ)句所構(gòu)成,所以,在每次使用本系統(tǒng)的時(shí)候,都會(huì)將對(duì)應(yīng)的語(yǔ)句發(fā)送到服務(wù)器,再由服務(wù)器處理得出結(jié)果后返回客戶機(jī)。利用存儲(chǔ)過(guò)程,將實(shí)現(xiàn)三個(gè)功能的語(yǔ)句放在服務(wù)器上,每次調(diào)用直接從服務(wù)器上取出即可。這樣既減少了反復(fù)查詢產(chǎn)生的代碼傳送量,又加快了查詢速度,同時(shí)減輕了網(wǎng)絡(luò)負(fù)擔(dān)。

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

(6)代碼的優(yōu)化。文山公交換乘系統(tǒng)的開發(fā)是由三個(gè)項(xiàng)目組成員組成,在進(jìn)行編碼的時(shí)候,難免會(huì)有各自的編碼習(xí)慣。針對(duì)這點(diǎn),在版本上統(tǒng)一使用微軟公司的VSS,以保證開發(fā)成員使用的一定是最新的代碼版本;在程序代碼編寫上,建立規(guī)范的數(shù)據(jù)字典[1]和編碼規(guī)則,力求統(tǒng)一;在程序測(cè)試階段,分別利用白盒測(cè)試和黑盒測(cè)試[4],對(duì)整個(gè)程序進(jìn)行測(cè)試,避免產(chǎn)生一切可預(yù)料到的錯(cuò)誤。

5 結(jié) 語(yǔ)

文山州公交換乘系統(tǒng)(www.0876city.com)的開發(fā)用時(shí)一年,已經(jīng)進(jìn)入實(shí)際使用階段。目前系統(tǒng)所提供的查詢功能僅限于文山城區(qū)的10條公交線路,并且只提供一次換乘查詢,后期的二次換乘查詢和查詢網(wǎng)絡(luò)在全州八個(gè)縣的全面覆蓋是下一步的目標(biāo)。

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

[2] 薩師煊,王珊.數(shù)據(jù)庫(kù)系統(tǒng)概論[M].北京:高等教育出版社,2004:176.

[3] 陳玉峰.SQL Server2000數(shù)據(jù)庫(kù)開發(fā)教程[M].北京:科學(xué)出版社,2003:65-199.

[4] 白鵬.數(shù)據(jù)庫(kù)編程[M].北京:科學(xué)出版社,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

文山師范高等專科學(xué)?？蒲谢痦?xiàng)目“文山州公交換乘系統(tǒng)”(08W SY04)

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

(責(zé)任編輯 劉常福)