{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T09:10:11Z","timestamp":1687425011525},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2012,4,25]],"date-time":"2012-04-25T00:00:00Z","timestamp":1335312000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>In this paper we propose various extensions to the relational model to support similarity-based querying. We build upon the<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0960129511000740_char1\" \/><\/jats:private-char>-relation model, where tuples are assigned values from an arbitrary semiring<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0960129511000740_char1\" \/><\/jats:private-char>, and its associated positive relational algebra<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0960129511000740_inline1\"><jats:alt-text>$\\text{RA}^{+}_{\\mathcal{K}}$<\/jats:alt-text><\/jats:inline-graphic>. We consider a recently proposed extension to<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0960129511000740_inline1\"><jats:alt-text>$\\text{RA}^{+}_{\\mathcal{K}}$<\/jats:alt-text><\/jats:inline-graphic>using a monus operation on the semiring to support negative queries, and show how, surprisingly, it fails for important \u2018fuzzy\u2019 semirings. Instead, we suggest using a negation operator. We also consider the identities satisfied by the relational algebra<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0960129511000740_inline1\"><jats:alt-text>$\\text{RA}^{+}_{\\mathcal{K}}$<\/jats:alt-text><\/jats:inline-graphic>. We show that moving from a semiring to a particular form of lattice (a De Morgan frame) yields a relational algebra that satisfies all the classical (positive) relational algebra identities. We claim that to support real-world similarity queries realistically, one must move from tuple-level annotations to attribute-level annotations. We show in detail how our De Morgan frame-based model can be extended to support attribute-level annotations and give worked examples of similarity queries in this setting.<\/jats:p>","DOI":"10.1017\/s0960129511000740","type":"journal-article","created":{"date-parts":[[2012,4,25]],"date-time":"2012-04-25T12:28:35Z","timestamp":1335356915000},"page":"686-718","source":"Crossref","is-referenced-by-count":2,"title":["Extending relational algebra with similarities"],"prefix":"10.1017","volume":"22","author":[{"given":"MELITA","family":"HAJDINJAK","sequence":"first","affiliation":[]},{"given":"GAVIN","family":"BIERMAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,4,25]]},"reference":[{"key":"S0960129511000740_ref32","volume-title":"Principles of Database and Knowledge-Base Systems: Volume 2","author":"Ullman","year":"1989"},{"key":"S0960129511000740_ref31","volume-title":"Principles of Database and Knowledge-Base Systems: Volume 1","author":"Ullman","year":"1988"},{"key":"S0960129511000740_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24627-5_17"},{"key":"S0960129511000740_ref26","first-page":"429","article-title":"Quasi-boolean lattices and associations. In: Proceedings of Colloquia Mathematica Societatis J\u00e1nos Bolyai.","volume":"43","author":"Salii","year":"1983","journal-title":"Lectures in Universal Algebra"},{"key":"S0960129511000740_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33289-8_1"},{"key":"S0960129511000740_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"S0960129511000740_ref18","first-page":"137","article-title":"Fuzzy database modeling of imprecise and uncertain engineering information.","volume":"195","author":"Ma","year":"2006","journal-title":"Studies in Fuzziness and Soft Computing"},{"key":"S0960129511000740_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(75)90039-6"},{"key":"S0960129511000740_ref8","volume-title":"Introduction to Lattices and Order","author":"Davey","year":"1990"},{"key":"S0960129511000740_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"S0960129511000740_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01359910"},{"key":"S0960129511000740_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182254"},{"key":"S0960129511000740_ref12","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2006.32.2.263"},{"key":"S0960129511000740_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511805967"},{"key":"S0960129511000740_ref23","volume-title":"Fuzzy Relational Calculus: Theory, Applications and Software","author":"Peeva","year":"2004"},{"key":"S0960129511000740_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056009"},{"key":"S0960129511000740_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"S0960129511000740_ref5","doi-asserted-by":"crossref","unstructured":"Buneman P. , Khanna S. and Tan W. (2001) Why and where: A characterization of data provenance. In: Proceedings of the International Conference on Database Theory 316\u2013330.","DOI":"10.1007\/3-540-44503-X_20"},{"key":"S0960129511000740_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04031-7"},{"key":"S0960129511000740_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0165-0114(89)90201-7"},{"key":"S0960129511000740_ref33","first-page":"539","article-title":"On the structure of fuzzy lattices.","volume":"29","author":"Wang","year":"1986","journal-title":"Acta Mathematica"},{"key":"S0960129511000740_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.33"},{"key":"S0960129511000740_ref21","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/PL00022469","article-title":"Equational fragments of systems for arithmetic.","volume":"46","author":"Montagna","year":"2001","journal-title":"Algebra Universalis"},{"key":"S0960129511000740_ref10","doi-asserted-by":"crossref","unstructured":"Green T. , Karvounarakis G. and Tannen V. (2007) Provenance semirings. In: Proceedings of the Symposium on Principles of Database Systems 31\u201340.","DOI":"10.1145\/1265530.1265535"},{"key":"S0960129511000740_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2009.09.001"},{"key":"S0960129511000740_ref3","doi-asserted-by":"publisher","DOI":"10.1109\/IRI.2006.252414"},{"key":"S0960129511000740_ref19","first-page":"189","article-title":"A literature overview of fuzzy database models.","volume":"24","author":"Ma","year":"2008","journal-title":"Journal of Information Science and Engineering"},{"key":"S0960129511000740_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"S0960129511000740_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90241-X"},{"key":"S0960129511000740_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276340"},{"key":"S0960129511000740_ref11","first-page":"135","article-title":"Similarity measures for relational databases.","volume":"33","author":"Hajdinjak","year":"2009","journal-title":"Informatica"},{"key":"S0960129511000740_ref30","doi-asserted-by":"publisher","DOI":"10.1145\/1388240.1388260"},{"key":"S0960129511000740_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"S0960129511000740_ref17","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals.","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Soviet Physics Doklady"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129511000740","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T08:29:22Z","timestamp":1687422562000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129511000740\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,25]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["S0960129511000740"],"URL":"https:\/\/doi.org\/10.1017\/s0960129511000740","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,25]]}}}