利用工具进行数据库数据的复杂查询

2024-07-11

利用工具进行数据库数据的复杂查询（精选3篇）

1.利用工具进行数据库数据的复杂查询篇一

在使用CAD进行设计的过程中，必然会遇上要对所绘对象进行必要的查询，了解该对象的特性，查询的方法很多，下面向大家一一罗列。

1.通过左下角的坐标来查询数据。这个方法非常不精确，而且只能看看坐标，在不需要精确定位的时候可以使用。

2.使用相应的命令来查询，命令id查询坐标，命令distance查距离，命令area查面积。这些命令可以查询对象某些点的坐标，很准确，精确的程度就看设置到保留小数多少位，

3.使用list命令，使用list命令查询出来的内容很多，有句柄、当前空间、层、颜色、线型、线宽等，根据对象不同还有不同的内容，如圆还有中间点、半径、圆周、面积等。

4.使用标注，标注是CAD里面一个不可缺少的功能，同样也能数据查询。通过标注，能直接查出来的数据只有：距离，角度，但是通过这两个数据结合一定的计算方法，就能将所有的数据都计算出来。

5.使用ZWCAD提供的计算器，只需要上面部分，看下图，上面有七个按钮，第四个就是查询点坐标，第五个按钮就是查询两点距离，第六个按钮是查询直线与水平线的角度。第七个就是查两根线的交点的坐标的。结果显示在下面输入框。

2.利用工具进行数据库数据的复杂查询篇二

关键词：算法,平均复杂度,最坏复杂度,分组算法,数据查找,数据序列

序言

对无序数据表的查询一般采用顺序查找方法。实际工作中会出现部分有序的现象, 即在由若干个数据组成的一组内部数据中, 数据排列是无序的, 但数据组与数据组之间是有序的。此时既可以采用顺序查找方法, 也可以将数据序列分为若干组, 然后仅对待查数据所在组进行顺序查找, 而避开其他数据组, 如此可以在很大程度上提高查询效率、优化程序设计。这种查找方法的代价与顺序查找的代价[1]用“平均复杂度O (n) ”和“最坏情形复杂度W (n) ”来衡量, 都可以得到很大改善。

一、算法的平均情形复杂度和最坏情形复杂度

设Sn是一个有n个元素序列Ii (i=1…n) 的集合。Ii在集合中出现的概率为p (Ii) , t (Ii) 是算法在输入Ii时所执行的基本运算次数[2], 则:

二、顺序查询复杂性分析

2.1算法。一个含有n个数据项的升序排列表R, 给定一个数据值key, 在表R中寻找key出现的位置 (可能是数组下标) , 若在表R中key不存在, 则返回结果0。算法如下[5,6]:

设Ii表示key出现在表中的第i个位置的情况。t (Ii) 表示输入Ii的比较次数, 所以在顺序比较的情况下, 下式成立[7]:

设q表示key出现在整个表R中的可能性, 并假定它出现在表R中的任何位置的可能性是一样的。那么出现在某个位置上的可能性为p (Ii) =q/n。当比较位置出现在n+1时属于key不可能出现的情况, 即不出现的概率, 因此有p (In+1) =1-q。

2.2平均复杂度。作为顺序表R[1, 2…, n]的某个项R[i], 为了防止下标溢出监视节点, 如R[n+1], 让其值等于要查找的值, i逐次加1, 这样如果查找不成功, 则i=n+1, 所以有:

式 (1) 中, q (n+1) /2部分表示key出现在表R中的情况; (1-q) (n+1) 为key为不出现的情况。

1) key肯定出现在表R中:

即q=1, 则O (n) = (n+1) /2

表明平均要查找半个数据列表。

2) key出现在线性表R中的可能性为二分之一:

即q=1/2, 则O (n) = (n+1) /4+ (n+1) /2≈3/4*n[6]

表明平均需要查找线性表中3/4的数据元素。

3) key肯定不出现在表R中:

即q=0, 则O (n) =n+1

表明平均需要查找整个表。

2.3最坏复杂度。算法在最坏情况下, 比较次数是:

即key不出现在表R中或出现在表R的最后一个位置时, 都要查找整个线性表R。

三、分组拆分算法

