更新时间: 2018-10-10 00:15:06       分类: 未分类


前言

我们考虑一个对web数据库进行的查询,当用户输入的限制条件较为苛刻时,很有可能会得到一个很小的、甚至可能为空的结果集,而这很有可能不是用户所想看到的。因此我们希望在进行查询时,如果遇到此类情况,就适当将用户的限制条件放松一些,来得到一个更大的结果集。

本文将主要探讨如何根据用户搜索的上下文环境,以及数据库中的整体环境来对用户输入的限制条件进行合理的放松。

使用语言为Python(2.7)

整体思路

第一步:衡量各个属性值对于本查询的重要程度。

第二步:根据各个属性值的重要程度,决定该值可以放大的范围。

第三步:根据在第二步中计算出的范围松弛查询,然后执行松弛过后的查询。

Demo(10.06)

首先确定一下我们要在什么形式的数据上来做工作,我对携程的爬虫数据进行了二次加工,暂定使用下面的数据形式来作为我们的xml样本:

<hotel hid = "1702362">
         <general>
            <title>
                富阳世豪假日酒店
            </title>
            <address>
                杭州富阳区迎宾北路58-1号
            </address>
            <level>
                舒适型
            </level>
            <roomCount>
                130
            </roomCount>
            <score>
                4.1
            </score>
            <supports>
                <support type="交通设施" value="免费停车场" />
                <support type="交通服务" value="叫车服务" />
                <support type="休闲娱乐" value="足浴" />
                <support type="休闲娱乐" value="棋牌室" />
                <support type="休闲娱乐" value="KTV" />
                <!--注意这个嵌套的属性,我们可以在计算属性重要程度的时候利用上深度,越深的属性说明对用户越重要,因此松弛程度就越小-->
            </supports>
            <rooms>
                <room rid="4738677">
                    <title>大床房</title>
                    <price>188</price>
                    <personCount>2</personCount>
                    <canOrder>true</canOrder>
                </room>
                <room rid="4738678">
                    <title>标准间</title>
                    <price>188</price>
                    <personCount>2</personCount>
                    <canOrder>true</canOrder>
                </room>
            </rooms>
         </general>
         <spatioTemporal>
            <latitude>39.91505577441051</latitude>
            <longitude>116.43634646030722</longitude>
            <time>时间属性缺失,可以想办法自己模拟</time>
         </spatioTemporal>
    </hotel>

其中所有属性分为三类:

  1. 时空属性(有一套自己的处理逻辑): latitude, longitude, time
  2. 数值型属性: roomCount, score, rooms>room>price
  3. 分类型属性:所有其他属性

问题与思考:

  1. (问题)爬虫的提供的数据源无法告知我们什么时间有哪些房间可以预定,这就导致了时间属性的缺失,这个可能要我们想办法模拟。

  2. (启发)xml的树状结构给我们暗示了不同类型属性的重要程度,我觉得可以简单的认为,深度越大的属性,其重要性就越高,因此在松弛时可以放松的范围就越小,因此可以在weight的地方想办法把这个深度的影响给加进去。

  3. (问题)匹配问题,和数据库的二维表数据进行对比,可以发现xml的数据形式其实进行了一定程度的聚合。就以上面的那个携程酒店为例,关系型数据可能会把它处理成下面这样:

     hotel		roomType		price
     富阳酒店	大床房			150
     富阳酒店	标准间			180
     富阳酒店	套房			300
    

    一共由3条数据组成,但在xml里面就不一样了,他们都是一棵树上的:

<hotel name = "富阳酒店">
	<rooms>
		<room type="大床房"  price = 150/>
		<room type="标准间" price = 180/>
		<room type="套房" price = 300/>
	</rooms>
</hotel>

这样的好处是,储存空间减少了,并且可以减少查询的次数来提升速度(无需join),但是在返回结果时需要额外处理一个问题,那就是如果查询命中了,究竟是直接返回整棵树?还是返回树里命中的部分,把其他裁减掉?或者返回整棵树,但对命中的部分加以标记?这个可以在结果分类的部分好好考虑考虑。

一点个人看法

论文的两个重点保持不变,依然是XML(树形结构)时空属性,我觉得我们研究的几个重要意义在于:

这些都是和原有basis不一样的地方,同时也是实验部分需要重点体现的地方,目前只是提出了这些点,具体怎么实现,还需要我们一起多多思考。

代码部分现在只是把idf的计算给写完了,离全部完成还有蛮多的工作量,考虑到国庆后一上班可以自由利用的时间就会变少,还是希望小葭同学在平常多思考一些细节和实现思路,然后给我更加明确、细化的目标来逐个实现,这样应该能够提高不少的效率~

Keep thinking, enjoy the journey!

编码过程中想到的一些问题

  1. 查询松弛整个过程太依赖于数据的静态性,每当数据库中有了新记录,就需要经过各种计算来重新生成一遍辅助表。然而数据库一般都是流动性很强的,这样势必会有时效性或者性能问题。

体现XML的不同?

既然我们一时无法自己找到突破点,就先参考一下他山之石吧。

先来看看李晓桐学姐的论文中,是如何体现XML的不同?

  1. 提出XML时空数据模型(2.2.1)

    把节点的类型做了分类,并用一个五元组标识不确定时空数据

    这里主要是因为强调了不确定性,和我们demo中应用到的xml文档模型还是有些区别的,或许可以考虑考虑我们的文档模型可不可以借助树形结构的优势进行扩展?

  2. P-文档模型 (2.2.2)

    把节点类型分为了独立性和互斥型;这个也是和不确定性数据强相关的内容,感觉对我们暂时没有什么帮助。

  3. Dewey编码 (2.3)

    提出了在xml中对节点进行快速定位的一种编码,在后面有应用到。另一种定位的方法是xpath。

    可以想想节点定位方案如何在我们的课题中发挥作用。

  4. T-List(3.2)

    一种根据时间段为XML树制作的索引,用于优化多次松弛查询的效率。是针对树形结构遍历起来比较耗时这个特点考虑的(递归深搜的效率肯定是比一维循环低很多)。

    这个点上我有个想法,可以基于hash map来做一个属性缓存索引集,减少多次查询松弛情况下的耗时(后面有机会详谈)

基本上就是这些了,其余的部分和xml结构本身挂钩的倒并不是很多。

参考这个,我觉得我们能够根据xml结构的特点,在松弛算法部分提出一两个细节,并且对模型做一下介绍是不是就可以了。

另外引用到的下面几篇论文也是和xml相关的,可以看看它们是怎么描述xml的:

柏禄一,徐长明,刘旭龙,于长永. 基于 XML 的不确定时空数据模型[J]. 东北大学学报:自然科学版,2016, 37(11): 1546-1550.

Liu C, Li J, Yu J X, and Zhou R. Adaptive relaxation for querying heterogeneous XML data sources [J], Information Systems, 2010, 35: 688-707

代码实现简要说明

github地址: https://github.com/MarkLux/xml-query-relaxation

python语言本身是非常语义化的,看的时候不用有太大压力,能明白意思就行

说下几个文件都是干嘛的;

define.py 定义了属性的辅助类(可以认为就是辅助表), 每个属性对应一个Attribute对象,里面封装了跟属性idf有关的一些方法,并且做了一层缓存。

importance.py 定义了计算idf的数学方法,以及sub_threshold的计算逻辑,基本上就是把basis里面和属性重要性计算相关的所有公式都实现了下。

process.py 定义了核心流程的处理函数。

reader.py 定义了数据读取相关的工作,如从文件中解析xml文档,深度优先遍历xml树。

settings.py 定义了一些常量和配置项


评论

还没有评论