965:
have a lossless join if there is some way in which we can repeatedly perform lossless joins until all the schemas have been joined into a single schema. Once we have a new sub-schema made from a lossless join, we are not allowed to use any of its isolated sub-schema to join with any of the other
1533:
890:
798:
276:
1270:
963:
704:
664:
1419:
557:
1448:
1324:
624:
1369:
1210:
346:
1004:
85:
1151:
1037:
1118:
1091:
1064:
500:
473:
198:
171:
426:
577:
446:
397:
370:
296:
141:
121:
45:
1698:
1453:
804:
712:
1638:
583:
203:
1581:
1611:
1674:
1651:
91:
of the two smaller relations yields back the original relation. This is central in removing redundancy safely from
1744:
299:
1739:
1234:
903:
669:
629:
1749:
1702:
1378:
516:
1424:
1278:
589:
1329:
1165:
305:
1553:
Pohler, K (2015). "Lossless-Join
Decomposition: applications in quantitative computing metrics".
969:
377:
50:
1734:
1123:
1009:
1096:
1069:
1042:
478:
451:
176:
149:
1598:
402:
8:
25:
1729:
562:
431:
382:
355:
281:
126:
106:
30:
1647:
1607:
1577:
95:
while preserving the original data. Lossless join can also be called non-additive.
17:
579:
1723:
88:
1528:{\displaystyle (R_{1}\cap R_{2}\rightarrow R_{1}\setminus R_{2})\in F^{+}}
505:
Decompositions into more than two schemas can be defined in the same way.
966:
schemas. For example, if we can do a lossless join on a pair of schemas
885:{\displaystyle (R_{1}\cap R_{2})\to (R_{2}\setminus R_{1})\in F^{+}}
793:{\displaystyle (R_{1}\cap R_{2})\to (R_{1}\setminus R_{2})\in F^{+}}
92:
1699:"www.data-e-education.com - Lossless Join Decomposition"
271:{\displaystyle \pi _{R_{1}}(r)\bowtie \pi _{R_{2}}(r)=r}
1576:(Seventh ed.). Hoboken, NJ: Pearson. p. 461.
1456:
1427:
1381:
1332:
1281:
1237:
1168:
1126:
1099:
1072:
1045:
1012:
972:
906:
807:
715:
672:
632:
592:
565:
519:
481:
454:
434:
405:
385:
358:
308:
284:
206:
179:
152:
129:
109:
53:
33:
895:
1646:(1 ed.). Computer Science Press. p. 397.
1527:
1442:
1413:
1363:
1318:
1264:
1204:
1145:
1112:
1085:
1058:
1031:
998:
957:
884:
792:
706:. In other words, one of the following must hold:
698:
658:
618:
571:
551:
494:
467:
440:
420:
391:
364:
340:
290:
270:
192:
165:
135:
115:
79:
39:
1640:Principles of Database and Knowledge-base Systems
1555:International Journal of Applied Computer Science
1721:
1093:) to form a lossless join with another schema
1632:
1630:
1358:
1346:
1313:
1295:
1259:
1244:
1199:
1175:
1627:
1212:be the relation schema, with attributes
1606:. Computer Science Press. p. 101.
1571:
1722:
1636:
1565:
1552:
1450:. In other words, we have proven that
1272:be the set of functional dependencies.
1039:, we use this new schema (rather than
1596:
1265:{\displaystyle F=\{A\rightarrow BC\}}
958:{\displaystyle R_{1},R_{2},...,R_{n}}
1421:and we have a functional dependency
1120:(which may already be joined (e.g.,
699:{\displaystyle R_{2}\setminus R_{1}}
659:{\displaystyle R_{1}\setminus R_{2}}
559:has a lossless join with respect to
13:
1600:The theory of relational databases
14:
1761:
1496:
1414:{\displaystyle R_{1}\cap R_{2}=A}
896:Criteria for multiple sub-schemas
853:
761:
683:
643:
552:{\displaystyle R=R_{1}\cup R_{2}}
302:onto the smaller schemas. A pair
1574:Fundamentals of database systems
1443:{\displaystyle A\rightarrow BC}
1319:{\displaystyle R_{1}=\{A,B,C\}}
619:{\displaystyle R_{1}\cap R_{2}}
1691:
1667:
1590:
1546:
1509:
1483:
1457:
1431:
1250:
866:
840:
837:
834:
808:
774:
748:
745:
742:
716:
415:
409:
335:
309:
259:
253:
230:
224:
1:
1675:"Lossless-Join Decomposition"
1539:
1364:{\displaystyle R_{2}=\{A,D\}}
1205:{\displaystyle R=\{A,B,C,D\}}
341:{\displaystyle (R_{1},R_{2})}
98:
7:
1637:Ullman, Jeffrey D. (1988).
999:{\displaystyle R_{i},R_{j}}
508:
448:decomposes losslessly onto
350:lossless-join decomposition
298:is the natural join of its
80:{\displaystyle r_{1},r_{2}}
22:lossless join decomposition
10:
1766:
1156:
376:with respect to a set of
24:is a decomposition of a
1572:Elmasri, Ramez (2016).
1146:{\displaystyle R_{k,l}}
1032:{\displaystyle R_{i,j}}
378:functional dependencies
1745:Database normalization
1529:
1444:
1415:
1365:
1320:
1266:
1206:
1147:
1114:
1087:
1060:
1033:
1000:
959:
886:
794:
700:
660:
620:
573:
553:
496:
469:
442:
422:
393:
366:
342:
292:
272:
194:
167:
137:
117:
81:
41:
1597:Maier, David (1983).
1530:
1445:
1416:
1366:
1321:
1267:
1207:
1148:
1115:
1113:{\displaystyle R_{k}}
1088:
1086:{\displaystyle R_{j}}
1061:
1059:{\displaystyle R_{i}}
1034:
1006:to form a new schema
1001:
960:
900:Multiple sub-schemas
887:
795:
701:
661:
621:
574:
554:
497:
495:{\displaystyle R_{2}}
470:
468:{\displaystyle R_{1}}
443:
423:
394:
367:
343:
293:
273:
195:
193:{\displaystyle R_{2}}
168:
166:{\displaystyle R_{1}}
144:decomposes losslessly
138:
118:
82:
42:
1740:Database constraints
1454:
1425:
1379:
1330:
1279:
1235:
1166:
1124:
1097:
1070:
1043:
1010:
970:
904:
805:
713:
670:
630:
590:
563:
517:
479:
452:
432:
421:{\displaystyle r(R)}
403:
383:
374:have a lossless join
356:
306:
282:
204:
177:
150:
127:
107:
51:
31:
1275:Decomposition into
1750:Relational algebra
1525:
1440:
1411:
1371:is lossless under
1361:
1316:
1262:
1202:
1143:
1110:
1083:
1056:
1029:
996:
955:
882:
790:
696:
656:
616:
569:
549:
492:
465:
438:
418:
389:
362:
338:
288:
268:
190:
163:
133:
113:
77:
37:
572:{\displaystyle F}
441:{\displaystyle F}
392:{\displaystyle F}
365:{\displaystyle R}
291:{\displaystyle r}
136:{\displaystyle R}
116:{\displaystyle r}
40:{\displaystyle r}
1757:
1714:
1713:
1711:
1710:
1701:. Archived from
1695:
1689:
1688:
1686:
1685:
1671:
1665:
1664:
1662:
1660:
1645:
1634:
1625:
1624:
1622:
1620:
1605:
1594:
1588:
1587:
1569:
1563:
1562:
1550:
1534:
1532:
1531:
1526:
1524:
1523:
1508:
1507:
1495:
1494:
1482:
1481:
1469:
1468:
1449:
1447:
1446:
1441:
1420:
1418:
1417:
1412:
1404:
1403:
1391:
1390:
1374:
1370:
1368:
1367:
1362:
1342:
1341:
1325:
1323:
1322:
1317:
1291:
1290:
1271:
1269:
1268:
1263:
1227:
1223:
1219:
1215:
1211:
1209:
1208:
1203:
1152:
1150:
1149:
1144:
1142:
1141:
1119:
1117:
1116:
1111:
1109:
1108:
1092:
1090:
1089:
1084:
1082:
1081:
1065:
1063:
1062:
1057:
1055:
1054:
1038:
1036:
1035:
1030:
1028:
1027:
1005:
1003:
1002:
997:
995:
994:
982:
981:
964:
962:
961:
956:
954:
953:
929:
928:
916:
915:
891:
889:
888:
883:
881:
880:
865:
864:
852:
851:
833:
832:
820:
819:
799:
797:
796:
791:
789:
788:
773:
772:
760:
759:
741:
740:
728:
727:
705:
703:
702:
697:
695:
694:
682:
681:
665:
663:
662:
657:
655:
654:
642:
641:
625:
623:
622:
617:
615:
614:
602:
601:
578:
576:
575:
570:
558:
556:
555:
550:
548:
547:
535:
534:
513:A decomposition
501:
499:
498:
493:
491:
490:
474:
472:
471:
466:
464:
463:
447:
445:
444:
439:
427:
425:
424:
419:
399:if any relation
398:
396:
395:
390:
371:
369:
368:
363:
347:
345:
344:
339:
334:
333:
321:
320:
297:
295:
294:
289:
277:
275:
274:
269:
252:
251:
250:
249:
223:
222:
221:
220:
199:
197:
196:
191:
189:
188:
172:
170:
169:
164:
162:
161:
142:
140:
139:
134:
122:
120:
119:
114:
86:
84:
83:
78:
76:
75:
63:
62:
46:
44:
43:
38:
1765:
1764:
1760:
1759:
1758:
1756:
1755:
1754:
1720:
1719:
1718:
1717:
1708:
1706:
1697:
1696:
1692:
1683:
1681:
1673:
1672:
1668:
1658:
1656:
1654:
1643:
1635:
1628:
1618:
1616:
1614:
1603:
1595:
1591:
1584:
1570:
1566:
1551:
1547:
1542:
1519:
1515:
1503:
1499:
1490:
1486:
1477:
1473:
1464:
1460:
1455:
1452:
1451:
1426:
1423:
1422:
1399:
1395:
1386:
1382:
1380:
1377:
1376:
1372:
1337:
1333:
1331:
1328:
1327:
1286:
1282:
1280:
1277:
1276:
1236:
1233:
1232:
1225:
1221:
1217:
1213:
1167:
1164:
1163:
1159:
1131:
1127:
1125:
1122:
1121:
1104:
1100:
1098:
1095:
1094:
1077:
1073:
1071:
1068:
1067:
1050:
1046:
1044:
1041:
1040:
1017:
1013:
1011:
1008:
1007:
990:
986:
977:
973:
971:
968:
967:
949:
945:
924:
920:
911:
907:
905:
902:
901:
898:
876:
872:
860:
856:
847:
843:
828:
824:
815:
811:
806:
803:
802:
784:
780:
768:
764:
755:
751:
736:
732:
723:
719:
714:
711:
710:
690:
686:
677:
673:
671:
668:
667:
650:
646:
637:
633:
631:
628:
627:
610:
606:
597:
593:
591:
588:
587:
564:
561:
560:
543:
539:
530:
526:
518:
515:
514:
511:
486:
482:
480:
477:
476:
459:
455:
453:
450:
449:
433:
430:
429:
428:that satisfies
404:
401:
400:
384:
381:
380:
357:
354:
353:
329:
325:
316:
312:
307:
304:
303:
283:
280:
279:
245:
241:
240:
236:
216:
212:
211:
207:
205:
202:
201:
184:
180:
178:
175:
174:
157:
153:
151:
148:
147:
128:
125:
124:
108:
105:
104:
101:
71:
67:
58:
54:
52:
49:
48:
47:into relations
32:
29:
28:
18:database design
12:
11:
5:
1763:
1753:
1752:
1747:
1742:
1737:
1732:
1716:
1715:
1690:
1666:
1652:
1626:
1612:
1589:
1583:978-0133970777
1582:
1564:
1544:
1543:
1541:
1538:
1537:
1536:
1522:
1518:
1514:
1511:
1506:
1502:
1498:
1493:
1489:
1485:
1480:
1476:
1472:
1467:
1463:
1459:
1439:
1436:
1433:
1430:
1410:
1407:
1402:
1398:
1394:
1389:
1385:
1360:
1357:
1354:
1351:
1348:
1345:
1340:
1336:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1289:
1285:
1273:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1229:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1158:
1155:
1140:
1137:
1134:
1130:
1107:
1103:
1080:
1076:
1053:
1049:
1026:
1023:
1020:
1016:
993:
989:
985:
980:
976:
952:
948:
944:
941:
938:
935:
932:
927:
923:
919:
914:
910:
897:
894:
893:
892:
879:
875:
871:
868:
863:
859:
855:
850:
846:
842:
839:
836:
831:
827:
823:
818:
814:
810:
800:
787:
783:
779:
776:
771:
767:
763:
758:
754:
750:
747:
744:
739:
735:
731:
726:
722:
718:
693:
689:
685:
680:
676:
653:
649:
645:
640:
636:
613:
609:
605:
600:
596:
580:if and only if
568:
546:
542:
538:
533:
529:
525:
522:
510:
507:
489:
485:
462:
458:
437:
417:
414:
411:
408:
388:
361:
337:
332:
328:
324:
319:
315:
311:
287:
267:
264:
261:
258:
255:
248:
244:
239:
235:
232:
229:
226:
219:
215:
210:
187:
183:
160:
156:
132:
112:
100:
97:
74:
70:
66:
61:
57:
36:
9:
6:
4:
3:
2:
1762:
1751:
1748:
1746:
1743:
1741:
1738:
1736:
1735:Data modeling
1733:
1731:
1728:
1727:
1725:
1705:on 2014-02-21
1704:
1700:
1694:
1680:
1676:
1670:
1655:
1649:
1642:
1641:
1633:
1631:
1615:
1613:0-914894-42-0
1609:
1602:
1601:
1593:
1585:
1579:
1575:
1568:
1561:(4): 190–212.
1560:
1556:
1549:
1545:
1520:
1516:
1512:
1504:
1500:
1491:
1487:
1478:
1474:
1470:
1465:
1461:
1437:
1434:
1428:
1408:
1405:
1400:
1396:
1392:
1387:
1383:
1355:
1352:
1349:
1343:
1338:
1334:
1310:
1307:
1304:
1301:
1298:
1292:
1287:
1283:
1274:
1256:
1253:
1247:
1241:
1238:
1230:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1172:
1169:
1161:
1160:
1154:
1138:
1135:
1132:
1128:
1105:
1101:
1078:
1074:
1051:
1047:
1024:
1021:
1018:
1014:
991:
987:
983:
978:
974:
950:
946:
942:
939:
936:
933:
930:
925:
921:
917:
912:
908:
877:
873:
869:
861:
857:
848:
844:
829:
825:
821:
816:
812:
801:
785:
781:
777:
769:
765:
756:
752:
737:
733:
729:
724:
720:
709:
708:
707:
691:
687:
678:
674:
651:
647:
638:
634:
611:
607:
603:
598:
594:
585:
581:
566:
544:
540:
536:
531:
527:
523:
520:
506:
503:
487:
483:
460:
456:
435:
412:
406:
386:
379:
375:
359:
351:
330:
326:
322:
317:
313:
301:
285:
265:
262:
256:
246:
242:
237:
233:
227:
217:
213:
208:
185:
181:
158:
154:
146:onto schemas
145:
130:
110:
96:
94:
90:
72:
68:
64:
59:
55:
34:
27:
23:
19:
1707:. Retrieved
1703:the original
1693:
1682:. Retrieved
1678:
1669:
1657:. Retrieved
1653:0-88175188-X
1639:
1617:. Retrieved
1599:
1592:
1573:
1567:
1558:
1554:
1548:
899:
512:
504:
373:
349:
143:
102:
89:natural join
87:such that a
21:
15:
372:or said to
300:projections
103:A relation
1724:Categories
1709:2014-02-12
1684:2016-02-07
1540:References
278:, that is
123:on schema
99:Definition
1730:Databases
1679:Cs.sfu.ca
1659:16 August
1619:16 August
1513:∈
1497:∖
1484:→
1471:∩
1432:→
1393:∩
1251:→
870:∈
854:∖
838:→
822:∩
778:∈
762:∖
746:→
730:∩
684:∖
644:∖
626:includes
604:∩
537:∪
238:π
234:⋈
209:π
93:databases
1375:because
509:Criteria
26:relation
1157:Example
584:closure
1650:
1610:
1580:
1644:(PDF)
1604:(PDF)
348:is a
1661:2024
1648:ISBN
1621:2024
1608:ISBN
1578:ISBN
1326:and
1231:Let
1224:and
1162:Let
1153:)).
582:the
475:and
173:and
20:, a
1066:or
666:or
586:of
352:of
200:if
16:In
1726::
1677:.
1629:^
1559:21
1557:.
1220:,
1216:,
502:.
1712:.
1687:.
1663:.
1623:.
1586:.
1535:.
1521:+
1517:F
1510:)
1505:2
1501:R
1492:1
1488:R
1479:2
1475:R
1466:1
1462:R
1458:(
1438:C
1435:B
1429:A
1409:A
1406:=
1401:2
1397:R
1388:1
1384:R
1373:F
1359:}
1356:D
1353:,
1350:A
1347:{
1344:=
1339:2
1335:R
1314:}
1311:C
1308:,
1305:B
1302:,
1299:A
1296:{
1293:=
1288:1
1284:R
1260:}
1257:C
1254:B
1248:A
1245:{
1242:=
1239:F
1228:.
1226:D
1222:C
1218:B
1214:A
1200:}
1197:D
1194:,
1191:C
1188:,
1185:B
1182:,
1179:A
1176:{
1173:=
1170:R
1139:l
1136:,
1133:k
1129:R
1106:k
1102:R
1079:j
1075:R
1052:i
1048:R
1025:j
1022:,
1019:i
1015:R
992:j
988:R
984:,
979:i
975:R
951:n
947:R
943:,
940:.
937:.
934:.
931:,
926:2
922:R
918:,
913:1
909:R
878:+
874:F
867:)
862:1
858:R
849:2
845:R
841:(
835:)
830:2
826:R
817:1
813:R
809:(
786:+
782:F
775:)
770:2
766:R
757:1
753:R
749:(
743:)
738:2
734:R
725:1
721:R
717:(
692:1
688:R
679:2
675:R
652:2
648:R
639:1
635:R
612:2
608:R
599:1
595:R
567:F
545:2
541:R
532:1
528:R
524:=
521:R
488:2
484:R
461:1
457:R
436:F
416:)
413:R
410:(
407:r
387:F
360:R
336:)
331:2
327:R
323:,
318:1
314:R
310:(
286:r
266:r
263:=
260:)
257:r
254:(
247:2
243:R
231:)
228:r
225:(
218:1
214:R
186:2
182:R
159:1
155:R
131:R
111:r
73:2
69:r
65:,
60:1
56:r
35:r
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.