顺序查找算法简单, 容易实现, 但无论是平均复杂度, 还是最坏情形复杂度都比较大, 效率低。而分组算法比顺序算法有较大的改进, 查找效率有较大的提高。为提高查找速度, 最好的方法是二分算法即折半法, 但二分法要求数据列完全保持有序, 当数据集上有频繁的插入或删除操作时, 这种有序极易遭到破坏, 那么为了能继续保持有序, 需要大量移动数据的存储位置。此时可以将二分法与顺序查找法综合运用, 即分组拆分查找算法。这种分组不要求每组的数据量相同, 但是必须制作一张索引表[8], 索引表中记录了每组的长度mi和其中的最大值Rim,

首先将关键数据key与索引表中第i段的最大值Rim进行比较, 如果key=Rim, 比较成功;如果key<Rim则表明key处在第i段中, 然后在第i段中进行顺序比较, 比较次数为mi;如果key>Rim, 将key与第i+1段中的最大数据项Ri+1m进行比较;如果最终未比较成功, 则返回i=0。

3.1算法描述。假设有以下数据序列:

将它们划分为四个子序列, 第一组有3个元素, 第二组有5个元素, 第三组有3个, 第四组有6个。其中, 第一组的全部数据均小于第二组, 第二组的全部数据均小于第三组, 以此类推。但是各组内部数据是无序的。

索引表由两部分组成, 一部分为每组的长度描述, 用数组c[5]表示, 图1中索引表的最后一位是索引表的结束标志。另一部分为每组中的最大值, 用数组m[5]表示。

分组拆分算法描述:

如果比较成功, 输出该数据所在的位置, 否则输出标志0。

3.2平均复杂度。平均复杂度的计算由两部分组成, 一是对索引表的折半查找, 一是对关键段内的顺序查找。

折半查找复杂度。用int (x) 表示小于或等于x的最大正整数。假设key出现在表R中的概率为1。将n个数据分为y段, 对于y个数据, 它出现在表R以及索引表中任何一个位置的可能性为1/y。

假设有以下y=15个有序数据列:2, 4, 7, 10, 14, 15, 18, 21, 22, 25, 26, 29, 33, 37, 39, 在采用二分算法的情况下, 其查找顺序如图2所示。由图可见, 查找某些数据的最大次数 (即二叉树的层) 是c=int (y/4) +1。

假设所查询的数据a肯定出现在图2中, 且落在所有位置上的可能性是相同的, 则p (Ii) =1/y。又由于每次二分就是一次折半, 它是一种二进制关系, 因此图2中的层数c与数据总量y的关系大致满足[4]:

y越大, 式 (3) 越精确。式中, 应当保证c是一个整数, 因此由式 (3) 得到:

对这y个数据进行二分查找, 则平均性态为:

段内顺序查找复杂度。假设段内有数据z个, 由前述已知, 顺序查找的平均复杂度为:

分组拆分复杂度。假设数据项为n, 划分为k段, 每段内的数据量为z, 则分组拆分算法的平均复杂度为:

由于z随不同的分组块其大小有所不同, 因此, 当key处于不同的分组段时, 其平均性态有所差异。总的平均性态可以将分组视为平均分组, 此时可以得到平均复杂性态为:

3.3最坏复杂度。在二分算法情况下, 最坏复杂度即式 (4) 所表达的最大层数, 即:

在段内顺序查找情况下, 最坏复杂度为:

所以, 分组拆分最坏复杂度为:

由式 (7) 可见, 分组拆分算法的最坏复杂度比顺序查找得到了明显改善, 其关键在于减小z值, 因此, 在分组环境允许的情况下, 尽量增大y使得z尽量小。

四、分组拆分算法在题库建设中的应用

本院每学期的高等数学、计算机基础等课程的考试均采用计算机程序随机抽题的方式进行选题。题目是按照教材的章节等因素分类的, 或是分组的。在题库建设过程中, 要不断地增加新题目, 另外, 题目的难度、区分度、猜测度等参数也在不断变化, 它们在题库中的顺序也在不断地被调整, 有些题目还将被删除。为了提高服务器抽题效率, 设计一种好的算法是十分必要的。此时的抽题解决方案可以是对题库重新全部排序, 也可以是分组排序。如果采用全部排序, 则抽题的算法可以采用二分法或分组拆分算法, 如果是分组排序则应当采用分组拆分算法。

本文所讨论的算法可以做为题库建设过程中的程序设计依据。

五、结束语

每一种算法都针对某一种数据结构[9,10], 分组拆分算法则主要针对分组式排序的数据序列, 也针对全排序数据序列。作为一种顺序查询和二分法查询的综合查询法, 其性能表现在既提高了数据查询效率, 又适应非完全排序的数据序列, 在数据序列的顺序有一定变化的情况下显示出较大的优势。

参考文献

[1]Hector Garcia-Molina, Jeffrey D.ullman, Jennifer Widom.Database System Implementation[M].北京.机械工业出版社, 2012, 8.

[2]覃贤立.并行排序算法的设计与分析[J].电脑与信息技术, 2014, 3:14-16.

[3]王晓东.计算机算法设计与分析[M].北京:电子工业出版社, 2012, 2.

[4]苏德富, 钟诚.计算机算法设计与分析[M].北京:电子工业出版社, 2001, 1.

[5]丁亚涛.C语言程序设计[M].北京:中国水利水电出版社, 2010, 1.

[6]刘模群.排序算法时间复杂度研究[J].软件导刊, 2012, 6:35-38.

[7]杨绣丞, 李彤, 赵娜, 等.计算排序算法设计与分析[J].计算机应用研究, 2014, 31 (3) :120-125.

[8]王哲.计算机程序设计中查找算法的效率分析[J].城市建设理论研究, 2012, 22:46-49.

[9]包振宇, 孙干, 陈勇.数据结构[M].北京:中国铁道出版社, 2009, 6.

3.利用工具进行数据库数据的复杂查询篇三

近年来, 电子信息技术快速地融入医疗卫生机构的日常诊疗工作、平时的健康监控记录工作以及医学研究和数据信息研究之中, 极大的提高了医疗相关工作的效率与准确性[1]。人体生理数据一般包括三种[2]: 单值数据 ( 例如: 单次测量的血压、心率体温等数据) 、信号数据 ( 例如: 心电图、脑电图、持续测量的体温血压等数据) 、图像数据 ( 例如: CT图像、核磁共振图像等) 。信号数据又是一种时间序列数据, 这类数据反映了某一事物、现象等随时间变化的状态或程度, 是一种与时间维度紧密相关的典型数据类型。除了信号数据外, 定期测量的单值生理数据, 也可作为时间序列数据进行处理。时间序列数据作为一种特殊的数据, 其存储和管理不同于普通的单值数据, 且具有很高的数据挖掘研究价值。本文针对生理学时间序列数据, 通过对结构化查询语言SQL进行扩展。实现了对时间连续数据的分析和查询功能, 期望通过对生理学数据的分析, 达到发现和预测疾病的目的。

1 SQL 扩展语言设计基础

( 1) 关系型数据库是建立在关系模型基础上的数据库。当前主流的数据库产品都是基于关系模型, 支持结构化查询语言。本文中的时间连续数据是存储在关系型数据库中。

( 2) 结构化查询语言SQL, 是一种用于存取数据以及查询、更新和管理关系数据库系统的语言。结构化查询语言是高级的非过程化编程语言, 允许用户在高层数据结构上工作。它不要求用户指定对数据的存放方法, 也不需要用户了解具体的数据存放方式, 所以具有完全不同底层结构的不同数据库系统可以使用相同的结构化查询语言作为数据输入与管理接口。结构化查询语言语句可以嵌套, 这使它具有极大的灵活性和强大的功能[2]。

本项目在SQL语言的框架下, 对其功能进行扩展, 以支持时间连续数据的相似序列查找。使得该SQL扩展语言不仅具有与SQL相同的灵活性, 还使其具有了良好的可移植性。

( 3) 相似序列查询方法标准。相似序列匹配算法是相似查询算法中的重要组成部分, 它的特性极大地影响着整个试验系统的效率与功能的实现。因此它必须满足以下三个条件: 高效性, 由于该数据库中将有百万条以上的记录, 因此每条记录的相似匹配效率显得尤为重要; 准确性, 是指所得结果与给定序列的相似度, 在本项目中, 我们使用欧式距离作为量度二者之间相似度的标准; 可分级, 是指所使用的相似序列匹配算法, 应该易于进行不同相似度等级的序列查询, 通过设置定位匹配容忍值, 分段聚合近似法分块长度或者小波变换级别和序列之间匹配的欧氏距离D等参数, 可得到符合不同相似度等级的结果子序列[3]。

2 SQL 扩展语言处理流程

2. 1 功能流程

通过对用户提交的查询语句进行分解, 分解出标准SQL和扩展功能, 并在关系型数据库返回的原始结果集的基础上进行扩展功能处理, 得到最终的结果数据集。系统实现该扩展SQL语言的功能流程如图1所示。

用户从系统界面输入框输入查询语句后。程序首先对输入的语句进行解析。剥离扩展功能, 将扩展功能处理类型与相关参数写入扩展功能队列, 运行处理后的标准SQL语句返回数据集, 根据扩展功能队列中扩展功能参数, 对返回的数据集进行处理, 将得到的最终数据集返回系统界面; 如果是非法语句, 则返回错误信息。试验系统使用Java程序语言设计实现。

2. 2 时间连续数据存储

在本系统中, 人体生理数据被写入一个EDF ( European DataFormat) 文件中, 每一次检测的数据将以一条记录的形式存储于数据库中, 所有信息存储在传统关系型数据库, 其中包括一个指针。通过该指针, 指向对应的信号文件中的信号, 信号文件则以EDF格式存储于硬盘。指针为一个三元组, 形式如下:

[文件路径, 信号名, 时间段]

其中文件路径是EDF信号文件的物理路径; 可通过该路径找到人体生理数据信号所在的文件, 信号名称是该指针所指向的信号在文件中的名称; 时间段是信号开始和结束的样本点号, 一个文件指针可包含多个时间段, 表示多段信号。

2. 3 SQL 扩展功能

为了不破坏SQL语言原有的语法特征, 让使用者更好地理解扩展功能。本文自定义了一个函数。形式如下:

Time Series Data ( 列名)

通过调用此函数可将调用列当做时间序列数据进行处理。

本文所述工具定义了若干运算符完成四个功能:

(1) 单值查询, 数值范围符合条件的数据段;

(2) 时间段查询, 某一确定位置的数据段;

( 3) 趋势查询, 查询一定粒度下, 时间序列数据变化趋势符合条件的数据段[4];

( 4) 相似性查询, 查询与子序列相似的数据段。

这些运算符只能与扩展函数搭配使用, 完成扩展功能, 运算符的用法如表1所示。

这里所有的扩展符号返回的数据都是一个指针, 可表示一段或者多段子序列。时间段的表示方法如下所示:

[开始点: 结束点]

由一个开始点参数和一个结束点参数表示。开始点必须小于结束点, 且都为正整数, 如果两个参数相等, 则表示一个单独的点。

大于号、小于号等运算符, 可对序列进行单值查询, 返回符合条件的序列段, 如果没有符合条件的序列, 则该条记录不符合此条件。

等于号可以用于单值查询, 也可用于时间段查询, 当等于号用于时间段查询时, 后面可跟多个时间段, 时间段之间不需要分隔符, 默认为‘与’关系。

Slope[x]运算符用于序列趋势查询, 是对序列斜率进行条件判断的符号。方括号内有一个参数用来设置斜率计算的粒度大小, 该参数是正整数, 最小为1, 最大为该序列的长度。假设参数为5, 则该序列中每五个点求平均值得到一个新的点, 相邻的两个点之间计算斜率。当该参数大于等于序列长度时, 斜率为零。

Like[x]运算符是用来查询相似序列的运算符。运算符后跟一个指针表示一个子序列, 在整个序列中查询与此子序列相似的序列。方括号内的参数表示相似度, 参数范围是0到9, 参数越小相似度越高, 0表示完全相同。

2. 4 扩展语言应用

SQL扩展语言采用类似SQL语句的描述, 嵌入扩展功能, 提交系统后可执行子序列查询功能。例如:

Select record_id, Time Series Data ( Respiration) from physioda-ta where Time Series Data ( Respiration) Like[3][Data , Respira-tion, [1000: 2000]]

该例句执行的功能是: 查询生理学数据记录表physiodata中, 与给定序列[Data, Respiration, [1000: 2000]]相似的所有Respiration信号子序列, 其中序列相似度参数为3。

该语句返回的结果集是: 存在的相似子序列的数据记录中, record_id列数据与结果子序列的指针, 这些指针分别指向每条记录的信号序列中符合条件的子序列。

具体的相似查询算法将在后面的章节中进行详细的说明。

通过对SQL进行功能扩展, 可以高效地对时间连续数据的趋势、数值等特征进行搜索, 还可以从一个长序列中找出与某一特定序列相似的子序列。使用这些扩展功能, 可以完成一些标准SQL无法完成的功能。

3 相似序列查找算法

本文设计的算法, 可以通过三步找到相似序列。首先, 需要对子序列进行预处理, 计算子序列的特征值并计算一部分相似查询参数, 然后, 通过这些特征值, 在查询序列中进行定位处理, 找出可能相似的多个位置, 最后通过一些算法与这些可能相似的子序列进行逐点比较, 找出符合相似度的结果序列。

3. 1 预处理给定序列

对给定序列进行预处理, 主要是获得一些后续算法中需要的参数, 以及给定序列的特征值, 用来进行可能相似子序列的定位。在测试系统中, 需要参数包括信号取值范围等, 给定序列的特征值包括序列的开始点、结束点以及极值点。通过特征点可以在一个长序列中, 快速定位到可能与给定序列相似的子序列。如2. 4中所述扩展SQL语句例子, 预处理阶段通过文件指针[Data, Respiration, [1000: 2000]], 读入给定序列数据, 获取信号的取值范围参数、开始点、结束点, 并计算序列的各个极值点作为该序列的特征点, 用于之后的匹配计算。

3. 2 可能相似子序列定位

在这一阶段, 以给定序列[Data 0, Respiration, [1000:2000]]的开始点的值在整个序列中搜索, 搜索到符合定位容忍值范围的点后, 首先计算匹配序列长度是否足够, 在2. 4节的例子中, 是判断从定位点到信号结尾长度是否大于等于1000, 然后开始按照特征值的相对位置顺序, 进行逐一比较。如图2所示。

图2中的小圆圈表示给定序列和可能相似子序列的特征值点。如果所有的特征值点都符合定位容忍值, 那么该子序列可作为可能相似的子序列, 进入下一步的处理。定位容忍值Ltolerance的计算方法如下:

其中, S为给定的序列样本点值, SC为与之相匹配的子序列对应的样本点值。由于每个序列的基值不同, 我们需要使用相对差, 而不是绝对差, 因此需要使用距离除以范围值。在这里, 绝对差是指进行比较的两个样本点之间的真实差值, 而相对差是指绝对差值与样本点取值范围的比值。使用相对差的意义在于忽略不同信号样本基础值不同的差异, 使比较算法可以规范化。Srange为被查询序列的样本点取值范围。

3. 3 子序列相似匹配

在这一阶段, 完成相似定位, 并找出一系列可能相似的子序列之后, 需要将给定序列[Data , Respiration, [1000: 2000]]与可能相似的子序列进行比较。相似序列比较的算法, 是一个研究热点, 现有的算法有许多种, 例如分段聚合近似法 ( PAA) 、小波变换法、数据抽样法、滑动窗口法、在线挖掘算法等等[5]。其中分段聚合近似法与小波变换法简单易用且有较高的处理效率, 且便于进行相似度分级[6]。

两种算法在性能方面有些差别。经过测试, 分段聚合近似法在匹配速度上优于小波变换算法, 而在准确度上, 则是后者更优。

( 1) 分段聚合近似法

分段聚合近似PAA ( Piecewise Aggregate Approximation) 将时间序列Q = { q1, q2, …, qm} 用另外一个序列R表示, 有R ={ r1, r2, …, rw} , 其中w < m, 且m被w整除。令k = m/w, 则R中元素ri满足条件:

分段聚合近似表示将长度为m的时间序列Q转变成长度w的序列R, 进而实现了将原序列从高维到低维的降维过程。降维后的时间序列可以粗糙地表示原时间序列的基本形态, 缩短了序列的长度, 隐藏部分波形细节, 但保留大部分波形变化信息[7], 反映了时间序列的整体变化趋势, 但容易忽视局部数据分布形态, 尤其是当w值逐渐增大时[8]。通过设置子区间的宽度k, 可以控制序列查询的相似度。分段聚合近似法如图3所示, X轴表示采样点序列, Y轴表示采样点数值, 单位为m V。

( 2) 基于小波变换的算法

小波变换法是一种通用的数字信号处理技术。类似于傅里叶变换, 小波变换把输入的序列变换成一系列小波参数, 少数的几个小波参数拥有原来序列的大部分特征, 从而可以通过小波变换的方法以较少内存使用和计算的开销[7,9,10,11]实现快速匹配。在本文的试验系统中, 使用Haar小波对原序列进行不同级别的小波变换, 每个级别的小波变换可以将序列长度变换为上一级别可变换的一半。例如2级的变换将原序列变为其四分之一长度的序列, 但变换后仍然保留原序列的趋势变化信息, 这样可以实现对原序列的降维。不同级别的小波分解如图4所示, X轴Y轴表示意义与图3相同。

3. 4 相似度分级

本文中所定义的相似查询功能的参数范围为0到9, 因此相似度查询等级可分为0到9共十个等级。0表示每一个样本点都完全相同, 等级值越大相似度越低。通过调整一些相似查询参数的值来控制相似度, 得到不同相似度的结果序列[11]。这些参数包括定位匹配容忍值 ( Ltolerance) , 分段聚合近似法分块长度 ( Length) 或者小波变换级别 ( Level) 和序列之间的欧氏距离D等参数, 其中欧氏距离D的计算公式为:

可以通过配置以上相似查询参数的参数变表, 来控制相似查询的功能。

4 结语

本文所述方法在传统关系型数据库的基础上, 对结构化查询语言SQL进行扩展, 使其可以完成时间连续型数据的分析和查询功能。相似序列查询算法是该扩展语句的核心功能, 通过分段聚合近似法和小波变换方法对给定的序列和可能的子序列进行相似匹配。这两种方法简单高效, 且易于进行相似度分级, 很好地实现了相似子序列的查找。

本文所述SQL扩展语言, 为时间连续数据的分析和处理提供了一种可行的方案。然而试验系统所实现的SQL扩展功能还有所不足。不足之处在于, 这些扩展功能的实现只是对扩展语句进行了预解析, 然后对标准SQL语句返回的结果集进行处理, 得到最终的结果集。这使得SQL的一些特性没有实现, 希望在未来的工作中可以对这一方面进行改进, 重新编写标准SQL的编译器, 以完成这些没有实现的功能。

摘要：在家庭电子医疗平台中, 存在生理学时间连续数据, 实现对其分析和查询是数据利用的基础。针对这类数据的特点, 提出以关系型数据库结构化查询语言SQL为基础, 定义相似查询算法, 快速有效地从给定信号序列中找出符合某一相似度等级的相似子序列。相似匹配使用了分段聚合近似法和小波变换两种算法, 易于进行子序列的相似度分级。实验结果表明, 该试验系统能够高效、准确地完成设计功能。

关键词：时间连续数据,小波变换,扩展结构化查询语言,生理学信号,电子医疗

参考文献

[1]娄海容.国外电子病案现状及前景[J].现代医院, 2003 (01) :73-75.

[2]李武, 姚珺.数据库原理及应用[M].哈尔滨:哈尔滨工程大学出版社, 2011:179-180.

[3]李林海.时间序列数据挖掘中的特征表示与相似性度量方法研究[D].大连:大连理工大学, 2012.

[4]聂淑媛.时间序列分析的早期发展[D].西安:西北大学, 2012.

[5]刘建伟.流数据查询系统结构及模式查询算法的研究[D].上海:东华大学, 2005.

[6]刘博宁, 张建业, 张鹏, 等.基于曲率距离的时间序列相似性搜索方法[J].电子与信息学报, 2012 (9) :2200-2207.

[7]刘敬.基于小波变换的图像压缩算法研究[D].重庆:重庆大学, 2012.

[8]李林海, 郭崇慧.基于云模型的时间序列分段聚合近似方法[J].控制与决策, 2011, 26 (10) :1525-1529.

[9]武永红.基于小波变换的图像无损压缩算法研究[D].重庆:重庆大学, 2012.

[10]张勇.时间序列模式匹配技术研究[D].武汉:华中科技大学, 2012.